Znajdowanie prostokąta wyrównanego do osi wewnątrz wielokąta

Question

Poszukuję dobrego algorytmu, aby znaleźć prostokąt wyrównany względem osi w (niekoniecznie wypukłym) wielokącie. Maksymalny prostokąt byłby miły, ale nie jest konieczny - jakikolwiek algorytm, który znajdzie "dość dobry" prostokąt, będzie w porządku.

Wielokąt może mieć również dziury, ale pomocne będą również dowolne wskazówki dotyczące algorytmów działających tylko w przypadku wypukłych lub prostych wielokątów.

W mojej implementacji testowanie skrzyżowań dla stron jest dość tanie, ale testy "point in polygon" są drogie, więc najlepiej należy je zminimalizować.

Answer 1

Dla porównania, jak dotąd wszystko, co mam, to brutalna siła: utworzyć siatkę, a dla punktów na siatce, jeśli znajdują się wewnątrz wielokąta, zrobić serię prostokątów, rozszerzając każdy róg lub bok po kolei, aż do momentu, w którym uderza w bok. Następnie wybierz największy.

Najprostszą (i bardzo skuteczną) optymalizacją jest jedynie sprawdzenie, czy punkt siatki znajduje się w wielokącie po sprawdzeniu, czy nie jest on zawarty w jednym z już zbudowanych prostokątów, ponieważ sprawdzanie "punktu w prostokącie" jest płonące szybki.

Z oczywistych względów, jest to dość powolne i niedokładne, nie wspominając nieeleganckie :)

Answer 2

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
Has algorytm wypukły, odniesienia może być warta obejrzenia.
nie jestem pewien, czy można go rozszerzyć na nie wypukły.

Answer 3

Jednym z rozwiązań jest podzielenie wklęsłego wielokąta na wypukłe segmenty, a następnie użycie linku cobbal.

Ponieważ naprawdę masz dwa różne podstawowe problemy, czy rozważałeś inne alternatywy dla problemu testu trafienia, na przykład używając drzewa BSP? Możesz przyspieszyć to jeszcze bardziej, układając siatkę ponad polem i budując drzewo BSP dla każdego kwadratu siatki. Lub drzewo kd z najwyżej jedną krawędzią w każdym liściu?

Edit: będę ellaborate na kd-drzewa (z nudów, nawet jeśli może to być dowolnego użytku dla nikogo):

kd-drzewa mają następujące właściwości:

1. Są one binarne
2. Każdy nie-liść węzłowy dzieli przestrzeń wzdłuż płaszczyzny prostopadłej do osi, z jednej strony na dziecko. Na przykład. root dzieli przestrzeń na x < x0 i x> = x0
3. Poziomy drzew z kolei dzielą się na różne osie, np. poziom 0 (root) dzieli prostopadle X, Poziom 1 -> Y, itd

Aby użyć tego wielokąta uderza detekcję skonstruować drzewo w następujący sposób:

1. Odbiór wierzchołek podzielić wzdłuż. (Leprably gdzieś blisko środka dla zrównoważonego drzewa).
2. Podziel pozostałe wierzchołki na dwa zestawy, po jednym dla każdej strony podziału. Powyższy wierzchołek nie przechodzi do żadnego z zestawów.
3. Umieść krawędzie w zestawach. Każda krawędź, która przecina linię podziału, przechodzi do obu zbiorów.
4. Skonstruuj dzieci rekurencyjnie z powyższych grup.

Jeśli podzielony wierzchołek zostanie wybrany odpowiednio, drzewo powinno mieć głębokość zbliżoną do log (N), gdzie N jest liczbą wierzchołków. Każdy węzeł liści będzie miał co najwyżej jedną krawędź przechodzącą przez niego. Aby wykryć trafienie:

1. Znajdź liść, w którym znajduje się punkt.
2. Jeśli w liściu jest krawędź, porównaj z nią punkt. Jeśli nie, powinno być oczywiste, czy punkt jest wewnątrz czy na zewnątrz (przechowuj tę informację w takich liściach podczas konstruowania drzewa).

Answer 4

A co z wykorzystaniem obcinania uszu? W każdym trójkącie można znaleźć prostokąt wyrównany do osi. Wtedy możesz spróbować dołączyć do trójkątów i przeliczyć swoje prostokąty.