Distancia más corta entre un punto y un segmento de recta
Necesito una función básica para encontrar la distancia más corta entre un punto y un segmento de línea. Siéntase libre de escribir la solución en el idioma que desee; Puedo traducirlo a lo que estoy usando (Javascript).
EDITAR: Mi segmento de línea está definido por dos puntos finales. Entonces mi segmento de línea ABestá definido por los dos puntos A (x1,y1)y B (x2,y2). Estoy tratando de encontrar la distancia entre este segmento de línea y un punto C (x3,y3). Mis habilidades de geometría están oxidadas, por lo que los ejemplos que he visto son confusos, lamento admitirlo.
Eli, el código que has elegido es incorrecto. Un punto cerca de la línea en la que se encuentra el segmento pero lejos de un extremo del segmento se juzgaría incorrectamente cerca del segmento. Actualización: La respuesta incorrecta mencionada ya no es la aceptada.
Aquí hay un código correcto, en C++. Se supone una clase de vector 2D class vec2 {float x,y;}, esencialmente, con operadores para sumar, restar, escalar, etc., y una función de distancia y producto escalar (es decir x1 x2 + y1 y2).
float minimum_distance(vec2 v, vec2 w, vec2 p) {
// Return minimum distance between line segment vw and point p
const float l2 = length_squared(v, w); // i.e. |w-v|^2 - avoid a sqrt
if (l2 == 0.0) return distance(p, v); // v == w case
// Consider the line extending the segment, parameterized as v + t (w - v).
// We find projection of point p onto the line.
// It falls where t = [(p-v) . (w-v)] / |w-v|^2
// We clamp t from [0,1] to handle points outside the segment vw.
const float t = max(0, min(1, dot(p - v, w - v) / l2));
const vec2 projection = v + t * (w - v); // Projection falls on the segment
return distance(p, projection);
}
EDITAR: Necesitaba una implementación de Javascript, así que aquí está, sin dependencias (ni comentarios, pero es una adaptación directa de lo anterior). Los puntos se representan como objetos con xatributos y.
function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegmentSquared(p, v, w) {
var l2 = dist2(v, w);
if (l2 == 0) return dist2(p, v);
var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
t = Math.max(0, Math.min(1, t));
return dist2(p, { x: v.x + t * (w.x - v.x),
y: v.y + t * (w.y - v.y) });
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }
EDITAR 2: necesitaba una versión de Java, pero lo más importante es que la necesitaba en 3D en lugar de 2D.
float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) {
float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2);
if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1);
float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist;
t = constrain(t, 0, 1);
return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1));
}
Aquí, en los parámetros de la función, <px,py,pz>está el punto en cuestión y el segmento de recta tiene los puntos finales <lx1,ly1,lz1>y <lx2,ly2,lz2>. La función dist_sq(que se supone que existe) encuentra el cuadrado de la distancia entre dos puntos.
Aquí está el código completo más simple en Javascript.
x, y es su punto objetivo y x1, y1 a x2, y2 es su segmento de línea.
ACTUALIZADO: solución para el problema de la línea de longitud 0 en los comentarios.
function pDistance(x, y, x1, y1, x2, y2) {
var A = x - x1;
var B = y - y1;
var C = x2 - x1;
var D = y2 - y1;
var dot = A * C + B * D;
var len_sq = C * C + D * D;
var param = -1;
if (len_sq != 0) //in case of 0 length line
param = dot / len_sq;
var xx, yy;
if (param < 0) {
xx = x1;
yy = y1;
}
else if (param > 1) {
xx = x2;
yy = y2;
}
else {
xx = x1 + param * C;
yy = y1 + param * D;
}
var dx = x - xx;
var dy = y - yy;
return Math.sqrt(dx * dx + dy * dy);
}
ACTUALIZADO: versión Kotlin
fun getDistance(x: Double, y: Double, x1: Double, y1: Double, x2: Double, y2: Double): Double {
val a = x - x1
val b = y - y1
val c = x2 - x1
val d = y2 - y1
val lenSq = c * c + d * d
val param = if (lenSq != .0) { //in case of 0 length line
val dot = a * c + b * d
dot / lenSq
} else {
-1.0
}
val (xx, yy) = when {
param < 0 -> x1 to y1
param > 1 -> x2 to y2
else -> x1 + param * c to y1 + param * d
}
val dx = x - xx
val dy = y - yy
return hypot(dx, dy)
}
Esta es una implementación hecha para SEGMENTOS DE LÍNEA FINITA, no para líneas infinitas como parecen ser la mayoría de las otras funciones aquí (es por eso que hice esto).
Implementación de la teoría de Paul Bourke .
Pitón:
def dist(x1, y1, x2, y2, x3, y3): # x3,y3 is the point
px = x2-x1
py = y2-y1
norm = px*px + py*py
u = ((x3 - x1) * px + (y3 - y1) * py) / float(norm)
if u > 1:
u = 1
elif u < 0:
u = 0
x = x1 + u * px
y = y1 + u * py
dx = x - x3
dy = y - y3
# Note: If the actual distance does not matter,
# if you only want to compare what this function
# returns to other results of this function, you
# can just return the squared distance instead
# (i.e. remove the sqrt) to gain a little performance
dist = (dx*dx + dy*dy)**.5
return dist
AS3:
public static function segmentDistToPoint(segA:Point, segB:Point, p:Point):Number
{
var p2:Point = new Point(segB.x - segA.x, segB.y - segA.y);
var something:Number = p2.x*p2.x + p2.y*p2.y;
var u:Number = ((p.x - segA.x) * p2.x + (p.y - segA.y) * p2.y) / something;
if (u > 1)
u = 1;
else if (u < 0)
u = 0;
var x:Number = segA.x + u * p2.x;
var y:Number = segA.y + u * p2.y;
var dx:Number = x - p.x;
var dy:Number = y - p.y;
var dist:Number = Math.sqrt(dx*dx + dy*dy);
return dist;
}
Java
private double shortestDistance(float x1,float y1,float x2,float y2,float x3,float y3)
{
float px=x2-x1;
float py=y2-y1;
float temp=(px*px)+(py*py);
float u=((x3 - x1) * px + (y3 - y1) * py) / (temp);
if(u>1){
u=1;
}
else if(u<0){
u=0;
}
float x = x1 + u * px;
float y = y1 + u * py;
float dx = x - x3;
float dy = y - y3;
double dist = Math.sqrt(dx*dx + dy*dy);
return dist;
}
En mi propio hilo de preguntas, ¿cómo calcular la distancia 2D más corta entre un punto y un segmento de línea en todos los casos en C, C#/.NET 2.0 o Java? Me pidieron que pusiera una respuesta en C# aquí cuando encontrara una: así que aquí está, modificada de http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :
//Compute the dot product AB . BC
private double DotProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] BC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
BC[0] = pointC[0] - pointB[0];
BC[1] = pointC[1] - pointB[1];
double dot = AB[0] * BC[0] + AB[1] * BC[1];
return dot;
}
//Compute the cross product AB x AC
private double CrossProduct(double[] pointA, double[] pointB, double[] pointC)
{
double[] AB = new double[2];
double[] AC = new double[2];
AB[0] = pointB[0] - pointA[0];
AB[1] = pointB[1] - pointA[1];
AC[0] = pointC[0] - pointA[0];
AC[1] = pointC[1] - pointA[1];
double cross = AB[0] * AC[1] - AB[1] * AC[0];
return cross;
}
//Compute the distance from A to B
double Distance(double[] pointA, double[] pointB)
{
double d1 = pointA[0] - pointB[0];
double d2 = pointA[1] - pointB[1];
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(double[] pointA, double[] pointB, double[] pointC,
bool isSegment)
{
double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB);
if (isSegment)
{
double dot1 = DotProduct(pointA, pointB, pointC);
if (dot1 > 0)
return Distance(pointB, pointC);
double dot2 = DotProduct(pointB, pointA, pointC);
if (dot2 > 0)
return Distance(pointA, pointC);
}
return Math.Abs(dist);
}
Soy @SO para no responder, sino hacer preguntas, así que espero no obtener millones de votos negativos por algunas razones, excepto por la construcción de críticas. Solo quería (y me animaron) compartir las ideas de otra persona, ya que las soluciones en este hilo están en algún lenguaje exótico (Fortran, Mathematica) o alguien las ha etiquetado como defectuosas. El único útil (de Grumdrig) para mí está escrito en C++ y nadie lo etiquetó como defectuoso. Pero faltan los métodos (punto, etc.) que se llaman.
