Algorithmus zum sortieren von Linien nach Schnittpunkten

[cycovery]

hi!

dies ist eine rein algorithmische Frage:

Ich habe ein Set von 2D linien. Einige dieser Linien treffen sich UNGEFÄHR in einem Schnittpunkt. Es kann mehrere solcher Schnittpunkte geben (üblicherweise sinds 2 bis 5). Es gibt Ausreisser, die nicht zu solch einer Gruppe von sich in einem Schnittpunkt treffenden Linien gehöhren.

Nun suche ich einen effizienten weg, zu bestimmen:
-wieviele solcher Schnittpunkte es gibt,
-die einzelnen Linien den Schnittpunkten zuzuordnen,
-für jeden Schnittpunkt eine optimale position bestimmen
-und die Ausreisser ausschliessen.

Hab mir gedacht das vielleicht irgendwie mit RANSAC hinzukriegen . . . konnte aber noch nicht recht austüfteln wie ich genau vorgehen soll..

Im Anhang hab ich ein Beispiel - die grauen Linien sollen auf diese weise gruppiert werden. In dem Fall gäbe es 3 verschiedene cluster und einen Ausreisser (die rote Linie)

Jemand ne Idee? dankeschön.

 

[Onkel Schuppig]

Ich habe ein Set von 2D linien. Einige dieser Linien treffen sich UNGEFÄHR in einem Schnittpunkt. Es kann mehrere solcher Schnittpunkte geben (üblicherweise sinds 2 bis 5).

Erkläre mal genauer. Ich sehe im Prinzip Dutzende, wenn nicht Hunderte Kreuzungen (nicht nur 2 bis 5).

Es gibt Ausreisser, die nicht zu solch einer Gruppe von sich in einem Schnittpunkt treffenden Linien gehöhren.

Wie ich es sehe, ist keine einzige Linie ganz frei.

Nun suche ich einen effizienten weg, zu bestimmen:
-wieviele solcher Schnittpunkte es gibt,
-die einzelnen Linien den Schnittpunkten zuzuordnen,
-für jeden Schnittpunkt eine optimale position bestimmen
-und die Ausreisser ausschliessen.

Watt is'n 'ne optimale Position?

Schnittalgorithmus: Im Prinzip hast du ja eine Menge von Linien mit den Koordinaten-Parametern x1, y1, x2, y2. Durch Einführung eines Parameters t, der von 0 bis 1 läuft, kannst du jede Linie so beschreiben:
Px(t) = x1 + t (x2 - x1)
Py(t) = y1 + t (y2 - y1)
Der Schnittpunkt mit einer zweiten Linie (z.B. x3, y3, x4, y4) führt zu einem Gleichungssystem:
1) x1 + t1 * (x2 - x1) = x3 + t2 * (x4 - x3)
2) y1 + t1 * (y2 - y1) = y3 + t2 * (y4 - y3)
t1 und t2 lassen sich daraus bestimmen.
Wenn 0 <= t1 <= 1 UND 0 <= t2 <= 1, dann schneiden sich die Linien, sonst nicht.
Bei gefundenem Schnittpunkt kann man diesen in eine Gesamtschnittpunktliste einfügen. Falls es diesen Schnittpunkt dort schon gibt, kann man einen weiteren Zeiger auf eine Linie dort eintragen und bekommt so nach und nach die gewünschte Liste mit Linien an jedem Schnittpunkt.

 

[cycovery]

Danke Onkel Schupping aber das ist nicht mein Problem . . . . vielleicht muss ich es besser erklären.

Natürlich hat es jede Menge Schnittpunkte - aber es gibt lokale Häufungen dieser Schnittpunkte, die indizieren dass diese Linien sehr warscheinlich tatsächlich von diesem Schnittpunkt gehöhren. Es sollte rein visuell schon auf den bildern erkennbar sein, dass zwei solche Punkte hervorstechen. Ein dritter solcher Punkt liegt oben links ausserhalb des Bildes. Der Grund, weshalb sich die Linien nicht genau im selben Punkt schneiden sind Messfehler. Und genau das ist das Problem. Die etlichen "einzelnen" Schnittpunkte von diesen "gehäuften" Schnittpunkten zu unterscheiden und das warscheinlichste Zentrum dieser gehäuften Schnittpunkte zu bestimmen (dass sie sich nicht genau schneiden liegt ja an den Messfehlern).
Nicht gerade einfacher wird das ganze dadurch, dass nicht bekannt ist, wieviele solcher echter 'gehäufter' Schnittpunkte es gibt - das Resultat (anzahl solcher gefundenen Punkte) wird also ganz klar von den Parametern meines Algorithmus abhängen - aber diese kann ich dann ja finetunen.

 

[cycovery]

Hier noch einmal ein Beispiel.

Das erste Bild wäre optimal und enthält keine Messfehler. Du (als Mensch) solltest relativ Einfach eine Zugehörigkeit der Linien zu einem von Zwei Punkten ausmachen können.

Im Zweiten Bild ist das schon schwieriger, da es gewisse Messfehler gibt - aber es ist trotzdem immernoch möglich.

Ich Suche nach einem Algorithmus, der genau das macht. Solche "speziellen" Punkte ausmacht und die Linien zuordnet.

 

[Onkel Schuppig]

Ich Suche nach einem Algorithmus, der genau das macht. Solche "speziellen" Punkte ausmacht und die Linien zuordnet.

Ich fürchte, zunächst mal muss man jede Linie mit jeder schneiden und erhält zunächst mal eine recht umfangreiche Schnittpunktliste.
Nun kann ein 2. Algorithmus die Schnittpunktliste durchgehen und die Schnittpunkte, die einen bestimmten Abstand d unterschreiten, herauspicken und in eine Häufungspunktliste eintragen. Der Häufungspunkt erhält die Linien der zugehörigen Schnittpunkte.
Wie du den maximal zulässigen Abstand d festlegst, ist offen.

struct Schnittpunkt {
  float t1, t2;
  Linie* ptr_l1;
  Linie* ptr_l2;
};

struct Haeufungspunkt {
  float x, y;    // Position
  vector<Linie*> vec_linien;
};

Nun gilt es noch, die endgültigen Häufungspunkte herauszufiltern. Wie macht der Mensch es denn in deinen Beispielebildern? Ich würde sagen, er sucht sich die Häufungspnkte mit vec_linien.size() > 2.
Dann noch die Frage:Welche Koordinaten x,y soll denn der Häufungspunkt bekommen?
Vielleicht den Durchschnitt aller im Umkreis d liegenden Schnittpunkte.

 

[Thomas Darimont]

Hallo,

also ich würde das folgendermaßen machen:

1) Alle Schnittpunkte im gegebenen Ausschnitt finden und Mapping aufbauen 2D Linie <-> Schnittpunkt
2) Anschließend die Schnittpunkte mit einem geeigneten Verfahren Clustern
3) Über das Mapping die 2D Linien den entsprechenden Clustern zuordnen.

Die Anzahl der Schnittpunkte kannst du beispielsweise so finden:
(Sorry für Java Code, aber das kann ich ca. 10 mal schneller schreiben als C/C++ Code...)

/**
 * 
 */
package de.tutorials;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import javax.imageio.ImageIO;

public class CrossCountExample {

	public static void main(String[] args) throws Exception {

		double maxX = 10.0;
		double maxY = 10.0;

		Line2D lineA = new Line2D.Double(0.0, 0.0, maxX, maxY);
		Line2D lineB = new Line2D.Double(0.0, maxY, maxX, 0.0);
		Line2D lineC = new Line2D.Double(8.0, 0.0, 8.0, maxY);
		Line2D lineD = new Line2D.Double(0.0, 8.0, maxX, 8.0);
		Line2D lineE = new Line2D.Double(0.0, 5.0, maxX, 5.0); //parallel to lineD

		Line2D[] lines = new Line2D[] { lineA, lineB, lineC, lineD, lineE };

		List<Point2D> intersectionPoints = new ArrayList<Point2D>();

		for (int i = 0; i < lines.length; i++) {
			for (int j = i + 1; j < lines.length; j++) {
				Line2D firstLine = lines[i];
				Line2D secondLine = lines[j];
				Point2D.Double point = computeIntersectionPoint(firstLine, secondLine);
				if(point != null){
					intersectionPoints.add(point);
					System.out.printf("Found intersection at: %s between line1: %s and line2: %s%n", point, toString(firstLine), toString(secondLine));
				}				
			}
		}

		System.out.printf("Total crosses: %s%n", intersectionPoints.size());

		saveImage(lines, intersectionPoints,20.0);
	}

	private static void saveImage(Line2D[] lines, List<Point2D> intersectionPoints, double scalingFactor) throws IOException {
		BufferedImage crossImage = new BufferedImage(200, 200, BufferedImage.TYPE_INT_RGB);
		Graphics2D g = (Graphics2D) crossImage.getGraphics();
		g.setTransform(AffineTransform.getScaleInstance(scalingFactor, scalingFactor));
		g.setStroke(new BasicStroke(0.2F));
		
		draw(g, Color.RED, lines);
		for(Point2D point : intersectionPoints){
			//convert Point2d to Shape to render it
			draw(g, Color.YELLOW, new Line2D.Double(point, point));
		}
		ImageIO.write(crossImage, "jpeg", new File("c:/crossImage.jpg"));
	}


	private static void draw(Graphics2D g, Color color, Shape ... shapes) {
		g.setColor(color);
		for (Shape shape : shapes) {
			g.draw(shape);
		}
	}

	private static Point2D.Double computeIntersectionPoint(Line2D firstLine, Line2D secondLine) {
		
		float firstX1 = (float) firstLine.getX1();
		float firstX2 = (float) firstLine.getX2();
		
		float firstY1 = (float) firstLine.getY1();
		float firstY2 = (float) firstLine.getY2();
		
		float secondX1 = (float) secondLine.getX1();
		float secondX2 = (float) secondLine.getX2();
		
		float secondY1 = (float) secondLine.getY1();
		float secondY2 = (float) secondLine.getY2();
		

		float den = ((firstX2 - firstX1) * (secondY2 - secondY1))
				- ((firstY2 - firstY1) * (secondX2 - secondX1));

		// firstLine & secondLine are parallel -> no interception
		if (den == 0) {
			return null;
		}

		float n1 = ((firstY1 - secondY1) * (secondX2 - secondX1))
				- ((firstX1 - secondX1) * (secondY2 - secondY1));

		float r = n1 / den;

		//-> no interception
		if (r < 0 || r > 1){
			return null;
		}
		
		float n2 = ((firstY1 - secondY1) * (firstX2 - firstX1))
				- ((firstX1 - secondX1) * (firstY2 - firstY1));

		float s = n2 / den;

		//-> no interception
		if (s < 0 || s > 1) {
			return null;
		}

		float interX = firstX1
				+ (r * (firstX2 - firstX1));
		float interY = firstY1
				+ (r * (firstY2 - firstY1));
		
		return new Point2D.Double(interX, interY);
	}

	private static String toString(Line2D line) {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("[");
		stringBuilder.append(line.getX1());
		stringBuilder.append(", ");
		stringBuilder.append(line.getY1());
		stringBuilder.append("]");
		stringBuilder.append("-");
		stringBuilder.append("[");
		stringBuilder.append(line.getX2());
		stringBuilder.append(", ");
		stringBuilder.append(line.getY2());
		stringBuilder.append("]");
		return stringBuilder.toString();
	}

}

Ausgabe:

Found intersection at: Point2D.Double[5.0, 5.0] between line1: [0.0, 0.0]-[10.0, 10.0] and line2: [0.0, 10.0]-[10.0, 0.0]
Found intersection at: Point2D.Double[8.0, 8.0] between line1: [0.0, 0.0]-[10.0, 10.0] and line2: [8.0, 0.0]-[8.0, 10.0]
Found intersection at: Point2D.Double[8.0, 8.0] between line1: [0.0, 0.0]-[10.0, 10.0] and line2: [0.0, 8.0]-[10.0, 8.0]
Found intersection at: Point2D.Double[5.0, 5.0] between line1: [0.0, 0.0]-[10.0, 10.0] and line2: [0.0, 5.0]-[10.0, 5.0]
Found intersection at: Point2D.Double[8.0, 2.0] between line1: [0.0, 10.0]-[10.0, 0.0] and line2: [8.0, 0.0]-[8.0, 10.0]
Found intersection at: Point2D.Double[2.0, 8.0] between line1: [0.0, 10.0]-[10.0, 0.0] and line2: [0.0, 8.0]-[10.0, 8.0]
Found intersection at: Point2D.Double[5.0, 5.0] between line1: [0.0, 10.0]-[10.0, 0.0] and line2: [0.0, 5.0]-[10.0, 5.0]
Found intersection at: Point2D.Double[8.0, 8.0] between line1: [8.0, 0.0]-[8.0, 10.0] and line2: [0.0, 8.0]-[10.0, 8.0]
Found intersection at: Point2D.Double[8.0, 5.0] between line1: [8.0, 0.0]-[8.0, 10.0] and line2: [0.0, 5.0]-[10.0, 5.0]
Total crosses: 9

Gruß Tom