Блог пользователя Harolinch

closest point from a a given point to a line
Автор Harolinch, история, 6 лет назад, По-английски

having a point p1(x0, y0) and want to find the projection of p1 on the line L given in form ax + by + c = 0

let the projection point is p2(x1, y1), so how to find x1 and y1 ?

i have a code segment which do so but i don't understand it, so can someone help me to understand it ?

the code is 

point closest_point (line l, point p)
{
    double k = (l.a * p.x + l.b * p.y + l.c) / (l.a * l.a + l.b * l.b);
    return point (p.x - l.a * k, p.y - l.b * k);
}
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 10   Проголосовать: нравится +1 Проголосовать: не нравится

The projection is simply the intersection point of two perpendicular straight lines:

ax + by + c = 0

and

b(x - x0) - a(y - y0) = 0

where the latter line passes through (x0, y0). Instead of solving the two linear equations for x and y directly to compute the intersection point, your code segment uses a parametric approach. As the direction of the normal line is [a b], the second equation is replaced with two parametric equations in terms of the parameter k:

x = x0 - ka

y = y0 - kb

Substituting for x and y from these two parametric equations in the first equation gives one equation in the parameter k

a(x0 - ka) + b(y0 - kb) + c = 0

whose solution is the desired value of k at the intersection point

k = (ax0 + by0 + c) / (a2 + b2)

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i saw this equation b(x - x0) - a(y - y0) = 0 before on the internet but i didn't understand it, where it comes from, can you explain it to me.

    what i Know about my code segment is ...

    the the distance between a point and line is .

    the norm of line is .

    ==> i don't know why this true ? (can you explain it to me?

    can you continue on this ?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 18   Проголосовать: нравится 0 Проголосовать: не нравится

      The second equation is derived from the fact that the two straight lines:

      are perpendicular for any |a| + |b| > 0, and any c and d, where a, b, c and d are real numbers.

      The proof is simple as the normal vectors of and are

      The dot product of the two normal vectors is

      Therefore, the two lines are perpendicular. Note that and have the same norm, and can be normalized, i.e. transformed to orthonormal vectors, by dividing each component by .

      k is just the parameter used in the two parametric equations to find the intersection point as mentioned before.

      It can be shown from the two parametric equations that

      b(x - x0) = a(y - y0) =  - kab

      Therefore,

      b(x - x0) - a(y - y0) = 0

      Finally, if orthonormal vectors are used in the parametric equations, then k = d at the intersection point of and , where d is the minimum distance between the point (x0, y0) and .

      The following is an update for closest_point() when orthonormal vectors are used. 

      #include <bits/stdc++.h>

using namespace std;

typedef long double ldbl;

class point
{
    ldbl x, y;

    friend class line;

public:

    point( ldbl X = 0, ldbl Y = 0 ) : x( X ), y( Y ) {}

    friend istream& operator >> ( istream& in, point& p )
    {
        return in >> p.x >> p.y;
    }

    friend ostream& operator << ( ostream& out, const point& p )
    {
        return out << p.x << ' ' << p.y;
    }
};

class line
{
    ldbl a, b, c;

public:

    friend istream& operator >> ( istream& in, line& l )
    {
        in >> l.a >> l.b >> l.c;

        ldbl norm = 1.0 / abs( complex< ldbl >( l.a, l.b ) );

        l.a *= norm, l.b *= norm, l.c *= norm;

        return in;
    }

    point closest_point( const point& p ) const
    {
        ldbl d = a * p.x + b * p.y + c;

        return point( p.x - d * a, p.y - d * b );
    }
};

int main()
{
    line l; point p;

    cin >> l >> p, cout << l.closest_point( p );
}

      Sample Test

      Input:

      3 4 -5 0 0

      Output:

      0.6 0.8

      =====

      Used: 15 ms, 140 KB

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        thanks so much for your help, i'm somehow trying to put all together,

        you seemed to understand it well, and that's why can you help me understand what is the relation between A and B and C in line equation Ax + By + C = 0.

        seems there are a lot of relations, one of them is the slop and the slop of perp. what else could you show me ?

        → Ответить