Überschneidungen erkennen

[Henri.py]

Hi,
ich bastel gerade an nem kleinen Projekt, und habe ein Problem, an dem ich nicht vorbei komme:

Das Ziel ist es, einen Graph von Straßen und deren Verbindungen zu erstellen. Dazu wird in 2 Teile aufgeteilt: Verbindungen und Kreuzungen. Später soll das auch mehrspurig möglich sein.
Dabei sind die Koordinaten der Straßen auch negativ, da ich mit 4 Quadranten habe. Im folgenden Bild sind alle vom System erkannten Kreuzungen rot gefärbt. Ob eine Kreuzung als solche erkannt wird scheint teilweise völlig willkürlich. Ich gehe davon aus, dass das irgend etwas mit orientation() zutun hat...
https://imgur.com/a/StH9JD2

Code: Alles auswählen

import math

class Road:
    def __init__(self, start, end, ):
        self.start = start
        self.end = end
        self.length = math.dist(self.start, self.end)


def orientation(p, q, r):
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0  # Collinear points
    return 1 if val > 0 else 2  # Clockwise or counterclockwise


def on_segment(p, q, r):
    return max(p[0], r[0]) >= q[0] >= min(p[0], r[0]) and max(p[1], r[1]) >= q[1] >= min(p[1], r[1])


class Simulation:
    def __init__(self):
        self.roads = []
        self.Network = []

    def create_road(self, start, end):
        self.roads.append(Road(start, end))

    def build_network(self):
        """
        :return: Network = [Roadstart, Roadend, Roadlenght, Connections-to-Road:[Roadobj, pos], Connections-from-Road:[Roadobj, pos], Intersections:[Roadobj, pos],]
        """
        self.Network = []

        for road1 in self.roads:
            R = {"start": road1.start, "end": road1.end, "length": road1.length}
            intersections = []
            to_road = []
            from_road = []
            for road2 in self.roads:
                if road1 == road2:
                    continue

                o1 = orientation(road1.start, road1.end, road2.start)
                o2 = orientation(road1.start, road1.end, road2.end)
                o3 = orientation(road2.start, road2.end, road1.start)
                o4 = orientation(road2.start, road2.end, road1.end)

                connection = ((abs(road1.start[0]) == abs(road2.end[0]) and abs(road1.start[1]) == abs(road2.end[1])) or (abs(road1.end[0]) == abs(road2.start[0]) and abs(road1.end[1]) == abs(road2.start[1])))
                if (o1 != o2) and (o3 != o4) and not connection:
                    intersections.append(road1)

                if (o1 == 0 and on_segment(road1.start, road2.start, road1.end)) or (o4 == 0 and on_segment(road2.start, road1.end, road2.end)):
                    to_road.append(road1)  # road2.start lies on line1 or road1.end lies on road1
                if (o2 == 0 and on_segment(road1.start, road2.end, road1.end)) or (o3 == 0 and on_segment(road2.start, road1.start, road2.end)):
                    from_road.append(road1)  # road2.end lies on line1 or road1.start lies on road2

            R["intersections"] = intersections
            R["connections_to_road"] = to_road
            R["connections_from_road"] = from_road

            self.Network.append(R)
        for a in self.Network:
            print(a)

[__deets__]

Ich verstehe die Rohdaten nicht. Wie definierts du die Strassen, und hast du mal ein Beispiel fuer eine, die korrekt ist, und eine, die nicht?

[Henri.py]

also, der nutzer kann straßen erstellen. diese sind dann durch deren start position und end position definiert (siehe create_road()). Nachdem der Nutzer alle Straßen plaziert hat, soll erkannt werden, welche straßen mit einander verbunden sind und somit ein netz oder ein plan in form eines graphes mit edges und vertices erstellt werden. Eine Straße ist immer korrekt. Aber die Verbindungen werden nicht richtig erkannt. Ich möchte folgendes erkennen:
intersections: Dort wo sich 2 Straßen kreuzen
connections: 2 Straßen die einfach miteinander verbunden sind
Wie man auf dem Bild an den eingezeichneten Achsen erkennt, sind die Positionen auch mal im Minusbereich, und ich vermute, dass darin die Probleme begründet sind, habe aber bisher keine möglichkeit gefudnen das zu fixen

[Henri.py]

Ich hab das ganze mal auf https://github.com/PyHenri/lol hochgeladen, bestimmt ist es dann klarer

[__deets__]

Die Daten sind wichtig, nicht die simple Klasse. Es geht um die Frage, ob die Linien einfach unbedingt sind, und sich kreuz und quer verteilen koennen. Oder ob es dabei Regeln gibt. Wenn sie einfach kreuz und quer verlaufen, dann musst du die Daten erstmal normalisieren. Erstens musst du Punkte, die mit einem Epsilon-Kriterium nah beienander sind, zu einem zusammenfallen lassen. Sobald das passiert ist, muessen paarweise Linien auf Schnitt geprueft werden. Das erzeugt dann neue Punkte, und Segmente. Und dann muss man nur jeden Punkt mit mehr als zwei Abgaengen zur Kreuzung machen.