Pomiar prostoliniowości segmentu krzywej (reprezentowanej jako polilinia)

Pracuję nad automatycznym algorytmem etykietowania konturów elewacji i jednym z czynników, które chcę wziąć pod uwagę przy ustalaniu pozycji etykiet, jest to, jak „prosty” jest konkretny segment konturu. Im bardziej jest prosty, tym bardziej prawdopodobne jest, że zostanie użyty do umieszczenia etykiety w tym segmencie.

Każdy kontur jest reprezentowany przez polilinię (ale z punktami blisko siebie, które wyglądają jak krzywa gołym okiem). Mam wtedy stałą długość (szerokość etykiety), powiedzmy 100 pikseli. Jeśli losowo (lub inaczej) wybiorę segment konturu o szerokości 100 pikseli, chcę być w stanie uzyskać liczbową wartość liczbową jego prostoliniowości (powiedz zero dla całkowicie prostego segmentu konturu, pewna wartość większa od zera dla nie tak prosty odcinek, a wartość ta rośnie wraz ze wzrostem krzywizny).

Szukałem odpowiedzi, ale nie znalazłem nic naprawdę przydatnego. Byłbym wdzięczny za wszelkie wskazówki.

Odpowiedź zależy od kontekstu : jeśli będziesz badał tylko niewielką (ograniczoną) liczbę segmentów, być może będziesz mógł sobie pozwolić na drogie obliczeniowo rozwiązanie. Wydaje się jednak prawdopodobne, że będziesz chciał uwzględnić te obliczenia w pewnego rodzaju poszukiwaniu dobrych punktów na etykiecie. Jeśli tak, to wielką zaletą jest posiadanie rozwiązania, które albo jest szybkie obliczeniowo, albo pozwala na szybką aktualizację rozwiązania, gdy segment linii kandydującej jest nieco zróżnicowany.

Załóżmy na przykład, że zamierzasz przeprowadzać systematyczne wyszukiwaniew poprzek całego połączonego komponentu konturu, reprezentowanego jako ciąg punktów P (0), P (1), ..., P (n). Odbyłoby się to poprzez zainicjowanie jednego wskaźnika (indeksu w sekwencji) s = 0 („s” dla „startu”), a drugiego wskaźnika f (dla „zakończenia”), aby był najmniejszym indeksem dla którego odległości (P (f), P (s))> = 100, a następnie przesuwając s tak długo, jak odległość (P (f), P (s + 1))>> 100. To daje kandydującą polilinię (P (s), P (s +) 1) ..., P (f-1), P (f)) do oceny. Po dokonaniu oceny jego „zdolności” do obsługi etykiety, należy następnie zwiększyć o 1 (s = s + 1) i przejść do zwiększenia f do (powiedzmy) f 'i s do s', aż ponownie kandydująca polilinia przekroczy minimum wytwarzana jest rozpiętość 100, reprezentowana jako (P (s '), ... P (f), P (f + 1), ..., P (f')). W ten sposób wierzchołki P (s) ... P (s ') Jest wysoce pożądane, aby sprawność mogła być szybko aktualizowana na podstawie wiedzy tylko o upuszczonych i dodanych wierzchołkach. (Ta procedura skanowania będzie kontynuowana, aż s = n; jak zwykle, f musi mieć możliwość „zawinięcia” od n z powrotem do 0).

Ta uwaga wyklucza wiele możliwych mierników kondycji ( zwinność , krętość itp.) , Które w innym przypadku mogłyby być atrakcyjne. Prowadzi nas to do faworyzowania miar opartych na L2 , ponieważ zazwyczaj można je szybko zaktualizować, gdy podstawowe dane nieznacznie się zmienią. Biorąc analogię z analizy głównych składowych proponuje się następujący środek rozpoznania (gdzie małe jest lepsze, ponieważ wymagane): stosować mniejszą z dwóch wartości własnych w macierzy kowariancjiwspółrzędnych punktu. Geometrycznie jest to jedna miara „typowego” odchylenia na boki wierzchołków w części kandydackiej polilinii. (Jedna interpretacja jest taka, że ​​jej pierwiastek kwadratowy jest mniejszą półosią elipsy reprezentującą drugie momenty bezwładności wierzchołków polilinii.) Będzie ona równa zero tylko dla zbiorów wierzchołków współliniowych; w przeciwnym razie przekracza zero. Mierzy średnie odchylenie z boku na bok w stosunku do linii bazowej 100 pikseli utworzonej przez początek i koniec polilinii, a zatem ma prostą interpretację.

Ponieważ macierz kowariancji wynosi tylko 2 na 2, wartości własne można szybko znaleźć, rozwiązując pojedyncze równanie kwadratowe. Co więcej, macierz kowariancji jest sumą wkładów z każdego z wierzchołków polilinii. Tak więc jest on szybko aktualizowany, gdy punkty są usuwane lub dodawane, co prowadzi do algorytmu O (n) dla konturu n-punktowego: będzie dobrze skalowane do bardzo szczegółowych konturów przewidzianych w aplikacji.

Oto przykład wyniku tego algorytmu. Czarne kropki są wierzchołkami konturu. Ciągła czerwona linia jest najlepszym kandydującym segmentem polilinii o długości od końca do końca większej niż 100 w obrębie tego konturu. (Widoczny wizualnie kandydat w prawym górnym rogu nie jest wystarczająco długi.)

W społeczności grafików komputerowych często konieczne jest znalezienie obwiedni wokół obiektu. W związku z tym jest to dobrze zbadany problem z szybkimi algorytmami. Np. Zobacz artykuł dotyczący minimalnych algorytmów ramki ograniczającej w Wikipedii . Możesz znaleźć prostokąt o minimalnym obszarze otaczającym polilinię, a następnie użyć proporcji, wysokości / długości prostokąta. Aby uzyskać dokładniejszą miarę, możesz spojrzeć na odchylenie polilinii od linii środkowej tego prostokąta ograniczającego.

Nie wiem, czy to pomaga, czy nawet liczy się jako odpowiedź, ale kiedy siedziałem tutaj i myślałem o właśnie zadanym pytaniu, pomyślałem:

Co jeśli umieścisz okrąg o określonym promieniu na linii konturu. Ten okrąg przecina linię konturu w co najmniej dwóch miejscach. Im linia jest prostsza, tym krótsza jest odległość wzdłuż linii konturu między dwoma punktami przecięcia. Im większa odległość wzdłuż linii konturu między punktami przecięcia, tym bardziej zakrzywiona jest linia. Jeśli są więcej niż dwa punkty przecięcia, linia konturu jest zbyt zakrzywiona.

Możesz dowiedzieć się, jaka długość da najlepszy wskaźnik prostoliniowości, i ustawić procedurę, aby kroczyć wzdłuż każdej linii konturu i tam, gdzie była wystarczająco prosta, umieść etykietę.

Jestem pewien, że to nie pomaga zbytnio, a to, co mówię po angielsku, jest o wiele trudniejsze w jakimkolwiek języku programowania, którego używasz, ale może to być początek?

Najłatwiejsze podejście, jakie mogę wymyślić, to stosunek rzeczywistej długości ścieżki między początkiem a końcem do najkrótszej odległości (linii prostej) od początku do punktu końcowego. Linie proste będą miały stosunki zbliżone do jednego, podczas gdy linie bardzo zakrzywione będą miały bardzo wysoki stosunek.

To powinno być naprawdę łatwe do wdrożenia rozwiązanie.

Aktualizacja: Jak Mike zauważył poprawnie, będzie to równe Sinuosity .

Szukając „krzywizny” i „polilinii”, otrzymałem te informacje. Jak znaleźć krzywiznę polilinii? . Tam zasugerował użycie powrotu do definicji krzywizny - K= DF/Ds. Tutaj przez Fniego phi, lub Tw notacji wikipedia tutaj ( http://en.wikipedia.org/wiki/Curvature ).

Powiedzmy, że masz sekwencję trzy punkty, p0, p1 i p2. obliczyć odległość smiędzy p0 i p1, która jest deltą s ( Ds), zakładając, że punkty są wystarczająco blisko siebie. Następnie potrzebujesz delty T ( DT), która jest zmianą wektora stycznego w jednostce między p0 i p1. może być wyrafinowany sposób, ale prymitywną metodą, o której mogę myśleć, jest wzięcie dwóch wektorów p0-> p1, p1-> p2, znormalizowanie każdego z nich do długości jednego, a następnie odjęcie wektora tych dwóch, a następnie określenie wielkości. Że jest DT. Podział daje krzywiznę K0_1. złap p1, p2 i p3, aby obliczyć K1_2i tak dalej.

Zastanawiam się jednak, czy obrysujesz kontur jako polilinię, a nie jako renderowane piksele. Powiedziałeś 100 pikseli, więc trochę się martwię.