Moin Leute,
ich brauche nochmal eure Hilfe in Sachen Algorithmen. Ich verzweifel
hier noch an meiner Aufgabe.
Ich habe mehrere zweidimensionale Gebilde, die jeweils als Geraden und
Kreisbögen zusammengesetzt sind. Ungefähr so:
Linie von (13,11) nach (26,11)
Kreisbogen gg. Uhrzeigersinn um Mittelpunkt (26,16) von (26,11) nach
(26,21)
Linie von (26,21) nach (13,21)
Linie von (13,21) nach (13,11)
Es ist sichergestellt, dass dieses "Polygon" geschlossen ist, das heißt
Startpunkt = Endpunkt und alle Segmente fangen dort an, wo das vorherige
aufgehört hat.
Für die weitere Umsetzung (Darstellung von Luftraumdaten) muss ich nun
zwei Dinge wissen:
1. Ist ein gegebener Punkt innerhalb des Gebildes oder außerhalb? Bei
Polygonen aus Geraden findet Google tolle Algorithmen, das ist nicht das
Problem. Wenn aber Kreisbögen mit dabei sind, wird es schwierig. Einen
Kreisbogen einzeln zu bearbeiten, wäre vielleicht noch nicht mal so
schwierig. Aber wie zerlegt man das sinnvoll? Insbesondere, wenn der
Mittelpunkt des Kreisbogens nicht innerhalb, sondern außerhalb des
Gebildes liegt, es also "konkav" ist?
2. Was ist das kleinste einhüllende Rechteck des Gebildes, sprich, wie
groß muss ein Fenster sein, in dem ich das Ding komplett darstellen
kann? Problem ist ähnlich wie bei 1), mit fehlt der passende Ansatz. Das
genannte Beispiel finde ich dabei noch recht einfach, weil der
Kreisbogen genau ein Halbkreis ist und Anfang, Mittelpunkt und Ende
senkrecht übereinander liegen. Das muss allerdings nicht immer so sein.
Ideen wären echt hilfreich!
Ich denke das Einfachste wird sein deinen Kreisbogen in kleine gerade
Segmente zu zerlegen.
Dann ist es leicht nach kleinstem und grösstem X und Y zu sortieren und
so die Ausdehnung zu bestimmen.
Des weiteren kannst Du dann auch die normale "Punkt in Polygon"
Berechnung für gerade Elemente anwenden.
Polygon-Dreher schrieb:> 1. Ist ein gegebener Punkt innerhalb des Gebildes oder außerhalb?
Aus dem Bauch: Line-Sweep und die Kreissegmente approximieren,
Jordan-Kurvensatz (PIP, Point in polygon) (Edit: zu spät)
> 2. Was ist das kleinste einhüllende Rechteck des Gebildes, sprich, wie> groß muss ein Fenster sein, in dem ich das Ding komplett darstellen> kann? Problem ist ähnlich wie bei 1), mit fehlt der passende Ansatz.
Konvexe Hülle (Graham scan), Minimum-Bounding-Box
> Das> genannte Beispiel finde ich dabei noch recht einfach, weil der> Kreisbogen genau ein Halbkreis ist und Anfang, Mittelpunkt und Ende> senkrecht übereinander liegen. Das muss allerdings nicht immer so sein.>> Ideen wären echt hilfreich!
Polygon-Dreher schrieb:> genannte Beispiel finde ich dabei noch recht einfach, weil der> Kreisbogen genau ein Halbkreis ist und Anfang, Mittelpunkt und Ende> senkrecht übereinander liegen. Das muss allerdings nicht immer so sein.
Für den Kreisbogen müsstest du Fallunterscheidungen machen, in
welchen(m) Quadranten sich der Bogen abspielt, dann wirds leichter.
Mal dir auf einem Papier alle Möglichkeiten auf, du wirst sehen so viele
sind es gar nicht.
Für die Bounding Box sind nur 6 Punkte relevant
* Startpunkt des Bogens
* Endpunkt des Bogens
* Mittelpunkt + ( Radius; 0 )
* Mittelpunkt - ( Radius; 0 )
* Mittelpunkt + ( 0; Radius )
* Mittelpunkt - ( 0; Radius )
Aufgrund der Quadrantenanalyse findest du raus, von welchem dieser 6
Punkte jeweils die x bzw y Koordinate in die komplette Bounding Box des
Polygons eingerechnet werden muss.
Beispiel
2 | S 1
| *
| *
| *
| *
-------M------*---
| *
| E
3 | 4
Der Bogen (clockwise) beginnt beim Punkt S, also im Quadranten 1, und
geht zum Punkt E, also in den Quadranten 4
Aus dieser Kombination ergibt sich, dass von S bzw E die y Koordinaten
in die komplette Bounding Box eingerechnet werden. Für die x Koordinaten
sind Sx, Ex (fürs Minimum) relevant, fürs Maximum ist es MittelpunktX +
Radius
Und so gibt es für alle Kombinationen, aus welchem Quadranten in welchen
Quadranten der Bogen verläuft einfache Vorschriften, welche der 6 Punkte
in den jeweiligen Achsrichtungen relevant sind.
Und für dein erstes Problem:
du legst eine unendlich lange Gerade ausgehend vom Punkt quer durch das
Polygon. Im Prinzip spielt es keine Rolle, wie die Gerade verläuft, mit
einer waagrechten wird es meistens einfach. Dann zählst du die
Schnittpunkte mit dem Polygon. Bei einer geraden Anzahl an
Schnittpunkten liegt der Punkt drinnen, bei einer ungeraden liegt er
draussen. Es gibt ein paar pathologische Sonderfälle, auf die man achten
muss
###############
# # 3
# #
# P *---#####--------
# #
# # 1
###########
Die Gerade hat Schnittpunkte mit den Abschnitten 1 und 3. Das wären 2
Stück, was eigentlich auf P->aussen deuten würde, was aber klar falsch
ist. Ich habs bei mir dann so gemacht, dass ich mir angesehen habe, ob
der Schnittpunkt identisch mit einem der Endpunkte des Abschnitts ist.
(Einfacher Vergleich der y-Koordinaten, Bild studieren). Wenn ja, dann
wird der Punkt nur dann gezählt, wenn er identisch zum Maximum der
Y-Koordinaten der Endpunkte ist.
Im obigen Polygon wird daher der Schnitt mit 1 gezählt, der mit 3 nicht.
Dieselbe Regel kommt dann auch mit sowas
################
# #
# P *--######--#----
# # # #
# # # #
######## ####
problemlos klar. In dem Fall werden 3 Schnittpunkte gezählt und der
Punkt als innen klassifiziert.
Ich hab das seinerzeit über die Umlaufzahl gelöst:
Beitrag "Re: Ideen für Umlaufzahl-Berechnung?"
Da sind zwar keine Kreisbögen dabei, aber die kann man genauso einbauen.
Der einzige Unterschied ist, daß sich der Schnittpunkt mit einer Geraden
anders berechnet für einen Kreisbogen.
