맨하탄에서 점과 선 사이의 가장 가까운 거리

Question

주어진 지점에서 가장 작은 이미지에 그려지는 선분에서 점을 찾고 싶습니다. Manhattan distance.

명백한 방법은 선분의 픽셀을 얻고 각 픽셀에 대해 거리를 계산하여 최소값을 얻는 것입니다. 하지만 이보다 더 잘 할 수 있습니까?

Answer 1

이것은 검색 문제입니다. 당신이 시점에서 시작하여 breadth first search을 적용하면 선 픽셀을 칠 때까지 커집니다. 모든 픽셀에 대한 아이들 상태는 오른쪽 - 왼쪽 - 아래쪽 이웃이어야합니다. 맨하탄 거리는 목표의 깊이 만이 아닙니다.

편집 : 빠른 검색을 위해 몇 가지 휴리스틱을 추가해야합니다. 모든 라인 픽셀이 시점의 왼쪽에있는 경우. right을 방문 할 필요가 없습니다. 선의 각도는 상태를 추가로 줄이기 위해 고려해야 할 또 다른 사항입니다.