X,y noktaları bir dizi verilen, nasıl, saat yönünde sırayla bu dizi (genel ortalama merkezi noktası civarında) puan sıralama? Amacım hattı oluşturma işlevi, bir puan bir şey değil, "katı" olarak dışbükey çizgiler kesişiyor. mümkün olduğunca bir görünümle sona geçmek.

Ne, Lua kullanıyorum, ama herhangi bir yalancı mutluluk duyacağız. Teşekkürler herhangi bir yardım için çok fazla!

Güncelleme:Başvuru için, bu Lua kodu Ciamej mükemmel cevap dayanmaktadır (benim Yoksay "uygulama" öneki):

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

İlk olarak Merkez noktasını hesaplamak. Sonra puan sıralama algoritması her tür gibi, ama özel bir karşılaştırma rutin bir noktadan diğerine göre daha az olup olmadığını belirlemek için kullanın.

Bir nokta (a) (b) Sol ya da olup olmadığını bu basit bir hesaplama ile: center ilgili olarak kontrol edebilirsiniz

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

eğer sonuç sıfır ise, o zaman onlar aynı satırda merkezine, eğer olumlu ya da olumsuz, o zaman bir tarafı ya da diğer bir nokta olur önce. Bunu kullanarak az-çok bir ilişki noktaları karşılaştırın ve sıralanmış dizideki göründükleri sırasını belirlemek için inşa edebilir. Ama bu emri başında nerede olduğunu tanımlamak gerekir, açı başlangıç (x-ekseninin pozitif yarısı gibi) ne olacak yani.

Karşılaştırma işlevi için kodu şöyle:

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;
}

Bu noktaları saat yönünde 12 saat itibaren sipariş olacaktır. Aynı puanla "saat" daha Merkezi'nden olanları itibaren sipariş edilebilir.

Eğer kullanarak tamsayı türleri (hangi değil gerçekten şimdiki Lua), daha iyi mi olurdu güvence altına det, d1 ve d2 değişkenleri bir tür olacak tutabilecek sonucu yapılan hesaplamalar.

Eğer sağlam bir şey, mümkün olduğunca dışbükey olarak elde etmek istiyorsanız, o zaman Convex Hull arıyorsunuz sanırım. Graham Scankullanarak hesaplayabilirsiniz. Bu algoritma aynı zamanda noktaları saat yönünde (ya da saat yönünün tersine) özel özet bir noktadan başlayarak Sırala. O zaman sana basit bir döngü adımları her zaman eğer sola dönerseniz veya dışbükey gövde için yeni noktalar ekleyerek, bu onay gibi karşılaştırıldığında, yukarıda çapraz ürün fonksiyonu dayalı doğru kontrolü tekrar.

Düzenleme:

Açıklama if (a.y - center.y >= 0 || b.y - center.y >=0) x=0 ve y negatif olduğu noktalar sıralanmış olduğundan emin olmak için daha fazla merkezden olanları itibaren eğer bir tane daha eklendi. Eğer aynı 'saat' bu ifade ihmal ve her zaman a.y > b.y dönebilirsiniz. puan sırası umurunda eğer.

-center.x -center.y ekleme if ilk düzeltildi.

İkinci if ifadesi eklendi 10**. Eksik olduğunu bariz bir yanlışlık. İfadeler eğer bazı kontroller gereksiz çünkü şimdi yeniden olabilir. Eğer ilk deyimi ilk koşul yanlış ise, örneğin, daha sonra ikinci ilk koşul doğru olması gerekir. Ancak, basitlik için olduğu gibi kod ayrılmaya karar verdim. Derleyici kodu optimize etmek ve aynı sonucu verir zaten olması kuvvetle muhtemel.