Jak mogę sprawdzić, czy punkt leży w kształcie 3D z jego powierzchnią zdefiniowaną przez chmurę punktów?

Mam kolekcję punktów, które opisują powierzchnię kształtu, który powinien być z grubsza sferyczny, i potrzebuję metody, dzięki której można określić, czy jakikolwiek inny dany punkt leży w tym kształcie. Wcześniej przybliżałem kształt jako dokładną kulę, ale okazało się to zbyt niedokładne i potrzebuję dokładniejszej metody. Prostota i szybkość są korzystne w stosunku do całkowitej dokładności, wystarczy dobre przybliżenie.Jak mogę sprawdzić, czy punkt leży w kształcie 3D z jego powierzchnią zdefiniowaną przez chmurę punktów?

Natknąłem się na techniki konwersji chmury punktów na siatkę 3d, ale większość rzeczy, które znalazłem, były bardzo skomplikowane i szukam czegoś tak prostego, jak to tylko możliwe.

Wszelkie pomysły?

Źródło

2010-06-16 Ben

Czy chmura została naprawiona? Czy powierzchnia jest wypukła? Jak często trzeba wykonywać testy punktowe? –

Chmura nie jest ustalona "długookresowo", ale dla celów tych obliczeń jest tak, jak będą wykonywane na "migawkach" systemu. Nie trzeba uruchamiać w czasie rzeczywistym, jak w grze lub cokolwiek innego. Testy będą przeprowadzane mniej więcej raz na 2 sekundy. – Ben

Co, jeśli obliczysz środek ciężkości chmury i przekształcisz jej współrzędne na układ polarny, którego pochodzenie jest tym środkiem ciężkości.

Następnie przekonwertuj punkt, który chcesz zbadać, na ten sam układ współrzędnych.

Zakładając, że powierzchnia jest reprezentowana przez triangulację Delaunaya, określ trzy punkty o najmniejszej różnicy kąta od badanego punktu.

Wyświetl punkt, który badasz na trójkącie określonym przez te trzy punkty, i sprawdź, czy odległość rzutowanego punktu od środka ciężkości jest większa niż odległość rzeczywistego punktu.

Zasadniczo konstruujesz trójkątną siatkę wypukłego kadłuba, ale w razie potrzeby jeden trójkąt naraz. Jeśli szybkość wykonania naprawdę ma znaczenie, możesz buforować powstałe trójkąty.

Steven Sudit zasugerował także a useful optimization, który polecam, jeśli pójdziesz tą ścieżką.

Źródło

2010-06-16 14:42:26

To brzmi jak dobry pomysł, wielkie dzięki! Spróbuję teraz i zobaczę, czy to działa. Mam już listę sąsiednich punktów dla każdego punktu do optymalizacji innego algorytmu, który mógłbym ewentualnie poddać recyklingowi, aby to przyspieszyć. – Ben

Pomyślałem o tym trochę i podejrzewam, że trzy powinny zawsze wystarczyć. Opiera się to na założeniu, że powierzchnię można zdefiniować za pomocą trójkątów. Dopóki punkt znajduje się po stronie trójkątnej płaszczyzny, która znajduje się bliżej środka ciężkości, znajduje się w granicach. Oczywiście, jeśli to założenie jest błędne - jeśli mogą istnieć dziury i zwisy - to nic z tego nie ma. Z drugiej strony nie wiem, co robi; dodawanie kolejnych punktów samo w sobie nie wystarczy. –

W poprawnej terminologii zakładam, że jest to kadłub wypukły, definiowalny pod względem trójkątów Delaunaya. –

Myślę, że metoda Billa Careya jest na dobrej drodze, ale chcę zaproponować możliwą optymalizację.

Ponieważ kształt jest z grubsza sferyczny, można wstępnie obliczyć promień sfery przez nią związanej i sfery, która go ogranicza. W ten sposób, jeśli odległość punktu znajduje się w obrębie mniejszej sfery, jest to określone uderzenie i jeśli znajduje się poza zewnętrzną kulą, jest to zdecydowanie brak.

To powinno pozwolić ci szybko rozwiązać proste sprawy. Dla trudniejszych, metoda Careya przejmuje kontrolę.

Źródło

2010-06-16 14:53:55

To zdecydowanie dobra optymalizacja. Czy mogę dodać odesłaną referencję do mojej odpowiedzi? –

@ Bill, myślę, że właśnie zrobiłeś. :) –

@Bill: Zobacz link "link" w lewym dolnym rogu każdej odpowiedzi? Możesz użyć tego plusa albo znacznika albo html, aby "Zobacz optymalizację Steven'a". typ linku w twoim poście ... Tak zwykle zarządzam tymi rzeczami. – dmckee

Użyj drzewa kd.

http://en.wikipedia.org/wiki/Kd-tree

W artykule zapewnia dobre wyjaśnienie.

Mogę wyjaśnić wszelkie dalsze nieporozumienia.

Źródło

2010-06-16 14:58:15 bearrito

Drzewo kd odnosi się do części dotyczącej znalezienia najbliższych trzech punktów, chociaż brzmi to tak, jak Ben ma inne metody osiągnięcia tego. –

Czy można skonstruować drzewo kd w układzie współrzędnych biegunowych? Nie pracowałem z nimi wystarczająco dużo, aby wiedzieć. Jeśli tak, może być przydatna. –

@Bill: O ile mi wiadomo, kd-drzewa są dla współrzędnych kartezjańskich. Jeśli tak, zawsze możesz dokonać konwersji. Jeśli nie, to chciałbym zobaczyć, jak radzą sobie z problemem jednostek mieszanych (kątów i odległości). –

Jak mogę sprawdzić, czy punkt leży w kształcie 3D z jego powierzchnią zdefiniowaną przez chmurę punktów?

Odpowiedz

Powiązane problemy