Zuerst weiß ich, dass eine ähnliche Frage bereits gestellt wurde, aber sie verwendet eine andere Struktur und ist in C (Selbst schneidendes Polygon teilen (C-Code)), meine Frage ist ein bisschen anders.
Ich habe Punkte des sich selbst schneidenden Polygons, seine Kanten und auch bin ich in der Lage, Punkte zu finden, wo es sich selbst mit dem Bentley-Ottmann-Algorithmus schneidet.
Ich plante, nicht selbst schneidende Polygone zu bauenWenn Sie zwei Kanten haben, die sich schneiden, wissen Sie nicht, welche zwei der vier Seiten innen liegen und welche außerhalb des Polygons liegen.
Ich könnte Ray-Crossing-Algorithmus zur Auflösung verwendendas ist aber zu langsam. Seine Zeitkomplexität ist O (n), und ich würde zwei tun es mindestens zwei Mal für jeden Schnittpunkt. So wäre es sehr langsam mit etwa 200.000 Punkte von Polygon.
Was ich also fragen möchte, ist, gibt es einen schnelleren Weg, sich selbst schneidende Polygon in nicht-selbst schneidende Polygon zu teilen.
Ich brauche das, weil ich Polygon macheTriangulation. Ich habe bereits einen Sweep-Line-Triangulationsalgorithmus zum Triangulieren von sich nicht selbst schneidenden Polygonen mit Löchern durchgeführt. Also brauche ich nur ein Array dieser Polygone als Eingabe.
Antworten:
1 für die Antwort № 1Als Vorverarbeitungsschritt können Sie berechnenjede Kante, welche Seite der Kante die Außenseite des Polygons bestimmt. Dies ist viel billiger als O (n) Zeit für jeden Schnittpunkt. Wenn sich dann zwei Kanten schneiden, können Sie bestimmen, welche zwei Liniensegmente außerhalb und welche zwei innen sind.