Zamawianie zestawu niezorganizowanych punktów wzdłuż krzywej

Mam zestaw punktów 3D (które odzyskuję z biblioteki wykonującej teselację bryły), które należą do krzywej (tj. Krawędzi bryły). Oznacza to, że krzywa z pewnością przechodzi przez każdy z tych punktów.

Niemniej jednak zestaw punktów jest nieuporządkowany, więc muszę je posortować, aby poprawnie narysować tę krzywą.

Czy jest jakieś znane podejście do tego rodzaju problemów?

Niektóre dodatkowe informacje:

Krzywe są ogólnie parametryczne (splajny / Beziera, wycinki kół ...).
Punkty podane są jako współrzędne zmiennoprzecinkowe.
Punkty są bardzo gęsto upakowane (ale mogą być tak gęste, jak chcę). Aby dać ci pomysł, dla krzywej, która zajmuje 19 jednostek x, 10 jednostek x i 5 jednostek z, cytuję sekwencję punktów w odcinku krzywej: (20.7622, 25.8676, 0) (20.6573, 25.856, 0) (20.5529, 25.8444, 0) (20.4489, 25.8329, 0) (20.3454, 25,8213, 0)

geometry mesh curve

— andrea.al
źródło

Nawet jeśli znamy kolejność aż do nieskończonej liczby krzywych, które pasują przez punkty. Nawet jeśli dodamy dodatkowe ograniczenia, wówczas otwarte końce są problematyczne, ponieważ ich orientacja styczna może być dowolna. Obraz tutaj

— joojaa

@joojaa Tak, masz rację. Ale ponieważ upakowanie punktów jest bardzo gęste, nie oczekuję, że będzie dokładne. Jeśli uda mi się uzyskać odpowiednią kolejność, planowałem połączyć sekwencję punktów jako polilinię.

— andrea.al

Czy w kodzie, który musi uporządkować punkty, zdajesz sobie sprawę z parametrycznej postaci krzywej? (Jeśli nie, usunę moją pierwszą odpowiedź, ponieważ wymaga znajomości formularza parametrycznego.)

— Martin Ender

@ MartinBüttner Tak, w razie potrzeby mam dostęp do parametrycznej postaci krzywej.

— andrea.al

Pokaż typowy zestaw punktów!

— Yves Daoust

Odpowiedzi:

Wystąpił przykład problemu zwanego rekonstrukcją krzywej z niezorganizowanych punktów . Teraz, gdy wiesz, czego szukać, znajdziesz kilka metod, takich jak skorupa, skorupa NN itp. Oto kilka linków:

Aplet odbudowy krzywej skorupy ziemskiej
Rekonstrukcja krzywej Tamal Dey
Rekonstrukcja krzywych i powierzchni: algorytmy z analizą matematyczną , książka Tamal K. Dey, Cambridge University Press, 2006

Ponieważ masz do czynienia z krzywymi, a próbki są gęste, proponuję obliczyć euklidesowe minimalne drzewo rozpinające.

— lhf
źródło

Po kilku wyjaśnieniach istnieje prawdopodobnie znacznie lepsze podejście, które nawet nie wymaga znajomości parametrycznej postaci krzywej, a także pozwala uniknąć potencjalnie problematycznego kroku numerycznej minimalizacji.

Jeśli krzywa nie przecina się, a punkty są wystarczająco gęsto upakowane na krzywej (a przez to rozumiem, że muszą być bliżej niż dwa dowolne punkty na krzywej, które nie należą do tego samego segmentu, np. Przez zawijanie krzywej wokół siebie), możesz łatwo określić poprzedni i następny punkt dla każdej próbki:

Określ dwóch najbliższych sąsiadów w każdym punkcie. To jest $O(n \log n)$ operacja .
Będziesz musiał wykonać specjalne leczenie punktów końcowych. Ich dwaj najbliżsi sąsiedzi będą następnymi dwoma punktami wzdłuż krzywej zamiast jednego z każdej strony. Możesz je wykryć heurystycznie, jeśli stosunek odległości do dwóch sąsiadów różni się o więcej niż pewien próg (1,5 powiedzmy, zależy od gładkości twojej krzywej i tego, jak gęsto upakowane są punkty). Lub możesz traktować dane najbliższego sąsiada jak wykres, na którym zobaczysz, że dwaj sąsiedzi punktów końcowych wskazują na siebie (co nie powinno się zdarzyć nigdzie indziej na wykresie).
Teraz możesz po prostu wybrać jeden punkt końcowy i przejść wzdłuż najbliższych sąsiadów (zawsze wybierając ten, z którego nie przybyłeś), aby przejść przez punkty wzdłuż krzywej.

Zwłaszcza jeśli możesz sprawić, że punkty będą bardzo gęste, powinna to być najbardziej niezawodna opcja, chyba że krzywa się przecina. Nawet w takim przypadku podejście to może być możliwe do odzyskania, pod warunkiem że samo przecięcie jest pod wystarczająco dużym kątem, a krzywa jest wystarczająco gładka (w takim przypadku można wybrać właściwych sąsiadów na podstawie pewnego ograniczenia, że kolejne kroki nie mogą spowodować, że kąt będzie większy niż pewien próg $\theta$ ).

— Martin Ender
źródło

Ponieważ masz tylko reprezentacje zmiennoprzecinkowe punktów, nie ma gwarancji, że nadal leżą one dokładnie na krzywej z powodu błędów zaokrąglania. Myślę więc, że jedynym ogólnym podejściem jest przybliżenie, gdzie były na krzywej, poprzez znalezienie najbliższego punktu na krzywej dla twojej próbki $(X,Y,Z)$ . Np. Jeśli twoja krzywa parametryczna to $(x(t), y(t), z(t))$ wtedy możesz spróbować zminimalizować

(X - x (t))^{2)} + (Y - y (t))^{2)} + (Z - z (t))^{2)}

$(X-x(t))^2+(Y-y(t))^2+(Z-z(t))^2$

z szacunkiem do $t$ . Jeśli wiesz, z jakim rodzajem krzywej masz do czynienia, mogą być fajne rozwiązania analityczne, w przeciwnym razie będziesz musiał skorzystać z jakiegoś algorytmu numerycznego. Ponieważ punkty powinny znajdować się bardzo blisko krzywej, ta metoda powinna być niezawodna (pod warunkiem, że algorytm minimalizacji), chyba że masz próbkę dokładnie tam, gdzie krzywa (prawie) przecina się sama. W takim razie i tak prawdopodobnie nie masz szczęścia.

Kiedy już to masz $t$ dla każdego z punktów możesz je po prostu posortować $t$ . Oczywiście, jeśli masz kontrolę nad sposobem otrzymywania punktów, możesz być w stanie ominąć wszystkie te problemy, powracając $t$ wraz ze współrzędnymi punktu od razu podczas ich generowania.

— Martin Ender
źródło