suche Algorithmus um Länge von Linien zu berechnen

[SebastianKN]

Hallo,

mir fehlen irgendwie die richtigen Suchbegriffe um über google was brauchbares zu finden...

Folgendes:
Ich hab eine beachtliche Anzahl an horizontalen und vertikalen Linien und möchte von allen Linien die Länge berechnen (bzw. die Summe aller Längen). Allerdings können die Linien überlappen. Die überlappenden Teilstücke sollen nur einfach zur Summe dazugezählt werden. Wenn sich z.B. zwei Linien komplett überlappen, soll nur die Länge einer der beiden Linien in die Gesamtlänge einfliessen. Die Linien können sich allerdings auch nur teilweise überlappen.

Ich hab in meinem Prog für die Berechnung der Schnittpunkte schon den Scanline/Sweepline-Algorithmus implementiert. Vielleicht lässt sich da irgendwas machen... Wäre natürlich schön, wenn die Länge der Linien und die Schnittpunkte in einem Rutsch berechnet werden könnten.
Mir fehlen da grade irgendwie die Ideen... (ist auch schon spät bzw schon wieder früh).

Vielleicht habt ihr ja ne Idee oder auch nur ein Stichwort. Würde mich freuen!

Grüße
Sebastian

[jeebee]

1. Zusätzlich zu den Schnittpunkten noch Länge der Überschneidungen merken. Z.b. jedes mal bei Haltepunkt:
Ende einer Überschneidung? Ja:
L_überschneid := L_überschneid + (x_halt - x_letzer_halt)
2. Gesamtlänge: Summe aller Längen (rechnen als (x_end - x_anf) + (y_end - y_anf), da ja nur horiz. und senkrechte Stücke(?)) - Länge der Überschneidungen

MfG jeebee

PS: nur so ne Idee, bin eh gerade am Lernen für Datenstrukturen & Algorithmen (auch Scanline ;))

[SebastianKN]

1. Zusätzlich zu den Schnittpunkten noch Länge der Überschneidungen merken. Z.b. jedes mal bei Haltepunkt:
Ende einer Überschneidung? Ja

ja sicher, aber das ist ja das Problem. Wie finde ich raus ob eine Linie überlappt bzw. verdeckt wird?

mit Haltepunkt meinst Du vermutlich wenn die Scanline anhält um die Bereichssuche, also die Schnittpunktberechnung, zu starten?




L_überschneid := L_überschneid + (x_halt - x_letzer_halt)


Wenn ich das richtig verstanden hab, berechnet man damit nur den zurückgelegten Weg der Scanline. (?)



2. Gesamtlänge: Summe aller Längen (rechnen als (x_end - x_anf) + (y_end - y_anf), da ja nur horiz. und senkrechte Stücke(?)) - Länge der Überschneidungen


Und das ist ineffizient (sorry, dass ich heut so bös bin ;) ). Wenn eine Linie komplett durch eine andere Linie verdeckt wird, muss hier trotzdem die Länge der Linie berechnet werden um sie nachher wieder als Überlappung von der Gesamtlänge abzuziehen. Das sind zwei Berechnungen zuviel.

Ich hab den Scanline-Algo aus "Algorithmen in C" von Robert Sedgewick implementiert/abgeschrieben bzw. mir die Codestücke in dem Buch zusammengesucht.

erst mal wie sieht mein Scanlinealgo aus:
- nach y-Werten sortierter Vektor, der alle Segmente (Linien) enthält
-> vertikale Linien sind darin zweimal enthalten: einmal mit y1- und
einmal mit y2-Wert als Sortierkriterium
-> horizontale Segmente nur einmal
(ist glaub immer so...)

Die Scanline durchläuft also den Vektor. Trifft sie auf einen Anfangspunkt (also y1), fügt sie den Punkt in einen binären Suchbaum ein. Der Schlüssel im Baum ist der x-Wert. Trifft sie im Vektor auf einen Endpunkt, wird der zugehörige Anfangspunkt im Suchbaum gelöscht. Der Suchbaum enthält also immer die Anfangspunkte aller vertikalen Segmente, die die Scanline schneiden. Liegt im Vektor eine horizontale Linie, wird über eine rekursive Funktion eine Bereichssuche im Baum durchgeführt und damit die Schnittpunkte berechnet.


Die Berechnung der Segmentlänge:

für vertikale Segmente/Linien:

wenn die Scanline an einem Endpunkt einer vertikalen Linie ankommt (bei mir läuft die Scanline horizontal, also Segmente sind nach y-Werten sortiert), wird der Anfangspunkt des Segments aus dem binären Suchbaum gelöscht. Jetzt wird im Suchbaum nach einem Anfangspunkt, der den gleichen x-Wert hat, wie der gerade gelöschte Punkt, gesucht. Wird ein Punkt gefunden, wird die gerade gelöschte Linie von mindestens einer anderen Linie überlappt. Jetzt muss man nur noch feststellen, ob die Linie komplett oder nur teilweise überlappt wird. Das macht man, indem man den y-Wert des Anfangspunkts der gelöschten Linie mit dem y-Wert des gefunden Punktes (mit dem gleichen X-Wert) vergleicht. Liegt der gefundene Punkt oberhalb der gelöschten Linie, macht man "length += 0" und sonst "length += das_stück_was_nicht_überlappt_wird". das_stück_was_nicht_überlappt_wird kann ja mit den y-Werten ausgerechnet werden.

Wenn also zB drei Linien übereinanderliegen, haben die kürzeren beiden die Länge 0 und die längste ihre normale Länge, also y2 - y1.

Für horizontale Segmente mach ich das im Grunde gleich, nur ein bisschen anders, da da die Scanline nicht horizontal verlaufen darf, sondern vertikal.

[jeebee]

Überlappungen erkennen:
Eine Linie hat angefangen aber noch nicht aufgehört, eine andere mit gleicher "fester" Koordinate fängt an (Bsp: Linie 1 von (1,1) nach (10,1); Linie 2 von (5,1) nach (11,1))

[SebastianKN]

ok, dann haben wir das gleiche gemeint