직선의 최단거리에 있는 점은 직선에 수직인 직선위에 있는 점이다.
두개의 직선을 구한다음 교점을 구하면 된다.
직선의 공식은 ax + by = c이다.
여기서 직선에 수직인 직선은 다음과 같다.
-bx + ay = c
점1(x1, y1), 점2(x2, y2)를 지나는 ax + by = c1 직선의 A, B, C는 다음과 같이 구한다.
A = a = y2 - y1
B = b = x1 - x2
C는 Ax + By이므로 C = c1 = a*x1 + b*y1
점 (x0, y0)을 지나가는 경우는
-bx0 + ay0 = c2이다.
-bx0 + ay0 = c2 직선에 수직이고 점 (x0, y0)을 지나는 직선의 A, B, C는 다음과 같이 구한다.
A = -b
B = a
C = c2 = A*x0 - B*y0 = -b*x0 + a*y0
두개의 직선은 다음과 같다.
a*x1 + b*y1 = c1
-b*x0 + a*y0 = c2
그러므로, 두 직선의 교점이 최단거리인 직선위에 있는점은 다음과 같이 구한다.
테스트 코드
다음과 같은 직선이 있다.-x -2y + 3 = 0
직선을 지나는 점 p1, p2는 다음과 같다.
p1 = (-1, 2)
p2 = (3, 0)
점은 다음의 위치에 있다.
p = (2, 2)
직선위에 최단거리 점은 다음과 같이 나와야 한다.
result = (1.4, 0.8)
#include "stdafx.h"
#include <algorithm>
class Point2
{
public:
float x, y;
Point2() : x(0.0f), y(0.0f)
{
}
Point2(float x, float y) : x(x), y(y)
{
}
const float& operator[] (int i) const
{
return ((&x)[i]);
}
float& operator[] (int i)
{
return ((&x)[i]);
}
Point2& operator =(const Point2& v)
{
x = v.x;
y = v.y;
return (*this);
}
Point2 operator +(const Point2& v) const
{
return Point2(x + v.x, y + v.y);
}
Point2 operator *(float num) const
{
return Point2(x * num, y * num);
}
};
Point2 ClosestPointOnLine(const Point2& p1, const Point2& p2, const Point2& p)
{
float A1 = p2.y - p1.y;
float B1 = p1.x - p2.x;
float C1 = A1*p1.x + B1*p1.y;
float C2 = -B1*p.x + A1*p.y;
float det = A1*A1 + B1*B1;
float cx = 0;
float cy = 0;
if(det != 0)
{
cx = (float)((A1*C1 - B1*C2)/det);
cy = (float)((A1*C2 + B1*C1)/det);
}
else
{
cx = p.x;
cy = p.y;
}
return Point2(cx, cy);
}
void testClosestPosition()
{
//line
Point2 p1 = Point2(-1 , 2);
Point2 p2 = Point2(3 , 0);
//point
Point2 p = Point2(2, 2);
Point2 res = ClosestPointOnLine(p1, p2, p);
//res = (1.4, 0.8)
}
#include <algorithm>
class Point2
{
public:
float x, y;
Point2() : x(0.0f), y(0.0f)
{
}
Point2(float x, float y) : x(x), y(y)
{
}
const float& operator[] (int i) const
{
return ((&x)[i]);
}
float& operator[] (int i)
{
return ((&x)[i]);
}
Point2& operator =(const Point2& v)
{
x = v.x;
y = v.y;
return (*this);
}
Point2 operator +(const Point2& v) const
{
return Point2(x + v.x, y + v.y);
}
Point2 operator *(float num) const
{
return Point2(x * num, y * num);
}
};
Point2 ClosestPointOnLine(const Point2& p1, const Point2& p2, const Point2& p)
{
float A1 = p2.y - p1.y;
float B1 = p1.x - p2.x;
float C1 = A1*p1.x + B1*p1.y;
float C2 = -B1*p.x + A1*p.y;
float det = A1*A1 + B1*B1;
float cx = 0;
float cy = 0;
if(det != 0)
{
cx = (float)((A1*C1 - B1*C2)/det);
cy = (float)((A1*C2 + B1*C1)/det);
}
else
{
cx = p.x;
cy = p.y;
}
return Point2(cx, cy);
}
void testClosestPosition()
{
//line
Point2 p1 = Point2(-1 , 2);
Point2 p2 = Point2(3 , 0);
//point
Point2 p = Point2(2, 2);
Point2 res = ClosestPointOnLine(p1, p2, p);
//res = (1.4, 0.8)
}
참고)
https://ericleong.me/research/circle-line/