Liegt ein Punkt im gleichseitigen Polygon oder ausserhalb?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Montag 30. März 2009, 10:28

Dein letzter Ansatz ist genau mein contains_any-Vorschlag, nur dass du den Inhalt der Funktion zweimal hinschreibst ;-)
Das Leben ist wie ein Tennisball.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Montag 30. März 2009, 13:58

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
User
Beiträge: 170
Registriert: Mittwoch 4. Juli 2007, 20:40

Mittwoch 1. April 2009, 13:50

nuss hat geschrieben:

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
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Freitag 10. April 2009, 00:11

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
User
Beiträge: 170
Registriert: Mittwoch 4. Juli 2007, 20:40

Freitag 10. April 2009, 09:03

nuss hat geschrieben: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.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Sonntag 12. April 2009, 12:30

damn your right ;)
also müssen alle schnittpunkte überprüft werden, um
eindeutig zu verifizieren, ob ein polygon im anderen liegt.

hab im übrigen auch ne neue "point_collide" geschrieben.

Code: Alles auswählen

    def point_collide(self, p):
        # zuerst werden alle linien, die komplett
        # überhalb oder unterhalb des punktes liegen
        # ausgeschlossen, so dass nurnoch linien übrigbleiben,
        # deren einer Punkt unterhalb des Punktes, und deren anderer
        # Punkt überhalb des Punktes liegen.
        # dann wird geschaut, wieviele der linien rechts, bzw links
        # von dem Punkt liegen. Ist diese Zahl ungerade,
        # so liegt der Punkt im Polygon, ist sie gerade, so liegt der
        # Punkt ausserhalb des Polygons.
        # Eckpunkte auf gleicher höhe wie der Punkt, werden dabei als
        # darüber-liegend angesehen.

        _count = 0
        for l in self.sides():
            # diesen Teil vielleicht wieder raus.
            if any(p == point for point in self):
                return False
            # ----------------------------------------
            # der hauptteil --------------------------
            elif (l[0][1] <= p[1] and l[1][1] > p[1]) or\
                    (l[0][1] > p[1] and l[1][1] <= p[1]):
                _s = left_or_right(l, p)
                if _s == "mid":
                    return False
                elif _s == "right":
                    _count += 1
            # ----------------------------------------

            # diesen Teil vieleicht wieder raus.
            # dieser block ist ausschließlich dafür da,
            # um zu verhindern, das Punkte, die auf einer der unteren
            # Linien des Polygons liegen, als im Polygon befindlich
            # ausgegeben werden.
            # Daher wäre es sinvoll, einen Weg zu finden,
            # das direkt im oberen Teil zu machen.
            elif radian(l[0], l[1]) == radian(l[0], p):
                if distance(l[0], l[1]) > distance(l[0], p):
                    return False
            # -----------------------------------------
        if _count % 2 == 0:
            return False
        return True


    def collide_any(self, points):
        return any(self.point_collide(point) for point in points)

    def polygon_collide(self, polygon):
        return polygon.collide_any(self) or self.collide_any(polygon)
;)
Antworten