포인트가 도로에 있는지 결정합니다

Question

도로를 설명하는 폴리 라인이 있고 모든 부품의 도로 너비를 알고 있다면 포인트가 도로에 있는지 확인하는 데 사용할 수있는 알고리즘이 있습니까? 선 자체의 너비는 1px의 폭이 있기 때문에이 작업을 수행하는 방법을 완전히 확신하지 못합니다.

감사해요,

제프

Answer 1

선으로의 지점의 최소 거리를 찾으십시오 (라인에 수직 인 벡터가 될 것입니다). P0이 도로 세그먼트의 첫 번째 지점 인 경우 실제 계산은 도로 세그먼트 벡터이고 W는 P0에서 문제의 지점까지 벡터입니다. 폴리 라인의 각 모서리를 반복해야합니다. 거리가 해당 세그먼트의 너비보다 작 으면 도로에 "위"됩니다.

d = |v x w| / |v|

모서리는 둥근 (일정한 반경) 또는 각도로 취급하는지에 따라 까다로울 수 있습니다.

Answer 2

아마도 각 라인 세그먼트를 취하고 선 세그먼트의 사각형을 만들고 너비의 사각형을 만들고 사각형/포인트 충돌 알고리즘을 사용하여 사각형에 포인트가 포함되어 있는지 확인할 수 있습니다. 좋은 알고리즘은 너비 = 1 시나리오를 설명합니다.이 시나리오는 단순히 라인 세그먼트의 역 함수를 빌드하고 y-1 (point.y)이 line_segment.x1과 line_segment.x2 사이의 x인지 확인해야합니다.