Biorąc pod uwagę tablicę punktów x, y, jak posortować punkty tej tablicy w kolejności zgodnej z ruchem wskazówek zegara (wokół ich ogólnego średniego punktu środkowego)? Moim celem jest przekazanie punktów do funkcji tworzenia linii, tak aby otrzymać coś, co wygląda raczej na „solidne”, jak najbardziej wypukłe, bez przecinania się linii.
Co jest warte, używam Lua, ale każdy pseudokod byłby doceniony.
Aktualizacja: dla porównania, oto kod Lua oparty na doskonałej odpowiedzi Ciamej (zignoruj mój prefiks „aplikacja”):
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
ipairs(tbl)
która iteruje po indeksach i wartościach tbl od 1 do #tbl. Więc do obliczenia sumy, można to, co większość ludzi patrzy czystsze zrobić:for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y end
ipairs
jest znacznie wolniejsza niż numeryczna pętla for.Odpowiedzi:
Najpierw oblicz punkt środkowy. Następnie posortuj punkty za pomocą dowolnego algorytmu sortowania, ale użyj specjalnej procedury porównywania, aby określić, czy jeden punkt jest mniejszy od drugiego.
Możesz sprawdzić, czy jeden punkt (a) znajduje się na lewo czy na prawo od drugiego (b) w stosunku do środka, wykonując to proste obliczenie:
jeśli wynik wynosi zero, to znajdują się w tej samej linii od środka, jeśli jest dodatni lub ujemny, to jest po jednej lub drugiej stronie, więc jeden punkt będzie poprzedzał drugi. Używając go, możesz skonstruować relację mniej niż w celu porównania punktów i określenia kolejności, w jakiej powinny się pojawiać w posortowanej tablicy. Ale musisz zdefiniować, gdzie jest początek tego porządku, czyli jaki kąt będzie początkowy (np. Dodatnia połowa osi x).
Kod funkcji porównania może wyglądać następująco:
Spowoduje to uporządkowanie punktów zgodnie z ruchem wskazówek zegara, zaczynając od godziny 12. Punkty z tej samej „godziny” zostaną uporządkowane zaczynając od tych, które są dalej od centrum.
Jeśli używasz typów całkowitych (które tak naprawdę nie są obecne w Lua), musisz upewnić się, że zmienne det, d1 i d2 są typu, który będzie w stanie przechowywać wyniki przeprowadzonych obliczeń.
Jeśli chcesz uzyskać coś, co wygląda na solidne, tak wypukłe, jak to tylko możliwe, myślę, że szukasz wypukłego kadłuba . Możesz to obliczyć za pomocą programu Graham Scan . W tym algorytmie musisz także posortować punkty zgodnie z ruchem wskazówek zegara (lub przeciwnie do ruchu wskazówek zegara), zaczynając od specjalnego punktu obrotu. Następnie powtarzasz proste kroki pętli za każdym razem sprawdzając, czy skręcasz w lewo czy w prawo dodając nowe punkty do wypukłego kadłuba, to sprawdzenie opiera się na iloczynu krzyżowym, tak jak w powyższej funkcji porównania.
Edytować:
Dodano jeszcze jedną instrukcję if,
if (a.y - center.y >= 0 || b.y - center.y >=0)
aby upewnić się, że punkty, które mają x = 0 i ujemne y są sortowane, zaczynając od tych, które są dalej od środka. Jeśli nie zależy Ci na kolejności punktów w tej samej „godzinie” możesz pominąć to oświadczenie if i zawsze zwracaća.y > b.y
.Poprawiono pierwsze instrukcje if z dodaniem
-center.x
i-center.y
.Dodano drugą instrukcję if
(a.x - center.x < 0 && b.x - center.x >= 0)
. To było oczywiste przeoczenie, że go brakowało. Instrukcje if można teraz zreorganizować, ponieważ niektóre kontrole są zbędne. Na przykład, jeśli pierwszy warunek w pierwszej instrukcji if jest fałszywy, to pierwszy warunek drugiej instrukcji if musi być prawdziwy. Postanowiłem jednak pozostawić kod tak, jak jest dla uproszczenia. Jest całkiem możliwe, że kompilator zoptymalizuje kod i i tak da ten sam wynik.źródło
atan()
, bez pierwiastka kwadratowego, a nawet bez podziałów. To dobry przykład myślenia o grafice komputerowej. Usuń wszystkie łatwe przypadki tak szybko, jak to możliwe, a nawet w trudnych przypadkach obliczaj jak najmniej, aby znać wymaganą odpowiedź.Ciekawym alternatywnym podejściem do twojego problemu byłoby znalezienie przybliżonego minimum do problemu komiwojażera (TSP), tj. najkrótsza trasa łącząca wszystkie Twoje punkty. Jeśli twoje punkty tworzą wypukły kształt, powinno to być właściwe rozwiązanie, w przeciwnym razie powinno nadal dobrze wyglądać (kształt „pełny” można zdefiniować jako taki, który ma niski stosunek obwodu do powierzchni, co tutaj optymalizujemy) .
Możesz użyć dowolnej implementacji optymalizatora dla TSP, a jestem pewien, że znajdziesz ich mnóstwo w wybranym przez siebie języku.
źródło
To, o co prosisz, to układ znany jako współrzędne biegunowe . Konwersję ze współrzędnych kartezjańskich na biegunowe można łatwo przeprowadzić w dowolnym języku. Formuły można znaleźć w tej sekcji .
Po przeliczeniu na współrzędne biegunowe posortuj dane według kąta theta.
źródło
Inna wersja (zwraca prawdę, jeśli a występuje przed b w kierunku przeciwnym do ruchu wskazówek zegara):
Jest to szybsze, ponieważ kompilator (testowany na Visual C ++ 2015) nie generuje skoku do obliczeń dax, day, dbx, dby. Tutaj zestaw wyjściowy z kompilatora:
Cieszyć się.
źródło
Wreszcie otrzymujesz posortowane verts Anticlockwize
list.Reverse () .................. Clockwise_order
źródło