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!
:
Verschoben durch User
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.