Grootste cirkel binnen een niet-convexe veelhoek

Hoe vind ik de grootste cirkel die in een concave veelhoek past?

Een brute force-algoritme is oké, zolang het polygonen met ~50 hoekpunten in realtime aankan.

Antwoord 1, autoriteit 100%

De sleutel tot het oplossen van dit probleem is eerst een observatie maken: het middelpunt van de grootste cirkel die in een willekeurige veelhoek past, is het punt dat is:

1. Binnen de veelhoek; en
2. Het verst verwijderd van elk punt aan de randen van de veelhoek.

Waarom? Omdat elk punt op de rand van een cirkel op gelijke afstand van dat middelpunt ligt. De grootste cirkel heeft per definitie de grootste straal en raakt de veelhoek op ten minste twee punten, dus als je het punt binnenin het verst van de veelhoek vindt, heb je het middelpunt van de cirkel gevonden.

Dit probleem komt voor in de geografie en wordt iteratief opgelost met elke willekeurige precisie. Het wordt het ‘Poles of Inaccessibility’-probleem genoemd. Zie Polen van ontoegankelijkheid: een rekenalgoritme voor de meest afgelegen plekken op aarde.

Het basisalgoritme werkt als volgt:

1. Definieer R als een rechtlijnig gebied van (x_min,y_min) tot (x_max,y_max);
2. Verdeel R in een willekeurig aantal punten. Het papier gebruikt 21 als een heuristiek (wat betekent dat de hoogte en breedte door 20 worden gedeeld);
3. Alle punten wegknippen die buiten de polygoon liggen;
4. Zoek voor de rest het punt dat het verst verwijderd is van een willekeurig punt op de rand;
5. Definieer vanaf dat punt een nieuwe R met kleinere intervallen en grenzen en herhaal vanaf stap 2 om een ​​willekeurig nauwkeurig antwoord te krijgen. Het papier reduceert R met een factor van de vierkantswortel van 2.

Eén opmerking, hoe te testen of een punt binnen de polygoon ligt of niet: De eenvoudigste oplossing voor dit deel van het probleem is om een ​​straal rechts van het punt te werpen. Als het een oneven aantal randen kruist, bevindt het zich binnen de veelhoek. Als het een even getal is, staat het buiten.

Voor zover u de afstand tot een rand wilt testen, moet u ook rekening houden met twee zaken:

1. Het punt staat loodrecht op een punt op die rand (binnen de grenzen van de twee hoekpunten); of
2. Dat is het niet.

(2) is eenvoudig. De afstand tot de rand is het minimum van de afstanden tot de twee hoekpunten. Voor (1) is het dichtstbijzijnde punt op die rand het punt dat de rand snijdt in een hoek van 90 graden vanaf het punt dat u aan het testen bent. Zie Afstand van een punt tot een straal of segment.

Antwoord 2, autoriteit 53%

Voor het geval iemand op zoek is naar een praktische implementatie, ik heb een sneller algoritme ontworpen dat dit probleem met een bepaalde precisie oplost en er een JavaScript-bibliotheek van gemaakt. Het is vergelijkbaar met het iteratieve rasteralgoritme beschreven door @cletus, maar het levert gegarandeerd een globaal optimum op en is in de praktijk ook 20-40 keer sneller.

Bekijk het: https://github.com/mapbox/polylabel

Antwoord 3, autoriteit 33%

Een O(n log(n))-algoritme:

1. Maak het Voronoi-diagramvan de randen in P. Dit kan bijvoorbeeld met , Fortunes-algoritme.
2. Voor Voronoi-knooppunten (punten op gelijke afstand van drie of meer randen) binnen P;
3. Zoek het knooppunt met de maximale afstand tot randen in P. Dit knooppunt is het middelpunt van de maximale ingeschreven cirkel.

Antwoord 4, autoriteit 29%

Samenvatting: In theorie kan dit in O(n) tijd. In de praktijk kun je het in O(n log n) tijd doen.

Gegeneraliseerde Voronoi-diagrammen.

Als je de hoekpunten en randen van de polygoon als een reeks locaties beschouwt en het interieur in de “dichtstbijzijnde buurcellen” plaatst, krijg je het zogenaamde (gegeneraliseerde) Voronoi-diagram. Het Voronoi-diagram bestaat uit knopen en randen die ze met elkaar verbinden. De spelingvan een knoop is de afstand tot de bepalende polygoonvlakken.

(Hier heeft de polygoon zelfs gaten; het principe werkt nog steeds.)

De belangrijkste observatie is nu dat het middelpunt van de maximaal ingeschreven cirkel drie vlakken (hoekpunten of randen) van de veelhoek raakt, en geen enkel ander vlak kan dichterbij zijn. Het centrum moet dus op een Voronoi-knooppunt liggen, d.w.z. het knooppunt met de grootste speling.

In het bovenstaande voorbeeld raakt het knooppunt dat het middelpunt van de maximale ingeschreven cirkel markeert, twee randen en een hoekpunt van de veelhoek.

De mediale as is trouwens het Voronoi-diagram met die Voronoi-randen verwijderd die afkomstig zijn van reflexhoekpunten. Het middelpunt van de maximale ingeschreven cirkel ligt dus ook op de mediale as.

Bron: een blogartikelvan mij dat behandelt generalisaties van maximale ingeschreven cirkels op een bepaald punt. Daar kun je meer vinden over Voronoi-diagrammen en hun relatie tot maximaal ingeschreven cirkels.

Algoritmen & implementaties.

Je zou het Voronoi-diagram kunnen berekenen. Een worst-case O(n log n)-algoritme voor punten en segmenten wordt gegeven door Fortune, A sweepline-algoritme voor Voronoi-diagrammen, SoCG’86. Held publiceerde het softwarepakket Vronimet een verwachte O (n log n) tijdcomplexiteit, die ook daadwerkelijk de maximale ingeschreven cirkel berekent. En er lijkt een implementatie te zijn in boost, ook.

Voor eenvoudige polygonen (dwz zonder gaten) is een tijdoptimaal algoritme dat in O(n)-tijd draait, te danken aan Chin et al., De mediale as van een eenvoudige veelhoek vinden in lineaire tijd, 1999.

Brute kracht.

Echter, zoals je zei dat je prima kunt werken met een brute-force-algoritme: hoe zit het met het simpelweg uitproberen van alle drietallen sites (hoekpunten en randen). Voor elk triplet vind je kandidaat Voronoi-knooppunten, d.w.z. loci op gelijke afstand van de drie locaties, en controleer of een andere locatie de maximale ingeschreven cirkel van de kandidaat zou kruisen. Als er een kruising is, ontslaat u de kandidaat. Neem het beste dat je kunt vinden over alle drielingen.

Zie hoofdstuk 3 in mijn Masterproefvoor meer details over informatica equidistante loci voor drie locaties.

Antwoord 5, autoriteit 2%

Ik heb rechte skeletten gebruikt om een ​​afbeelding in een veelhoek met drie stappen te plaatsen:

1. Zoek het rechte skelet met behulp van het Straight Skeleton-algoritme (foto 1)
2. Ga op het rechte skelet uit, zoek de grootste cirkel (foto 2)
3. Teken de afbeelding binnen die cirkel (foto 3)

Probeer het op: https://smartdiagram.com/simple-infographics- 3d-charts-2/

Antwoord 6

Een O(n log X) algoritme, waarbij X afhankelijk is van de gewenste precisie.

Binair zoeken naar grootste straal R voor een cirkel:

Duw bij elke iteratie, voor een gegeven straal r, elke rand E, “naar binnen” door R, om E’ te krijgen. Definieer voor elke rand E’ halfvlak H als de verzameling van alle punten “binnen” de veelhoek (gebruik E’ als grens). Bereken nu het snijpunt van al deze halve vlakken E’, wat in O(n) tijd kan. Als het snijpunt niet leeg is en je een cirkel tekent met straal r en een willekeurig punt in het snijpunt als middelpunt gebruikt, zal het binnen de gegeven veelhoek vallen.