Liegt ein Punkt im gleichseitigen Polygon oder ausserhalb?

[nuss]

Hallo, ich suche eine Möglichkeit, herauszufinden, ob ein Punkt
in einem gleichseitigen Polygon liegt, oder nicht.

Code: Alles auswählen

class Polygon(Circle):
    def __init__(self, center, point, angles):
        Circle.__init__(self, center, get_distance(center, point))
        # man kann jedes gleichseitige polygon aus genausovielen
        # Dreiecken zusammensetzen, wie es Seiten hat.
        angle_degree = 360.0/angles
        self.points = [point]
        degree = self.get_degree(point)
        while len(self.points) < angles:
            degree += angle_degree
            self.points.append(self.get_cordinate(degree))

Mein bisheriger ansatz ist, herauszufinden, welche beiden Eckpunkte dem Punkt am nächsten sind.
Jetzt weiß ich aber nicht, wie ich rauskriege, ob der Punkt Innerhalb, Ausserhalb, oder auf der Linie liegt.
Wäre froh um ein Stichwort, einen Link, oder eine Erklärung, die
das ganze auch für "nicht Mathematiker" verständlich erklärt

[numerix]

Ungetestete Idee:

Der Punkt, um den es geht, sei P. A und B seien die benachbarten Eckpunkte (die hast du ja schon herausbekommen, wenn ich dich recht verstehe; vermutlich über den Mittelpunktswinkel) und M der Mittelpunkt des Umkreises. Die Strecke AB schneidet die Gerade durch M und P im Punkt S. Dessen Koordinaten musst du berechnen.
Damit P im Polyon liegt, muss der Abstand d(M,P) <= d(M,S) sein.

Mach dir mal ne Skizze dazu mit der entsprechenden Beschriftung, dann sollte es klar werden.

[EyDu]

Alternativ kannst du auch für jedes Dreieck ABM testen, ob P darin liegt. Dazu betrachtest du die Winkel zwischen MA/MB, AM/AB und BA/BM. Ist die Summe der Winkel etwa 2*Pi, dann liegt der Punkt innen.

Oder noch einfacher: Wieder das Dreieck ABM. Teste ob der Punkt "rechts" (oder links, je nach Umlaufichtung) von allen Segmenten liegt.

[numerix]

Alternativ kannst du auch für jedes Dreieck ABM testen, ob P darin liegt. Dazu betrachtest du die Winkel zwischen MA/MB, AM/AB und BA/BM. Ist die Summe der Winkel etwa 2*Pi, dann liegt der Punkt innen.

Die Winkel, die du da nennst, sind doch die Innenwinkel des Dreiecks ABM, deren Summe sollte immer gleich 180° bzw. pi sein.

Oder ich habe dich missverstanden.

[EyDu]

Nee, ich war einfach zu trottelig es richtig hinzuschreiben

Gemeint waren die Winkel PA/PB, PB/PM und PM/PA. Also ein Kreis um P.

[bords0]

Und wenn das statt mit A, B und M mit den Eckpunkten des Polygons macht, geht es auch (man spart sich dann das Bestimmen der nächstliegenden Punkte).

Klappt auch mit beliebigen konvexen Polygonen.

[nuss]

ich glaube, ich hab nen vernünftigen ansatz gefunden, den ich aber noch umsetzen muss

Gegeben sind der Mittelpunkt M des Polygons
die nächstgelegenen Eckpunkte A und B,
und der Punkt, der genau auf der Mitte zwischen A und B liegt m(A, B)
der Winkel von m(A, B) zu A oder B und M muss bei einem gleichseitigen Polygon 90° betragen, also kann ich einfach gucken, ob der winkel von P
zum näheren der beiden Punkte A, B und M größer oder kleiner als 90° ist.
ist er kleiner, so ist der Punkt P im Polygon, ansonten ist er ausserhalb.

@EyDu und @boards:
irgendwie raff ich dass nicht, vielleicht kommts ja noch,
mit n bisschen zeit und nachdenken
ich machs jetzt ersmal so ^

[tordmor]

Überprüfe wie viele Strecken des Polygons sich mit der Halbgeraden oberhalb des Punktes schneiden. Ist die Zahl ungerade ist der Punkt innerhalb des Polygons sonst außerhalb. Funktioniert mit beliebigen geschlossenen Streckenzügen.

[HWK]

Diese beiden Algorithmen sind zwar sehr viel allgemeiner, sollten dann aber erst recht für diesen Spezialfall funktionieren.
MfG
HWK

[Goswin]

Es seien (x1, y1) und (x2, y2) die beiden nächstliegenden Punkte, es sei (xM, yM) der Mittelpunkt des Polygons (welcher bei dir ja vorgegeben ist) und es sei (xP, yP) der Testpunkt.

Die Gerade durch beide Polygonpunkte ist gegeben durch (x-x1)/(x-x2)==(y-y1)/(y-y2), also durch (x-x1)*(y-y2)-(y-y1)*(x-x2)==0.

Falls Vorzeichen[ (xP-x1)*(yP-y2)-(yP-y1)*(xP-x2) ]==Vorzeichen[ (xM-x1)*(yM-y2)-(yM-y1)*(xM-x2) ] gilt, dann liegt Punkt P innerhalb des Polygons; falls diese Vorzeichen verschieden sind, liegt Punkt P ausserhalb des Polygons; falls das erste Vorzeichen nicht existiert weil (xP-x1)*(yP-y2)-(yP-y1)*(xP-x2)==0 ist, dann liegt P genau auf demPolygon.

Das Polygon braucht nicht regelmäßig zu sein, muss aber für dieses Vorgehen konvex sein. Der Mittelpunkt M kann durch einen beliebigen Punkt im Polygoninneren ersetzt werden.

[nuss]

@ all, vielen Dank für die Ideen,
ich hab das ganze jetzt durch Winkel berechnungen gelöst.

Code: Alles auswählen

class Polygon(Circle):
    """
    class for equiliteral polygons
    """
    def __init__(self, center, point, angles):
        Circle.__init__(self, center, get_distance(center, point))
        # konkave? Polygone, lassen sich durch genausoviele
        # Dreiecke füllen, wie sie Seiten haben. Dabei zeigen diese Dreiecke
        # zum Mittelpunkt des Polygons.
        angle_degree = 360.0/angles
        degree = self.get_degree(point)
        self.points = [point]

        while len(self.points) < angles:
            degree += angle_degree
            self.points.append(self.get_cordinate(degree))
        
        # der Winkel von einem Eckpunkt aus, zu einem anliegenden Eckpunkt,
        # und dem Mittelpunkt.
        self._iw = winkel(self.points[0], self.center, self.points[1])[0]



    def collide_point(self, p):
        
        p_dist = get_distance(self.center, p)
        if p_dist > self.rad:
            return False

        # besorge den nächstgelegenen Eckpunkt.
        n_dist = self.rad*2
        for point in self.points:
            point_dist = get_distance(point, p)
            if point_dist < n_dist:
                n_dist = point_dist
                next = point

        lil_w = winkel(next, p, self.center)[0]
        if lil_w < self._iw:
            return True
        return False
        
        
    def polygon_collide(self, polygon):
        # um mit collide_point zu überprüfen, ob sich zwei Polygone
        # überschneiden, müssen beide Polygone alle Punkte des
        # anderen Polygons überprüfen.
        # Die Polygone überschneiden sich nur, wenn bei mindestens
        # einem Der Polygone ein Punkt des anderen Polygons 
        # innerhalb liegt.
        for point in polygon.points:
            if self.collide_point(point):
                return True
        for point in self.points:
            if polygon.collide_point(point):
                return True
        return False

[EyDu]

Vielleicht noch ein paar kleine Anmerkungen, sieht sonst ganz gut aus:
- Polygon ist ein ungünstiger Klassenname, da es nicht beliebige Polygone darstellt
- in deinem Fall ist das Polygon konvex; zum Füllen genügen schon n-2 Dreiecke
- gewöhne dir am besten an durchgehend in Bogenmaß zu rechnen, dass ist mathematisch am sinnvollsten und weniger fehleranfällig. Umrechnungen in oder aus Grad macht man dann nur bei der Anzeige.
- die while-Schleife in der __init__-Methode kannst du auch durch ein for ersetzen, dann sparst du dir das stückweise Aufaddieren. Die schönste Lösung dafür wäre sicher eine List Comprehension.
- du solltest next nicht überschreiben, da es eine built-in-Funktion
- die beiden for-Schleifen in polygon_collide kannst du durch itertools.chain zu einer einer Schleife zusammenfassen. Mit der any-Funktion und einem Generator-Ausdruck erhältst du für die Funktion sogar einen Einzeiler
- _iw und lil_w sind sehr nichtssagende Namen, die solltest du noch besser wählen. Andernfalls weißt du in vier Wochen nicht mehr, was du gemacht hast.

[nuss]

@EyDu

zum Füllen genügen schon n-2 Dreiecke

damit, dass sich das Polygon durch soviele Dreiecke füllen lässt,
wie es Seiten hatt, ist auch nicht gemeint, dass es sich nicht mit weniger füllen lassen würde, sondern, es geht mir vielmehr um diese Zeile.

Code: Alles auswählen

angle_degree = 360.0/angles

Ich hab mir dabei das Polygon als ein Konstrukt aus gleichgroßen Dreiecken vorgestellt, die alle zur Mitte zeigen.

die beiden for-Schleifen in polygon_collide kannst du durch itertools.chain zu einer einer Schleife zusammenfassen. Mit der any-Funktion und einem Generator-Ausdruck erhältst du für die Funktion sogar einen Einzeiler

besser ?

Code: Alles auswählen

return any(polygon.collide_point(s_point) or self.collide_point(p_point) for
                   p_point in polygon.points for s_point in self.points)

die while-Schleife in der __init__-Methode kannst du auch durch ein for ersetzen, dann sparst du dir das stückweise Aufaddieren. Die schönste Lösung dafür wäre sicher eine List Comprehension.

Code: Alles auswählen

for angle in range(angles+1)[1:]:
         self.points.append(self.get_cordinate(degree+angle_degree*angle))

besser so ? was meinst du mit list comprehesion in diesem Zusammenhang ?

Ich muss ehrlich zugeben, dass meine Mathekenntnisse doch eher schlecht als recht sind.
Daher sind die ganzen Mathematischen funktionen doch eher zusammengefrickelt.
Werd mir das Bogenmaß mal ansehen, und das Programm eventuell
später noch entsprechend umschreiben.
Jetzt ist mir erstmal wichtig, dass es fertig wird

[EyDu]

Hmm, das mit dem chain war wohl doch so keine gute Idee, ich hätte genauer hinschauen sollen.

Code: Alles auswählen

import itertools
def contains_any(ps, m):
    return any(m.collide_point(p) for p in ps.points)

und dann die eigentliche Methode:

Code: Alles auswählen

def polygon_collide(self, polygon):
    return contains_any(polygon, self) or contains(self, polygon)_any

Noch schöner wird es, wenn du aus der contains_any-Funktion eine Methode machst:

Code: Alles auswählen

def contains_any(self, ps):
    return any(self.collide_point(p) for p in ps.points)

Bei range kannst du auch eine untere grenze setzen:

Code: Alles auswählen

for angle in range(1, angles+1):
         self.points.append(self.get_cordinate(degree+angle_degree*angle))

oder mit der von mir angesprochenen List Comprehension:

Code: Alles auswählen

 self.points = [self.get_coordinate(degree+angle_degree*angle) for i in range(1, angles+1)]

[nuss]

Code: Alles auswählen

return any(polygon.collide_point(s_point) or self.collide_point(p_point) for
                   p_point in polygon.points for s_point in self.points)

ist wirklich nicht besonders schön, weil viel zu viele werte erzeugt werden.
But what about this?

Code: Alles auswählen

return any([any(polygon.collide_point(p) for p in self.points),
                   any(self.collide_point(p) for p in polygon.points])

(noch ungetestet)

edit:
das geht sogar noch schöner, mit einem any weniger

Code: Alles auswählen

return any(polygon.collide_point(p) for p in self.points) or\
        any(self.collide_point(p) for p in polygon.points)

(auch noch ungeteste)

[EyDu]

Dein letzter Ansatz ist genau mein contains_any-Vorschlag, nur dass du den Inhalt der Funktion zweimal hinschreibst

[nuss]

wobei du dafür allerdings 2 Funktionen brauchst,
im vergleich also 1ne Zeile mehr,
ausserdem kann contains_any so nur als ungebundene
Funktion oder über Polygon.contains_any(instanz, polygon)
angesprochen werden. :p

ich glaub, die Frage ist jetzt gelöst, danke für die Hilfe

[bords0]

Code: Alles auswählen

        # Die Polygone überschneiden sich nur, wenn bei mindestens
        # einem Der Polygone ein Punkt des anderen Polygons 
        # innerhalb liegt.

So wie es da geschrieben steht, stimmt es zwar, aber du überprüfst nur, ob die Ecken der Polygone im anderen liegen - und das muss nicht unbedingt der Fall sein, wenn sich die Polygone überschneiden.

[nuss]

Wenn man nur eins überprüft hast du recht, allerdings nicht, wenn man beide Polygone überprüft. dann muss eine Ecke von einem der Polygone im anderen Polygon liegen, damit sich die beiden überschneiden

[bords0]

Wenn man nur eins überprüft hast du recht, allerdings nicht, wenn man beide Polygone überprüft. dann muss eine Ecke von einem der Polygone im anderen Polygon liegen, damit sich die beiden überschneiden

Quark.

Geometrie ist nicht einfach. Gerade bei Fallunterscheidungen unterliegt man nur allzuleicht einer falschen Anschauung.

Nimm halt zwei gleichseitige Dreiecke mit Center (0, 0) und einer Ecke bei (1,0) bzw. (0,1). Dann liegen von den beiden Dreiecken gerade die 6 Ecken auf dem Einheitskreis und sonst alles im Innern des Einheitskreises. Also liegt keine der 6 Ecken im anderen Polygon.