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.)
