Znajdź kontur dwuwęzła niezorganizowanego 2D

Question

Mam zestaw punktów 2D, niezorganizowany, i chcę znaleźć "kontur" tego zestawu (nie wypukły kadłub). Nie mogę używać kształtów alfa, ponieważ mam cel prędkości (mniej niż 10 ms na przeciętnym komputerze). Moim pierwszym podejściem było obliczenie siatki i znalezienie obrysów kwadratów (kwadratów, które mają pusty kwadrat jako sąsiad). Myślę więc, że skutecznie zmniejszyłem liczbę punktów (z 22000 do 3000 mniej więcej). Ale wciąż muszę udoskonalić ten nowy zestaw.

Moje pytanie brzmi: w jaki sposób mogę znaleźć realne kontury punktów wśród moich zielonych punktów?

Answer 1

Po weekendzie pełnym refleksji, znalazłem wygodne rozwiązanie.

Potrzebujemy siatki, musimy ją wypełnić naszymi punktami, bez trudu.

Musimy zdecydować, które kwadraty są uważane za "Kontur". Nasze kryteria to: co najmniej jeden pusty sąsiad i co najmniej 3 niepustych sąsiadów.

Brakuje informacji o połączeniach. Więc wybieramy kwadrat "Kontur", który jako 2 "kontur" sąsiadów lub mniej. Następnie wybieramy jednego z sąsiadów. Od tego możemy rozpocząć ekspansję. Po prostu krąży wokół bieżącego kwadratu, aby znaleźć następny kwadrat "Kontur", znając poprzednie kwadraty "Konturu". Nasze kryteria konturu zapobiegają ślepemu zaułkowi.

Mamy teraz wektory połączonych kwadratów, i normalnie, jeśli nasz kształt nie ma dziury, tylko jeden wektor połączonych kwadratów!

Teraz dla każdego kwadratu musimy znaleźć najlepszy punkt dla konturu. Wybieramy ten, który znajduje się dalej od barycentrum naszego samolotu. Działa dla większości kształtów. Inną techniką jest obliczenie barycentrum pustych sąsiadów wybranego kwadratu i wybór najbliższego punktu.

czerwona punkty są kontur zielonym. Zastosowaną techniką jest płaska barycenter.

Dla zestawu 28 000 punktów techniki te trwają 8 ms. Formy alfa CGAL zajęłyby średnio 125 ms dla 28000 punktów.

PS: Mam nadzieję, że wyraziłem się jasno, angielski nie jest mój ojczysty: s

Answer 2

Naprawdę powinieneś używać kształtów alfa. Być może używaj tylko zielonych punktów jako danych wejściowych algorytmu alfa alfa.