Forum: PC-Programmierung Punkt innerhalb oder außerhalb? Einhüllendes Rechteck?


von Polygon-Dreher (Gast)


Lesenswert?

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
von hp-freund (Gast)


Lesenswert?

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.

von Arc N. (arc)


Lesenswert?

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!

von Karl H. (kbuchegg)


Lesenswert?

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.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

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
Noch kein Account? Hier anmelden.