Gegeben zwei einfache Polygone P und Q wo P konvex aber Q nicht ist, wie schnell kann man die Differenz $ P - Q $ zwischen P und Q berechnen, wenn P n und Q hat hat m Eckpunkte?Unterschied des einfachen konvexen und einfachen nicht konvexen Polygons
Man kann annehmen, dass die Polygone als Liste der im Uhrzeigersinn geordneten Scheitelpunkte angegeben sind.
"Wie schnell" hängt von vielen Parametern ab, also denke ich, wir sollten zuerst damit beginnen, wie es geht.
Erstens nehme ich an, Polygone liegen auf der gleichen Ebene. Beginnen Sie damit, den endlichen Schnittpunkt jeder Linie von P mit jeder Linie von Q zu berechnen. Wenn der Schnittpunkt existiert und der Schnittpunkt auf sich kreuzenden Linien liegt (ich meine zwischen Anfang und Ende, nicht auf ihnen), dividiere die Linie in zwei und führe die endliche Linie fort Linienschnittpunkte iterativ. Dann kategorisiere jedes Liniensegment (jetzt kann ich sie als Segment bezeichnen, weil sie alle geteilt sind, falls nötig), indem du einen Punkt in der Polygonberechnung mit den Mittelpunkten der Segmente verwendest ... Inner, Outer oder OnthePolygon ... Nach der Kategorisierung konstruiere a neues Polygon aus den Linien von P, die außerhalb von Q liegen, und Linien von Q, die innerhalb von P liegen. Hier wird Ihre Herausforderung mit Toleranzen und Linien, die aufeinander liegen, zu tun haben. Auf den ersten Blick ist der allgemeine Algorithmus so ..
Dieser Algorithmus kann verbessert werden, indem Linien und sogar Polygone eliminiert werden, indem ihre Bereiche (Minimum und Maximum für jede Achse) berechnet werden. Abgesehen von der Hardware, der Programmiersprache oder den Datenverarbeitungsparametern hängt die Geschwindigkeit dieser Operation von den eingegebenen Polygonen und deren Ausrichtung ab.