Veelhoekketting - Conversie naar niet-kruising met behoud van vorm?

Ik heb polygoonketens die lijken op de volgende ...

http: //upload.wikimedia .org/wikipedia/commons/thumb/6/62/Self_crossed_polygonal_chain.svg/220px-Self_crossed_polygonal_chain.svg.png

... gezien de ketting in de afbeelding, hoe zou ik gaan over het berekenen van een ketting die dezelfde vorm maar zonder kruisende paden definieert?

In het bijzonder, in het geval van de afbeelding, ziet het resultaat dat ik wil er zo uit:

A1,
A2,
Doorsnijden tussen A2 en A3,
Snijd tussen A3 en A4,
A4,
A5,
Snijd tussen A3 en A4,
A3,
Snijd tussen A3 en A2,
A6

Ik ben op zoek naar een algoritme om dit voor elke keten te bereiken, maar ik weet niet zeker wat ik probeer te doen is zelfs gebeld, wat het zoeken naar een oplossing lastig maakt.

Als er een naam is voor wat ik probeer te doen, zou het een grote hulp zijn om het te weten.

Bedankt voor alle hulp!

0
Dit kan in stackoverflow thuishoren - excuses als dit waar is.
toegevoegd de auteur Rudd-O, de bron

2 antwoord

Hoewel ik nog nooit heb gehoord dat uw exacte algoritme eerder is uitgevoerd, kan het algoritme voor de vegenlijn worden gebruikt om alle kruispunten snel te detecteren. (Zoals genoemd hier , bijvoorbeeld. )

1
toegevoegd

Er is veel onderzoek naar algoritmen voor dit probleem in de computationele geometrie, onder de naam "rangschikking van lijnsegmenten" (de lijnsegmenten zijn die in de polygonale keten en de rangschikking is de planaire grafiek die u krijgt wanneer u plaatst hoekpunten bij alle eindpunten en kruispunten).

In de praktijk is de suggestie van Jason Dyer om een ​​sweeplijn-algoritme te gebruiken een goede. In theorie zijn er betere algoritmen: voor $ n $ -lijnsegmenten met $ k $ -doorgangspunten geeft de sweeplijn u $ O ((n + k) \ log n) $, en sommige andere methoden leiden tot $ O ( n \ log n + k) $ draaitijden; zie b.v. Clarkson and Shor, Discrete Comput. Geom. 1989 .

Wanneer de lijnsegmenten zelf een verbonden niet-vlakke grafiek vormen (zoals in uw geval, waar ze een padgrafiek vormen) zijn zelfs snellere algoritmen mogelijk (hoogstens een geïtereerde logfactor weg van de lineaire tijd en lineair wanneer $ k $ niet te dichtbij is naar $ n $): zie mijn paper "Lineaire-tijdalgoritmen voor geometrische grafieken met vele onderkruisingen" en zijn referenties. Maar ik denk dat deze methoden te gecompliceerd zijn om praktisch bruikbaar te zijn.

1
toegevoegd