algorithm - दक्षिणावर्त क्रम में अंक क्रमबद्ध करें?




math lua (3)

एक्स, वाई अंक की एक सरणी को देखते हुए, मैं इस सरणी के बिंदु को घड़ी के क्रम में कैसे क्रमबद्ध करूं (उनके समग्र औसत केंद्र बिंदु के आसपास)? मेरा लक्ष्य अंक को "ठोस" दिखने वाले कुछ के साथ समाप्त करने के लिए बिंदु-निर्माण फ़ंक्शन को पास करना है, जितना संभव हो उतना उत्तल हो जितना संभव हो।

इसके लायक होने के लिए, मैं लुआ का उपयोग कर रहा हूं, लेकिन किसी भी छद्म कोड की सराहना की जाएगी। किसी भी मदद के लिए बहुत बहुत धन्यवाद!

अद्यतन: संदर्भ के लिए, यह सीआमेज के उत्कृष्ट उत्तर के आधार पर लुआ कोड है (मेरे "ऐप" उपसर्ग को अनदेखा करें):

function appSortPointsClockwise(points)
    local centerPoint = appGetCenterPointOfPoints(points)
    app.pointsCenterPoint = centerPoint
    table.sort(points, appGetIsLess)
    return points
end

function appGetIsLess(a, b)
    local center = app.pointsCenterPoint

    if a.x >= 0 and b.x < 0 then return true
    elseif a.x == 0 and b.x == 0 then return a.y > b.y
    end

    local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
    if det < 0 then return true
    elseif det > 0 then return false
    end

    local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
    local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
    return d1 > d2
end

function appGetCenterPointOfPoints(points)
    local pointsSum = {x = 0, y = 0}
    for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
    return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end


आप जो मांग रहे हैं वह एक प्रणाली है जो ध्रुवीय निर्देशांक के रूप में जानी जाती है। कार्टेशियन से ध्रुवीय निर्देशांक में रूपांतरण किसी भी भाषा में आसानी से किया जाता है। सूत्र इस खंड में पाए जा सकते हैं।

मुझे लुआ नहीं पता, लेकिन यह पृष्ठ इस रूपांतरण के लिए कोड स्निपेट पेश करता प्रतीत होता है।

ध्रुवीय निर्देशांक में परिवर्तित करने के बाद, बस कोण, थेटा द्वारा क्रमबद्ध करें।


आपकी समस्या का एक दिलचस्प वैकल्पिक दृष्टिकोण ट्रैवलिंग सेल्समैन समस्या (टीएसपी), यानी अनुमानित न्यूनतम पाया जाएगा। आपके सभी बिंदुओं को जोड़ने वाला सबसे छोटा रास्ता। यदि आपके अंक एक उत्तल आकार बनाते हैं, तो यह सही समाधान होना चाहिए, अन्यथा, इसे अभी भी अच्छा दिखना चाहिए (एक "ठोस" आकार को उस व्यक्ति के रूप में परिभाषित किया जा सकता है जिसमें कम परिधि / क्षेत्र अनुपात होता है, जिसे हम यहां अनुकूलित कर रहे हैं) ।

आप टीएसपी के लिए एक अनुकूलक के किसी भी कार्यान्वयन का उपयोग कर सकते हैं, जिसमें से मुझे पूरा यकीन है कि आप अपनी पसंद की भाषा में एक टन पा सकते हैं।


सबसे पहले, केंद्र बिंदु की गणना करें। फिर जो भी सॉर्टिंग एल्गोरिदम आप पसंद करते हैं, उसका उपयोग करके अंक को सॉर्ट करें, लेकिन यह निर्धारित करने के लिए कि एक बिंदु दूसरे से कम है या नहीं, यह निर्धारित करने के लिए विशेष तुलना दिनचर्या का उपयोग करें।

आप इस सरल गणना द्वारा केंद्र के संबंध में एक बिंदु (ए) बाएं या दाईं ओर (बी) के दायीं तरफ देख सकते हैं:

det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)

यदि परिणाम शून्य है, तो वे केंद्र से एक ही रेखा पर हैं, यदि यह सकारात्मक या नकारात्मक है, तो यह एक तरफ या दूसरी तरफ है, इसलिए एक बिंदु दूसरे से पहले होगा। इसका उपयोग करके आप अंक की तुलना करने के लिए कम से कम संबंध बना सकते हैं और ऑर्डर निर्धारित कर सकते हैं जिसमें क्रमबद्ध सरणी में उन्हें दिखाना चाहिए। लेकिन आपको यह निर्धारित करना होगा कि उस आदेश की शुरुआत कहां है, मेरा मतलब है कि कोण कौन सा कोण शुरू होगा (उदाहरण के लिए एक्स-अक्ष का सकारात्मक आधा)।

तुलना समारोह के लिए कोड इस तरह दिख सकता है:

bool less(point a, point b)
{
    if (a.x - center.x >= 0 && b.x - center.x < 0)
        return true;
    if (a.x - center.x < 0 && b.x - center.x >= 0)
        return false;
    if (a.x - center.x == 0 && b.x - center.x == 0) {
        if (a.y - center.y >= 0 || b.y - center.y >= 0)
            return a.y > b.y;
        return b.y > a.y;
    }

    // compute the cross product of vectors (center -> a) x (center -> b)
    int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;

    // points a and b are on the same line from the center
    // check which point is closer to the center
    int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    return d1 > d2;
}

यह 12 बजे से शुरू होने वाले बिंदुओं को क्रमशः क्रमबद्ध करेगा। उसी "घंटे" पर अंक केंद्र से आगे वाले लोगों से शुरू होने का आदेश दिया जाएगा।

यदि पूर्णांक प्रकारों का उपयोग करना (जो वास्तव में लुआ में मौजूद नहीं हैं) तो आपको यह सुनिश्चित करना होगा कि det, d1 और d2 चर एक प्रकार के हैं जो प्रदर्शन की गणना के परिणाम को पकड़ने में सक्षम होंगे।

यदि आप ठोस दिखने वाले कुछ को हासिल करना चाहते हैं, तो संभवतः उत्तल रूप में, तो मुझे लगता है कि आप एक उत्तल हॉल की तलाश में हैं । आप ग्राहम स्कैन का उपयोग करके इसकी गणना कर सकते हैं। इस एल्गोरिदम में, आपको विशेष पिवट बिंदु से शुरू होने वाले बिंदुओं को दक्षिणावर्त (या काउंटर-वार वार) को सॉर्ट करना होगा। फिर आप प्रत्येक बार यह जांचने के लिए सरल लूप चरणों को दोहराते हैं कि क्या आप उत्तल हॉल में नए बिंदु जोड़कर बाएं या दाएं मुड़ते हैं, यह चेक उपरोक्त तुलनात्मक फ़ंक्शन की तरह क्रॉस उत्पाद पर आधारित है।

संपादित करें:

अगर कथन if (ay - center.y >= 0 || by - center.y >=0) एक और जोड़ा गया है if (ay - center.y >= 0 || by - center.y >=0) यह सुनिश्चित करने के लिए कि x = 0 और नकारात्मक y वाले बिंदुओं को उन लोगों से शुरू किया गया है जो आगे से हैं केंद्र। यदि आपको उसी 'घंटे' पर अंक के आदेश की परवाह नहीं है तो आप इसे कथन के बिना छोड़ सकते हैं और हमेशा से ay > by वापस लौट सकते हैं।

पहली बार सुधार किया गया है अगर -center.x और -center.y जोड़ने के साथ बयान।

दूसरा अगर कथन जोड़ा गया (ax - center.x < 0 && bx - center.x >= 0) । यह एक स्पष्ट निरीक्षण था कि यह गायब था। यदि बयानों को अब पुनर्गठित किया जा सकता है क्योंकि कुछ चेक अनावश्यक हैं। उदाहरण के लिए, यदि पहली स्थिति में पहली स्थिति गलत है, तो दूसरी स्थिति की पहली स्थिति सत्य होने चाहिए। हालांकि, मैंने सादगी के लिए कोड छोड़ने का फैसला किया। यह काफी संभव है कि संकलक कोड को अनुकूलित करेगा और वैसे भी उसी परिणाम का उत्पादन करेगा।





computational-geometry