선분과 한 점과의 최단거리 알고리즘

선분과 한 점과의 최단거리는 구해서 어디다 쓸까?

 
캐릭터가 선로와 출동하는지 판단하는 기능을 구현할 때,
공간 분할 기법을 사용하여 검색 범위를 줄일 때 등이 있다.
 
 
선분과 점의 위치 관계를 분석하여 3가지 예외상황으로 나누어 풀 수 있습니다.
 
1.     점 P에서 선분 AB로 수선을 그릴 수 있을 때


2.     점 P에서 선분 AB로 수선을 그릴 수 없으며,
        점 P가 점 A랑 더 가까울 때


3.     점 P에서 선분 AB로 수선을 그릴 수 없으며,
        점 P가 점 B랑 더 가까울 때
 
이 3가지 상황은 AP벡터를 AB벡터에 내적을 이용한 정사영시켜 구분할 수있습니다.
 
AP 벡터와 AB 벡터를 정사영시킨 벡터가 길이 0이하라면
점 P는 선분 AB에 수선을 그을 수 없는 상태입니다.
 
만약 길이가 선분 AB의 길이보다 작거나 같은 양수라면
선분 AB에 수선을 그려서 거리를 측정할 수 있습니다.
 
만약 길이가 선분AB의 길이보다 크다면 점 B와의 거리가
선분 AB와의 거리가 됩니다.
 

#include <iostream>
#include <cmath>

using namespace std;

struct Vector {
	double x;
	double y;
};

double length(Vector a) {
	return sqrt(a.x * a.x + a.y * a.y);
}

double getDistance(Vector a, Vector b) {
	double dx = b.x - a.x;
	double dy = b.y - a.y;
	return length({ dx, dy });
}

double dot(Vector a, Vector b) {
	return a.x * b.x + a.y * b.y;
}

double getSegmentDistance(Vector a, Vector b, Vector p) {
	Vector line = { b.x - a.x, b.y - a.y };
	double lineLength = length(line);

	if (lineLength == 0) return getDistance(a, p);

	double projection = dot({ p.x - a.x, p.y - a.y }, { b.x - a.x, b.y - a.y }) / lineLength;

	if (projection <= 0) return getDistance(a, p);
	else if (projection >= lineLength) return getDistance(b, p);
	else {

		Vector projectionVector = {
			a.x + line.x * projection / lineLength,
			a.y + line.y * projection / lineLength
		};

		return getDistance(projectionVector, p);
	}
}

int main() {
	Vector a, b, p;

	cin >> a.x >> a.y;
	cin >> b.x >> b.y;
	cin >> p.x >> p.y;

	std::cout << getSegmentDistance(a, b, p);

	return 0;
}

 
 
참고 블로그
https://blog.typi.kr/posts/algorithm-segment-distance/