Abstand Punkt zur Geraden

R

Ranjo

Mitglied
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.

Java: 
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;
		
	}
 
Zuletzt bearbeitet:
jgh

jgh

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

Ranjo

Mitglied
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?
 
M

Melfis

Aktives Mitglied
Ohne Mathekenntnise:
Java: 
	public double getDistance(Point  a, Point r1, Point r2){		
		Line2D.Double line=new Line2D.Double(r1, r2);
		return line.ptLineDist(a);
	}
 
S

SlaterB

Gast
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
 
M

Marco13

Top Contributor
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:
Java: 
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 ;)
 
Zuletzt bearbeitet:
M

Melfis

Aktives Mitglied
Vollständigkeitshalber noch ne Version mit einer Gradengleichung:
Java: 
	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;
        
    }
 
R

Ranjo

Mitglied
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
 
M

Marco13

Top Contributor
Vergleich mit den Ergebnissen, die von java.awt.geom.Line2D geliefert werden:
Java: 
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;
    }
    
    
}
 
M

Melfis

Aktives Mitglied
[EDIT]Waren zwei Flüchtigkeitsfehler drin, jetzt gehts[/EDIT]
Java: 
	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]
 
M

Marco13

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

Im Zweifelsfall die aus Line2D, mit entsprechenden Acknowledgements:
Java: 
    // 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 )
 
M

Melfis

Aktives Mitglied
@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.
 
R

Ranjo

Mitglied
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
 
T

TryToHelp

Gast
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 ;-)
 
R

Ranjo

Mitglied
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
 
R

Ranjo

Mitglied
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! :(
 
Zuletzt bearbeitet:
M

Marco13

Top Contributor
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)
 
T

TryToHelp

Gast
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 ;-)
 
R

Ranjo

Mitglied
Marco13 hat gesagt.:
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)
Zum Vergrößern anklicken....

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 :-(
 
Zuletzt bearbeitet:
Landei

Landei

Top Contributor
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²).
 
M

Melfis

Aktives Mitglied
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 :)
 
R

Ranjo

Mitglied
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
 
M

Melfis

Aktives Mitglied
Kannst mit Copy Paste testen, ist der selbe Code wie Post 14#:
Java: 
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;
	}
}
 
Zuletzt bearbeitet:
M

Marco13

Top Contributor
Ranjo hat gesagt.:
Sich zu verlesen ist wohl heut zu Tage verboten?!
Zum Vergrößern anklicken....

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:
 
P

pappawinni

Gast
Zuletzt bearbeitet von einem Moderator:
Ähnliche Java Themen
  Titel Forum Antworten Datum
J Zahlen Abstand zur Null bestimmen Allgemeine Java-Themen 11
S Algorithmus um Objekte auf einer Flaeche mit gleichem Abstand anzuordnen..? Allgemeine Java-Themen 20
M Swing JFreeChart Domain Axis Label Abstand zu TickUnitLabel Allgemeine Java-Themen 9
W itext: Initialer Abstand in einem Dokument Allgemeine Java-Themen 2
C JTable, Abstand zwischen Zellen Allgemeine Java-Themen 2
B Breite/Abstand Allgemeine Java-Themen 8
D abstand 2er punkte Allgemeine Java-Themen 18
S Best Practice Punkt im dreidimensionalen Raum Bestimmen Allgemeine Java-Themen 24
M Bei String.format ein Komma statt einem Punkt ausgeben lassen Allgemeine Java-Themen 1
das_leon Komma statt Punkt Allgemeine Java-Themen 10
S Einen Punkt um den Ursprung drehen Allgemeine Java-Themen 5
I Figur zu bestimmtem Punkt drehen Allgemeine Java-Themen 2
G Z Wert - 3 Dimensionaler Punkt Allgemeine Java-Themen 13
Guybrush Threepwood Pattern gesucht: Punkt ohne Leerzeichen dahinter Allgemeine Java-Themen 3
P Datentypen float mit komma statt punkt möglich? Allgemeine Java-Themen 6
S Punkt der Klasse Points färben Allgemeine Java-Themen 7
C Prüfen ob sich ein Punkt innerhalb einer Kugel befindet (Java3D,nicht-lineare GLS) Allgemeine Java-Themen 5
J Regulärer Ausdruck - Der Punkt und der Zeilenumbruch Allgemeine Java-Themen 6
D Regular Expression Mit Punkt und Zahl Allgemeine Java-Themen 4
G Mehr als drei Nullen nach dem Punkt? Allgemeine Java-Themen 8
G split() mit komma/punkt funktioniert nicht Allgemeine Java-Themen 16
A Textfeld prüfen, ob ein Punkt eingegeben wurde Allgemeine Java-Themen 8
@ RegEx: Alle Sonderzeichen ausser dem Punkt Allgemeine Java-Themen 4
R komma oder punkt akzeptieren Allgemeine Java-Themen 5
C enum Strings mit punkt ? Allgemeine Java-Themen 3
M punkt-linie Allgemeine Java-Themen 2
P Punkt berechnen Allgemeine Java-Themen 4
E Berechnung des Schnittpunktes von zwei Geraden Allgemeine Java-Themen 1
V Schnitt von 2 Geraden Allgemeine Java-Themen 14

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben