Geek Answers Handbook

How to find a point on the edge that is the closest point to another point

I am looking for a way to efficiently find a point on an edge that is the closest point to any other point.

Say I know two points that are the vertices of an edge. I can calculate the equation of the line that intersects these points.

What is the best way to calculate a point on the edge that is the closest point to any other point on the plane.

I would post an image, but I don't have enough reputation points.

+5
source share
4 answers

You have three areas to consider. The perpendicular approach for the middle zone:

enter image description here

For the other two zones, the distance is the distance to the end point of the nearest segment.

:

y[x] = m x + b


  m -> -((Ay - By)/(-Ax + By)), 
  b -> -((-Ax By + Ay By)/(Ax - By))

-1/

, A, :

  y[x] = (-Ax + By)/(Ay - By) x + (Ax^2 + Ay^2 - Ax By - Ay By)/(Ay - By)

, B, A B .

, , , x , y y [x]

, ?

, Ax & le; Bx ( , )

{x0, y0}

1)

 f[x0] =  (-Ax + By)/(Ay - By) x0 + (Ax^2 + Ay^2 - Ax By - Ay By)/(Ay - By)

y0.

y0 > f [x0], , - A.

2) Else, Calculate

g[x0] =  (-Bx + Ay)/(By - Ay) x0 + (Bx^2 + By^2 - Bx Ay - By Ay)/(By - Ay)

y0.

y0 < g [x0], , B.

3) " ", , ( :))

!

+6

, (x1, y1), (x2, y2), " " - (a, b). , , - (x, y).

enter image description here

. , , m1 * m2 = -1 (m1 m2 - ).

, , , - .

enter image description here

, :

  • x1 = x2, (x, y) = (x1, b).
  • y1 = y2, (x, y) = (a, y1).

Python ( , Python psudo-code):

def get_closest_point( x1,y1, x2,y2, a,b ):
    if x1==x2: return (x1,b)
    if y1==y2: return (a,y1)
    m1 = (y2-y1)/(x2-x1)
    m2 = -1/m1
    x = (m1*x1-m2*a+b-y1) / (m1-m2)
    y = m2*(x-a)+b
    return (x,y)
+15

, , . ?

, , . , , .

.

0

, . - , , , .

, (x1, y1), (x2, y2),

y = mx + b

( m b, )

, , - (p1, p2) , ..

(p1-x)^2 + (p2-y)^2     (equation I)


y = mx + b              (equation II)

II x. ; , I.

0

More articles:


All Articles