Jaki jest najszybszy sposób na znalezienie "wizualnego" środka wielokąta o nieregularnym kształcie?

Question

Potrzebuję znaleźć punkt, który jest wizualnym środkiem wielokąta o nieregularnym kształcie. Przez centrum wizualne rozumiem punkt, który wydaje się być w centrum dużego obszaru wielokąta wizualnie. Aplikacja polega na umieszczeniu etykiety wewnątrz wielokąta.

Oto rozwiązanie, które wykorzystuje wewnątrz buforowania:

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

Jeśli to ma być stosowane, co stanowi skuteczny i szybki sposób znaleźć bufor? Jeśli w jakikolwiek inny sposób należy użyć, to w ten sposób?

Dobrym przykładem naprawdę trudnych wielokątów jest gigantyczne grube U (napisane w Arial Black lub Impact lub jakiejś takiej czcionce).

Answer 1

Jeśli można konwertować wielokąt w obrazie binarnym, wówczas można użyć fundament, który istnieje w dziedzinie przetwarzania obrazu, np .: A Fast Skeleton Algorithm on Block Represented Binary Images.

Jednak w ogólnym przypadku nie jest to uzasadnione z powodu błędów dyskretyzacji i dodatkowej pracy.

Jednakże, może znaleźć te przydatne:

• Straight skeleton of a simple polygon
• Determining the Skeleton of a Simple Polygon in (Almost) Linear Time

EDIT: Może chcesz szukać punktu, który jest w centrum największego koła zawarte w wielokąt. Niekoniecznie jest to zawsze w obserwowanym ośrodku, ale przez większość czasu zapewne dawałby oczekiwany rezultat, a tylko w nieznacznie patologicznych przypadkach coś, co jest całkowicie wyłączone.

Answer 2

Ten problem prawdopodobnie byłby analogiczny do znalezienia "środka masy" przy założeniu jednolitej gęstości.

Edycja: Metoda ta nie będzie działać, gdy wielokąt „dziury”

Answer 3

obliczyć położenie punktu (x, y) każdej krawędzi wielokąta. Możesz to zrobić, znajdując różnicę między pozycjami na końcach każdej krawędzi. Weź średnią każdego centrum w każdym wymiarze. To będzie środek wielokąta.

Answer 4

Myślę, że jeśli zjednoczysz wielokąt z powrotem w jego wierzchołki, a następnie zastosujesz funkcję, by znaleźć największy wypukły kadłub, a następnie znajdziesz środek od tego wypukłego kadłuba, będzie on ściśle pasował do "pozornego" środka.

Znalezienie największej wypukłej daną wierzchołki: Look under the Simple Polygon paragraph.

Średnia wierzchołkami wypukłych kadłuba, aby znaleźć centrum.

Answer 5

Jeśli rozumiem punkt papieru, z którym się łączyłeś (dość interesujący problem, btw), ta technika "wewnętrznego buforowania" jest nieco analogiczna do modelowania danego kształtu z kawałka cukru, który jest rozpuszczany przez kwas od krawędzi w. (np. gdy odległość bufora wzrasta, pozostaje mniej oryginalnego kształtu) Ostatni pozostały bit jest idealnym miejscem do umieszczenia etykiety.

Jak tego dokonać w algorytmie niestety nie jest dla mnie bardzo jasne ....

Answer 6

można umieścić etykietę w naiwnej centrum (od obwiedni, być może), a następnie przenieść go na podstawie na przecięciach lokalnych krawędzi wielokątów i BB etykiety? Poruszaj się wzdłuż normalnych przecinających się krawędzi, a jeśli wiele krawędzi przecinają się, sumuj ich normalne ruchy?

Po prostu zgaduję; w tego rodzaju problemie prawdopodobnie próbowałbym rozwiązać iteracyjnie, o ile wydajność nie jest zbyt wielkim problemem.

Answer 7

Czy przyjrzałeś się użyciu formuły centroidów?

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

Answer 8

Co powiesz na znalezienie "incircle" wielokąta (największego koła, które mieści się w nim), a następnie wyśrodkowanie etykiety w centrum tego? Oto kilka linków, aby zacząć:

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

To nie będzie działać idealnie na każdym wielokąta, najprawdopodobniej; wielobok, który wyglądałby jak C, miałby etykietę w nieco nieprzewidywalnym miejscu. Ale zaletą byłoby to, że etykieta zawsze nakładałaby się na stałą część wielokąta.

Answer 9

Nie mam zbyt wiele czasu, aby to teraz opracować lub przetestować, ale postaram się zrobić więcej, gdy dostanę szansę.

Użyj centroidów jako podstawowej metody. Sprawdź, czy środek ciężkości znajduje się w wielokącie; jeśli nie, narysuj linię od najbliższego punktu i na drugą stronę wielokąta. W środkowej części sekcji linii znajdującej się w wielokącie umieść etykietę.

Ponieważ punkt znajdujący się najbliżej środka ciężkości prawdopodobnie będzie związany z dość obszernym obszarem, myślę, że może to dać wyniki podobne do incircles Kyralessy. Oczywiście może to zabrzmieć w szał, jeśli masz wielokąt z dziurami. W takim przypadku incircles byłoby prawdopodobnie znacznie lepsze. Z drugiej strony domyślnie stosuje się do (typowej) centroidy dla typowych przypadków.

Answer 10

Nie mówię, że to jest najszybszy, ale da ci punkt wewnątrz wielokąta. Oblicz wartość Straight Skeleton. Punkt, którego szukasz, znajduje się na tym szkielecie. Możesz wybrać na przykład ten z najkrótszą normalną odległością do środka obwiedni.

Answer 11

Metoda centroidowa została już zasugerowana wiele razy. Myślę, że jest to doskonały zasób, który opisuje proces (i wiele innych przydatnych sztuczek z wielokątów) bardzo intuicyjnie:

http://paulbourke.net/geometry/polygonmesh/centroid.pdf

Ponadto, za wprowadzanie prostą etykietę UI, może być wystarczające, aby po prostu obliczyć obwiedni pole wielokąta (prostokątny określone przez najniższy i najwyższy współrzędnych x i y w każdym wierzchołku wielokąta) i uzyskanie środek w:

{ 
    x = min_x + (max_x - min_x)/2, 
    y = min_y + (max_y - min_y)/2 
} 

jest nieco szybciej niż obliczanie środka ciężkości, co mogłoby mieć znaczenie dla aplikacji wbudowanej lub osadzonej w czasie rzeczywistym.

Należy również zauważyć, że jeśli wielokąty są statyczne (nie zmieniają formy), można zoptymalizować, zapisując wynik centrowania środka BB/środka masy (względem np. Pierwszego wierzchołka wielokąta), aby struktura danych wieloboku.

Answer 12

można użyć środka masy (lub środek ciężkości) metodę, która jest stosowana w inżynierii lądowej, tu jest bardzo przydatny link z wikipedii:

http://en.wikipedia.org/wiki/Center_of_mass

Answer 13

Jak o:

Jeśli środek wieloboku znajduje się wewnątrz wielokątu, a następnie użyj go: w innym przypadku:

1) Wydłuż linię od środka ciężkości przez wielokąt dzieląc wielokąt na dwie połówki równego obszaru

2) „Centrum wizualne” to punkt w połowie drogi między najbliższego punktu, gdzie linia dotyka obwodu i następny punkt cięcia obwodu w kierunku odchodzi od ciężkości

Oto kilka zdjęć aby go zilustrować:

Answer 14

znalazłem bardzo dobre rozwiązanie do tego z MapBox nazywa Polylabel. Pełne źródło jest dostępne również w ich wersji Github.

Zasadniczo próbuje znaleźć wizualne centrum wielokąta, jak powiedział T Austin.

Niektóre dane wskazują, może to być rozwiązanie praktyczne:

Niestety, obliczanie [idealne rozwiązanie] jest bardzo złożony i powolne. Opublikowane rozwiązania tego problemu wymagają albo 01/Ograniczonej triangulacji Delaunay, albo obliczenia prostego szkieletu jako kroków wstępnego przetwarzania - oba są powolne i podatne na błędy.

Dla naszego przypadku użycia nie potrzebujemy dokładnego rozwiązania - chcemy, aby wymieniał pewną precyzję, aby uzyskać większą szybkość. Kiedy umieszczamy etykietę na mapie, ważniejsze jest, aby była obliczona w milisekundach niż , aby była matematycznie doskonała.

Krótka informacja o użyciu. Kod źródłowy działa świetnie dla JavaScript wyjęciu z pudełka jednak jeśli masz zamiar na temat korzystania z tego z „normalnym” wielokąta następnie należy owinąć ją w pustej tablicy jak funkcjonuje tu wziąć GeoJSONPolygons zamiast normalnych wielokątów tj

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]]; 
var center = polylabel([myPolygon]);