Abstand Punkt zur Geraden

[Ranjo]

Hallo,
ich habe einen Point a und zwei Punkte r1 r2, die eine Gerade bilden.
Wie berechne ich nun den minimalen Abstand vom Punkt zur Geraden?
Versucht habe ich folgendende zwei Methoden, leider Erfolglos.

public double getDistance(Point  a, Point r1, Point r2)
	{
//		Point x = new Point();
//		Point ar = new Point();
//		x.x = r2.x - r1.x;
//		x.y = r2.y - r1.y;
//		ar.x = a.x * x.x;
//		ar.y = a.y * x.y;
//		
	//	double distance =  ((Math.sqrt(((ar.x*ar.x)+(ar.y*ar.y))))/(Math.sqrt((a.x*a.x)+(a.y*a.y))));
		
		double m= (r2.y -r1.y)/(r2.x -r1.x);
		double n = r1.y-(m*r1.x);
		
		double distance = Math.abs(((m*a.x) - (a.y+n))/Math.sqrt((m*m)+1));
		return distance;
		
	}

 

[jgh]

ein Punkt hat zu einer Geraden unendlich viele Abstände?
Was willst du denn haben, den minimalen, den maximalen....

 

[Ranjo]

ein Punkt hat zu einer Geraden unendlich viele Abstände?
Was willst du denn haben, den minimalen, den maximalen....

Hast recht 😉
Den minimalen Abstand suche ich.

 

[Melfis]

Auf der verlinkten Seite ist das sehr schön erklärt:
abstand-punkt-gerade

 

[Ranjo]

Leider auch nur in 3D, ich brauche 2D und wie du oben siehst habe ich es schon so ähnlich versucht.
Vielleicht ein Fehler in meinen Code?

 

[Melfis]

Ohne Mathekenntnise:

	public double getDistance(Point  a, Point r1, Point r2){		
		Line2D.Double line=new Line2D.Double(r1, r2);
		return line.ptLineDist(a);
	}

 

[Ranjo]

Ich programmiere eine Android-Anwendung, und da ist diese Java Klasse leider nicht vorhanden.

 

[SlaterB]

der Code in Posting 1 hat doch ein strukturiertes Vorgehen,
warum untersuchst du ihn nicht näher, vergleichst ihn mit Papierrechnung?

> double m= (r2.y -r1.y)/(r2.x -r1.x);
was ist m, was ist (r2.y -r1.y), was ist (r2.x -r1.x)?
alles einzeln ausgeben, prüfen!

zu beachten ist, dass int/ int in Java gerundet wird: 4/ 3 = int 1, nicht double 1.3333

trickse z.B. mit

double m= (r2.y -r1.y)*1.0/(r2.x -r1.x);

dann wird rechzeitig auf double umgeschaltet

 

[Ranjo]

Danke, aber das führt leider zu auch keinem Ergebnis.

 

[Marco13]

Die Division dort sieht aus, als würde dort eine Steigung berechnet. Das ist natürlich schlecht für senkrechte Linien. Nur schnell hingeschrieben, könnte aber grob passen:

import java.awt.Point;

public class Distances
{
    public static void main(String[] args)
    {
        Point a = new Point(1,2);
        Point r1 = new Point(1,1);
        Point r2 = new Point(4,4);
        double d = getDistance(a, r1, r2);
        System.out.println(d);
    }
    public static double getDistance(Point  a, Point r1, Point r2)
    {
        return Math.sqrt(getSquaredDistance(a,r1,r2));
    }
    
    public static double getSquaredDistance(Point  a, Point r1, Point r2)
    {
        // Normalisierte Richtung r1 --> r2 ausrechnen 
        double dx = r2.getX() - r1.getX();
        double dy = r2.getY() - r1.getY();
        double len = Math.sqrt(dx*dx+dy*dy);
        dx /= len;
        dy /= len;

        // Richtung r1 --> a ausrechnen
        double dax = a.getX() - r1.getX();
        double day = a.getY() - r1.getY();
        
        // Punkt a auf Gerade r1 --> r2 projizieren
        double dot = dax * dx + day * dy;
        double px = r1.getX() + dx * dot;
        double py = r1.getY() + dy * dot;
        
        // Abstand zwischen a und projiziertem Punkt ausrechnen
        double ddx = a.getX()-px; 
        double ddy = a.getY()-py;
        double squaredDistance = ddx * ddx + ddy * ddy;
        return squaredDistance;
    }
}

EDIT: Hab' nochmal in Line2D geschaut, da wird auch noch die erste Wurzel vermieden indem r1 in den Ursprung geschoben und mit quadrierten Werten gerechnet wird. Geschickt, geschickt 😉

 

[Melfis]

Vollständigkeitshalber noch ne Version mit einer Gradengleichung:

	public static double getDistance2(Point2D.Double a, Point2D.Double r1, Point2D.Double r2)
    {       
        if(r1.x==r2.x&&r1.y==r2.y){
        	return Double.NaN;	//oder Distance von r1 bzw r2 zu a
        }
		
		double m1= (r2.y -r1.y)/(r2.x -r1.x);
        double b1 = r1.y-(m1*r1.x);
        
        if(m1==0.0){
        	return Math.abs(b1-a.y);
        }
        
        if(Double.isInfinite(m1)){
        	return Math.abs(r1.x-a.x);
        }
        
        double m2=1.0/m1;
        double b2 = a.y-(m1*a.x);
        
        double xs=(b2-b1)/(m1-m2);
        double ys=m1*xs+b1;
 
        
        double c1=a.x-xs;
        double c2=a.y-ys;

        
        double distance = Math.sqrt(c1*c1+c2*c2);
        return distance;
        
    }

 

[Ranjo]

Hallo Leute, danke für eure beiträge, aber beide lösungen funktionierten noch nicht ganz. Scheint wohl echt etwas tricky zu seind as ganze.

@Marco13: läuft irgendwie gar nicht. distance sind immer zahlen im min 6 stelligen bereich obwohl der punkt nach dran ist!

@Melfis: deine lösung scheint nur bei horizontalen zu funktionieren

 

[Marco13]

Vergleich mit den Ergebnissen, die von java.awt.geom.Line2D geliefert werden:

import java.awt.Point;
import java.awt.geom.Line2D;
import java.util.Random;


public class Distances
{
    public static void main(String[] args)
    {
        Random random = new Random(0);
        for (int i=0; i<100; i++)
        {
            Point a = new Point(random.nextInt(100),random.nextInt(100));
            Point r1 = new Point(random.nextInt(100),random.nextInt(100));
            Point r2 = new Point(random.nextInt(100),random.nextInt(100));

            double d0 = getDistance(a, r1, r2);
            System.out.println(d0);
            double d1 = getDistance2(a, r1, r2);
            System.out.println(d1);
            
            if (Math.abs(d0-d1) > 1e-5)
            {
                System.out.println("Something wrong!");
                System.exit(-666);
            }
        }
        System.out.println("All fine...");
            
    }
    
    public static double getDistance2(Point  a, Point r1, Point r2)
    {
        return Line2D.ptLineDist(r1.x, r1.y, r2.x, r2.y, a.x, a.y);
    }

    public static double getDistance(Point a, Point r1, Point r2)
    {
        return Math.sqrt(getSquaredDistance(a,r1,r2));
    }
    
    public static double getSquaredDistance(Point  a, Point r1, Point r2)
    {
        // Normalisierte Richtung r1 --> r2 ausrechnen 
        double dx = r2.getX() - r1.getX();
        double dy = r2.getY() - r1.getY();
        double len = Math.sqrt(dx*dx+dy*dy);
        dx /= len;
        dy /= len;

        // Richtung r1 --> a ausrechnen
        double dax = a.getX() - r1.getX();
        double day = a.getY() - r1.getY();
        
        // Punkt a auf Gerade r1 --> r2 projizieren
        double dot = dax * dx + day * dy;
        double px = r1.getX() + dx * dot;
        double py = r1.getY() + dy * dot;
        
        // Abstand zwischen a und projiziertem Punkt ausrechnen
        double ddx = a.getX()-px; 
        double ddy = a.getY()-py;
        double squaredDistance = ddx * ddx + ddy * ddy;
        return squaredDistance;
    }
    
    
}

 

[Melfis]

[EDIT]Waren zwei Flüchtigkeitsfehler drin, jetzt gehts[/EDIT]

	public static double getDistance2(Point2D.Double a, Point2D.Double r1, Point2D.Double r2)
    {       
        if(r1.x==r2.x&&r1.y==r2.y){
        	return Double.NaN;	//oder Distance von r1 bzw r2 zu a
        }
		
		double m1= (r2.y -r1.y)/(r2.x -r1.x);
        double b1 = r1.y-(m1*r1.x);
        
        if(m1==0.0){
        	return Math.abs(b1-a.y);
        }
        
        if(Double.isInfinite(m1)){
        	return Math.abs(r1.x-a.x);
        }
        
        double m2=-1.0/m1;
        double b2 = a.y-(m2*a.x);
        
        double xs=(b2-b1)/(m1-m2);
        double ys=m1*xs+b1;
        
        double c1=a.x-xs;
        double c2=a.y-ys;
        
        double distance = Math.sqrt(c1*c1+c2*c2);
        return distance;   
    }

[OT]Seit wann darf man seine Beiträge nur 60 min nach erstellung editiren? Ich find das doof🙁[/OT]

 

[Ranjo]

Wo genau waren die Fehler?
Kanns nun leider nicht überprüfen.

Mache ich später...

 

[Melfis]

Bei m2 fehlte das minus vor der 1.0 und bei b2 gabs ein copy&paste Fehler m1 wurde nicht durch m2 ersetzt.

 

[Marco13]

Ich würde dir trotzdem dringend empfehlen, die vektorielle Version zu verwenden.

Im Zweifelsfall die aus Line2D, mit entsprechenden Acknowledgements:

    // From [url=http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/2d585507a41b/src/share/classes/java/awt/geom/Line2D.java]jdk6/jdk6/jdk: src/share/classes/java/awt/geom/Line2D.java@2d585507a41b[/url]
    public static double ptLineDistSq(double x1, double y1,
                                      double x2, double y2,
                                      double px, double py)
    {
        // Adjust vectors relative to x1,y1
        // x2,y2 becomes relative vector from x1,y1 to end of segment
        x2 -= x1;
        y2 -= y1;
        // px,py becomes relative vector from x1,y1 to test point
        px -= x1;
        py -= y1;
        double dotprod = px * x2 + py * y2;
        // dotprod is the length of the px,py vector
        // projected on the x1,y1=>x2,y2 vector times the
        // length of the x1,y1=>x2,y2 vector
        double projlenSq = dotprod * dotprod / (x2 * x2 + y2 * y2);
        // Distance to line is now the length of the relative point
        // vector minus the length of its projection onto the line
        double lenSq = px * px + py * py - projlenSq;
        if (lenSq < 0) {
            lenSq = 0;
        }
        return lenSq;
    }

@Melfis: In der Methodensignatur sollte (wenn) dann nur Point2D stehen, und nicht Point2D.Double (mit Point2D kann man auch einen Point oder einen Point2D.Float reinstecken). Zudem kann man die Vergleiche zweier double-Werte mit "==" (nicht nur, aber speziell in diesem Fall) als "schlicht falsch" bezeichnen (siehe z.B. Why doesn't my floating-point comparison work?, C++ FAQ )

 

[Melfis]

@Marco13: Ich würde auch die Vektorielle Methode empfehlen, jedoch hat Ranjo in einem Post gefragt wo sein fehler ist, deshalb hab ich das kleine Beispiel, welches seinen Ansatz weiterführt, zusammengeschustert. Ohne Double kein direkter zugriff auf die Feldvariablen d.h. mehr Schreibarbeit für mich.
Mit dem Vergleich zweier Fließkommazahlen geb ich dir recht, aber ich denke der TE weiß was die abfrage darstellen soll.

 

[Ranjo]

@marco13: Was wird bei deiner variante zurückgegen Abstand in Pixeln?

 

[Ranjo]

Also, letzendlich funktionieren doch beide methoden.
Problem war das in Android die Punkt methode anders definiert ist und es keine getX() existiert, die ein double zurückliefert, sondern nur direkter variablenzugriff auf X und Y, die als int deklariert sind.

Habt ihr evtl noch die Mathematische Formel(fürs Verständnis meinerseits) parat?

Danke

 

[TryToHelp]

Naja, du hast es ja schon verwendet.

Du hast eine Grade zwischen zwei Punkten.
Dann bildest du die Ortogonale (Grade mit der Steigung der ersten * -1
Diese lässt du durch den Punkt gehen
Dann schneidest du die zwei Graden die du hast.
Nun hast du den Schnittpunkt.
Zwischen Schnitpunkt und deinem Punkt berechnest du den Abstand ;-)

 

[Ranjo]

Nun habe ich noch einmal etwas getestet.

@marco13: Deine Lösung berechnet den Abstand vom Punkt bis zum Punkt B der geraden, also nicht den minimalen Abstand.

@melfis: funktioniert.

Danke euch beiden

 

[Marco13]

Hast du das aus http://www.java-forum.org/allgemeine-java-themen/143302-abstand-punkt-geraden.html#post954478 mal laufen lassen? (Ich will mich nicht rumschlagen, aber ... zumindest ICH versuche im allgemeinen, nur Dinge zu sagen, bei denen mir niemand widersprechen kann...)

 

[Ranjo]

Naja, habe es nun nochmal getestet, es ist definitiv nicht der minimale Abstandzu Geraden. Der nimmt sich auf der geraden irgendeinpunkt im letzten drittel und ermiteln dan den Abstand

@ melfis: deins scheint auch nicht korrekt zu laufen, habe ich mehrere geraden, ist die Distanz zu einer entfernteren geraden aufeinmal geringer als zu einer Geraden die näher gelegen ist.

EDIT: melfis, ddeine Lösung scheint trotzdem nur bei horizontalen zu funktionieren! 🙁

 

[Marco13]

Du kannst auf Report a Bug or Request a Feature einen Bug Report erstellen, in dem du den Leuten von Sun/Oracle erklärst:

"Die Methode Line2D#ptLineDistSq hat einen Fehler. Der nimmt sich auf der geraden irgendeinpunkt im letzten drittel und ermiteln dan den Abstand"

Viel Glück.

(Ich behaupte nicht, dass mein Code richtig ist. Wegen des Vergleiches mit der Line2D-Implementierung erwarte ich nur, dass die Begründung, warum er falsch ist, zumindest an einem Beispiel gezeigt wird, bei dem er etwas anderes ausrechnet, als die Line2D-Implementierung)

 

[TryToHelp]

Hast du einfach mal versucht es mittels Zettel und Stift auszurechnen? Zu schauen was dabei rauskommt und es verglichen? Wenn ja, programiere einfach den Algorithmus, denn du bei der Zettel und Stift variante genommen hast, dann funktioniert es ja Richtig. Hab mir die zwei code Beispiele nicht angeschaut, jedoch, wenn es nicht funktioniert, gehe halt mal mit logik ran, verstehe was der Code macht, dann findest du vielleicht den Fehler ;-)

 

[Ranjo]

Du kannst auf Report a Bug or Request a Feature einen Bug Report erstellen, in dem du den Leuten von Sun/Oracle erklärst:

"Die Methode Line2D#ptLineDistSq hat einen Fehler. Der nimmt sich auf der geraden irgendeinpunkt im letzten drittel und ermiteln dan den Abstand"

Viel Glück.

(Ich behaupte nicht, dass mein Code richtig ist. Wegen des Vergleiches mit der Line2D-Implementierung erwarte ich nur, dass die Begründung, warum er falsch ist, zumindest an einem Beispiel gezeigt wird, bei dem er etwas anderes ausrechnet, als die Line2D-Implementierung)

Du meinst ptLineDst?

Wo hast du überhaupt den Inhalt der Methode her?

Edit: Habe den Link schon gefunden 🙂

Deine und ptLineDist liefern die selben Resultate, aber leider steht in der Java Api nirgendwo etwas von minimalen Abstand :-(

 

[Landei]

Nochmal zur Mathematik:

Sei die Gerade gegeben als y = a*x+b und der Punkt mit (xp,yp). Setzt man xp in die Gleichung ein erhält man y = a*xp+b, also einen vertikalen Abstand dy = |a*xp+b - yp|.
Nun kann man die Gleichung nach x umstellen: x = (y - b)/a, und erhält dann analog einen horizontalen Abstand dx = |(yp - b)/a - xp|.

Nun ist die Höhe im rechtwinkligen Dreieck mit den Katheden dx und dy gesucht (die Hypothenuse wird ja durch unsere Gerade gebildet, und die Höhe steht senkrecht darauf). Da das Produkt der Katheden gleich dem Produkt aus Hypothenuse und Höhe ist (folgt aus der Flächenberechnung), haben wir h = dx*dy / sqrt(dx²+dy²).

 

[Marco13]

Line2D (Java Platform SE 6)

Returns the square of the distance from a point to a line. The distance measured is the distance between the specified point and the closest point on the infinitely-extended line defined by the specified coordinates

Ich bin raus.

 

[Ranjo]

Line2D (Java Platform SE 6)

Ich bin raus.

Sich zu verlesen ist wohl heut zu Tage verboten?!

 

[Melfis]

Würde mal behaupten mein code klappt, zumindest kommt bei mir das selbe raus wie bei Line2D.

Ich denke in diesem Thread gibt es genügend Tipps zur Lösung deines Problem, der Rest bleibt bei dir. Ich folge mal Marco13, ich bin raus 🙂

 

[Ranjo]

Melfis, nichts für ungut, aber bei dir kommen ganz andere zahlen raus als bei Line2D.

Nichts desto trotz habt Ihr mir sehr geholfen.

Tausend Dank.
Ranjo

 

[Melfis]

Kannst mit Copy Paste testen, ist der selbe Code wie Post 14#:

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.Random;

public class Distance {

	public static void main(String[] args) {

		Random ran = new Random();
		for (int i = 0; i < 10000; i++) {
			Point2D.Double a = new Point2D.Double(ran.nextDouble(),
					ran.nextDouble());
			Point2D.Double r1 = new Point2D.Double(ran.nextDouble(),
					ran.nextDouble());
			Point2D.Double r2 = new Point2D.Double(ran.nextDouble(),
					ran.nextDouble());
			
			double d1=getDistance1(a, r1, r2);
			double d2=getDistance2(a, r1, r2);
			

			if (!(Math.abs(d1-d2) < 0.0000001)) {
				System.out.println("Stimmt Nicht");
				}
			
		}

	}

	public static double getDistance1(Point2D a, Point2D r1, Point2D r2) {
		Line2D.Double line = new Line2D.Double(r1, r2);
		return line.ptLineDist(a);
	}

	public static double getDistance2(Point2D.Double a, Point2D.Double r1,
			Point2D.Double r2) {
		double m1 = (r2.y - r1.y) / (r2.x - r1.x);
		double b1 = r1.y - (m1 * r1.x);

		if (m1 == 0.0) {
			return Math.abs(b1 - a.y);
		}

		if (Double.isInfinite(m1)) {
			return Math.abs(r1.x - a.x);
		}

		double m2 = -1.0 / m1;
		double b2 = a.y - (m2 * a.x);

		double xs = (b2 - b1) / (m1 - m2);
		double ys = m1 * xs + b1;

		double c1 = a.x - xs;
		double c2 = a.y - ys;

		double distance = Math.sqrt(c1 * c1 + c2 * c2);
		return distance;
	}
}

 

[Marco13]

Sich zu verlesen ist wohl heut zu Tage verboten?!

Da es nicht um's Threadthema geht, bin ich nochmal kurz drin: Die eigentliche Fragestellung könnte man schon hinterfragen. Eine Websuche nach "distance point line 2d" dürfte doch das eine odere andere Ergebnis bringen. Auf die Idee zu kommen, mal zu schauen, wie die vorgefertigte Methode aus Line2D aussieht wäre auch nicht zu viel verlangt. Aber all das hat (bisher) keiner kritisiert, sondern es wurde versucht, sinnvoll und konstruktiv zu antworten. Wenn dann als Rückfragen/Reaktionen aber nur kommt ~"Das geht nicht, das ist falsch" etc, obwohl es eben nicht falsch ist, fühlt man sich schon veräppelt :bahnhof:

 

[Ranjo]

Fühle mich auch veräppelt, aber ist gut nun!

Bitte schliessen!

 

[pappawinni]

Hm... also der Abstand zwischen Geraden ist mal definiert durch den kürzesten Abstand.
Was sollte denn auch sonst der Abstand zwischen Geraden sein. Es gibt schon Spezialisten.
Und wenn ich schon dabei bin..
Hier:
http://www.java-forum.org/allgemeine-java-themen/139211-suche-matrix-libraries.html#post933761
hatte ich das mal für 3D gemacht.
Und 2D wird das, für Z=0. Das ist ja jetzt wohl keine Hürde.