minimalen Abstand zwischen Punkt und LineSegment bzw. zwischen 2 LineSegments

[Elemental]

Hallo,
ich versuche gerade den Abstand zwischen einem Punkt und einem LineSegment, sowie den Abstand zwischen 2 LineSegments zu ermitteln.
Dabei habe ich festgestellt, dass meine Mathe-Kenntnisse sehr eingerostet sind, d.h. ich bekomme es nicht hin :frown:

Ich habe eine Klasse für einen Punkt und eine Klasse für ein LineSegment:

public class Coordinate
{
#region fields

private int _x;
private int _y;

#endregion

#region constructors

public Coordinate(int x, int y)
{
X = (int) x;
Y = (int) y;
}

#endregion

#region properties

public int X
{
get { return _x; }
set { _x = value; }
}

public int Y
{
get { return _y; }
set { _y = value; }
}

#endregion
}


public class LineSegment
{
#region fields

Coordinate _startPoint = null;
Coordinate _endPoint = null;

#endregion

#region constructors

public LineSegment(Coordinate startPoint, Coordinate endPoint)
{
_startPoint = startPoint;
_endPoint = endPoint;
}

#endregion

#region properties

public Coordinate StartPoint
{
get
{
return _startPoint;
}
}

public Coordinate EndPoint
{
get
{
return _endPoint;
}
}

#endregion
}


Den Abstand zweier Punkte krieg ich ja gerade noch hin:

public double Distance(Coordinates coord)
{
int dX = this.X - coord.X;
int dY = this.Y - coord.Y;
return Math.Sqrt(dX * dX + dY * dY);
}


Aber der Abstand eines Punkts zu einem LineSegment oder der Abstand von zwei LineSegments zueinander?
Wäre für etwas Hilfe sehr dankbar!

mfG
Elemental

[Elemental]

Habe im Internet jetzt eine Lösung für den Abstand eines Punktes zu einem LineSegment gefunden:

//Compute the distance from A to B
double Distance(System.Windows.Point pointA, System.Windows.Point pointB)
{
double d1 = pointA.X - pointB.X;
double d2 = pointA.Y - pointB.Y;

return Math.Sqrt(d1 * d1 + d2 * d2);
}

//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double LineToPointDistance2D(System.Windows.Point pointA, System.Windows.Point pointB, System.Windows.Point pointC, bool isSegment)
{
System.Windows.Vector vectorAB = new System.Windows.Vector(pointB.X - pointA.X, pointB.Y - pointA.Y);
System.Windows.Vector vectorAC = new System.Windows.Vector(pointC.X - pointA.X, pointC.Y - pointA.Y);
System.Windows.Vector vectorBA = new System.Windows.Vector(pointA.X - pointB.X, pointA.Y - pointB.Y);
System.Windows.Vector vectorBC = new System.Windows.Vector(pointC.X - pointB.X, pointC.Y - pointB.Y);

if (isSegment)
{
double dot1 = System.Windows.Vector.Multiply(vectorAB, vectorAC);
if (dot1 > 0)
return Distance(pointB, pointC);

double dot2 = System.Windows.Vector.Multiply(vectorBA, vectorBC);
if (dot2 > 0)
return Distance(pointA, pointC);
}
double dist = System.Windows.Vector.CrossProduct(vectorAB, vectorAC) / Distance(pointA, pointB);
return Math.Abs(dist);
}



Aber wie berechnet man den Abstand zwischen 2 LineSegments?

mfG
Elemental

[del_4901]

min2(LinePntDst, ...)

Ich würde auch die ifs mit cmov ersetzen and das sqrt am ende machen.

[Elemental]

min2(LinePntDst, ...)

Ich würde auch die ifs mit cmov ersetzen and das sqrt am ende machen.

Sorry, aber ich versteh nur "Bahnhof"! :confused:

edit:
Hmm, OK. Also die beiden EndPunkte des zweiten LineSegments mit dem ersten LineSegment vergleichen
Der kleinere Abstand ist dann der Abstand der LineSegments.

Aber was ist dein "cmov" ?

[Marscel]

Aber was ist dein "cmov" ?

Er meint wohl Conditional Move-Assembly statt eines regulären if-Statements. Das sollte dich unter C# aber eh nicht tangieren. ;)

[Elemental]

OK, jetzt zum eigentlichen Problem :biggrin:

Ich habe zwei Polygone, gegeben durch zwei Point-Collections.
Wenn ich den Abstand der beiden Polygone ermitteln will, dann vergleiche ich die Punkte des ersten Polygons mit den Punkten und LineSegments des zweiten Polygons und danach die LineSegments des ersten Polygons mit den Punkten des zweiten Polygons.

Der kleinste Abstand ist dann der Abstand der beiden Polygone. Richtig oder falsch? :confused:

[Monger]

Was ist denn eigentlich das Ziel? Willst du herausfinden ob die beiden Polygone kollidieren? Oder brauchst du den minimalen Abstand (der Kanten? des Mittelpunkts?) aus irgendeinem anderen Grund?

[Elemental]

Also die Software soll bei der Auswahl der richtigen Lotpaste für den Lotpastendruck in der Elektronikfertigung helfen.
D.h. ich habe eine Lochmaske bzw. eine Schablone für den Lotpastendruck. Jedes Loch in der Lochmaske ist ein Polygon. Ich muss jetzt den Abstand jedes Polygons zu seinem nächsten Nachbar ermitteln.

[Monger]

Ich wünschte, ich hätte hier eine Zeichenfläche im 3DCF...

Aber die Fragestellung ist schon ganz wesentlich für den Algorithmus. Wenn die Ausgangsfrage ist: "finde mir den Abstand zwischen den beiden Mittelpunkten zweier beliebiger Polygone", dann muss man sich erstmal fragen was denn überhaupt mit dem Mittelpunkt gemeint ist. Der geometrische Mittelpunkt? (Also der Punkt zu dem alle Punkte einen minimalen Abstand haben) Oder der Schwerpunkt? (In jede Richtung wird die gleiche Fläche abgedeckt)

Oder geht es darum, den minimalsten Abstand zwischen zwei Flächen zweier Polygone zu finden? Wenn das ein beliebiges Polygon ist - also auch eins was z.B. wie ein W geformt sein kann - und beide Polygone eng beeinander liegen, musst du eventuell wirklich den minimalen Abstand aller Flächen ausrechnen. Hässlich.

Je mehr Grundannahmen du über die Form deiner Polygone machen kannst, desto einfacher und performanter wird der Algorithmus.

[Elemental]

Ich brauche den minimalen Abstand der Polygone, nicht vom Mittelpunkt aus, sondern vom Rand!
Abhängig von der Größe der Polygone und dem Abstand zueinander ist nämlich, ob man teure oder billigere Lotpaste verwenden kann.

Eigentlich gibts es ja nur 3 Fälle, wie der minimale Abstand sein kann (siehe http://cgm.cs.mcgill.ca/~orm/mind2p.html ):
- Ecke zu Ecke
- LineSegment zu LineSegment
- Ecke zu LineSegment

Müsste doch mit einem Ansatz von ein paar Posts weiter oben funktionieren:

Wenn ich den Abstand der beiden Polygone ermitteln will, dann vergleiche ich die Punkte des ersten Polygons mit den Punkten und LineSegments des zweiten Polygons und danach die LineSegments des ersten Polygons mit den Punkten des zweiten Polygons.

[del_4901]

Sind die Polys konvex oder konkav?
Line Line ist eh nur interessant wenn beide parallel sind.
Aber mal davon abgesehen sagt mir mein Bauchgefühl, dass man das elegant mit homgenen koordinaten lösen kann.

[Elemental]

Die Polygone sind definiert in einem Gerber File und können beliebiges Aussehen haben.

Ein Beispiel, wie sowas aussehen kann:
http://www.meatandnetworking.com/wp-content/uploads/2.png

[Elemental]

Also den Abstand zweier Polygone krieg ich jetzt schon hin, aber gibt's eine einfache Möglichkeit, damit ich nicht den Abstand von jedem zu jedem ermitteln muss?
Brauch ja nur den Abstand zum nächsten Nachbar...

[del_4901]

Broadphase: Bucketing, Quadtree, kd-tree
Narrowphase: Sweep and Prune
alles mit AABB versteht sich.

[Elemental]

Ähm, ja... :confused:

[ux-3]

Einwurf: Der minimale Abstand zweier Stecken muss nicht von den Endpunkten ausgehen.

[Elemental]

Einwurf: Der minimale Abstand zweier Stecken muss nicht von den Endpunkten ausgehen.

Mist, stimmt! :rolleyes:

[del_4901]

Einwurf: Der minimale Abstand zweier Stecken muss nicht von den Endpunkten ausgehen.
Ist irrelevant wenn die LineSegments nicht ueberlappen, was hier der Fall ist.