[🐣질문] 점에서 직선까지 가장 가까운 점 구하기 문제 질문좀~~*!@#&#$%*#

[루돌프돌프(jfczvkhgdy2y)]

안녕들 하신가

지금 여차저차 유니티 Navmesh써서 패스 구하고 에이전트로 이동하는건 해결했어.

왠지 수학교과서같은 질문이지만

k개의 코너점이 순차적으로 이어진 NavmeshPath(검정색 선)가 있을 때,

임의의 점(파란점)으로 부터, NavmeshPath에 가장 가까운 지점(빨간점)을 구하고

그 때의 빨간 점이 놓인 직선 구간 [n, n+1](단, n < k)을 구하고 싶어졌어.

예를 들어서 지금 점 5개로 이루어진 검정색 navmeshpath가 있고 (구간집합 = {[0-1],[1-2],[2-3],[3-4]}, 점 집합 = {p0, p1, ..., p4})

파란 점에서 가장 가까운 navmeshpath 구간과 그 구간 선분에 수선의 발을 내린 지점을 구하고 싶은거임.

지금 그림과 같은 상황이면 답은 [2-3] 구간과 빨간점의 위치가 되겠지.

당장 생각나는 방법은 input(파란점)이 입력 되었을 때

1. 파란점에서 모든 구간에 벡터프로젝션

2. 벡터프로젝션 성공한 구간들 중 거리가 가장 짧은 것 선택.

근데 이 방법은 요청이 있을 때 마다 모든 구간에 대해 조회하는건데 왠지 이건 update문에서 돌려야 해서 좀 무거울 것 같아서

미리 navMeshPath가 생성되었을 때 캐싱해서 효율적으로 구간 선택을 할 수 있는 알고리즘이 필요할 것 같은데 뭔지 모르겠단말이야...

도움 부탁드립니다.....

댓글에 각 선분 중점에서 가까운 순서로 선택이 안되는 경우는 이런게 있을 것 같아

[거붓(ggp02217)]

그래서 AB직선에서 가장 가까운 점 구하기 묻는거지?

[루돌프돌프(jfczvkhgdy2y)]

그거랑 동시에 여러개 직선 중 가장 가까운 직선 구하기임!

[거붓(ggp02217)]

A점과 B점의 이차방정식을 구해서 점들 x와y을 입력해 0에 가까운 걸 구하면 될껄?

[루돌프돌프(jfczvkhgdy2y)]

앗 좀 더 자세히 알려줄 수 있음 ㅜㅜ??

[거붓(ggp02217)]

A가 2,4 B가 6,9 라고 하자, 여기서 이차함수를 구할려면 x와y중에서 1로 만들어야함, 그러면 A를 기준으로 1,2 가 되고 함수는 y = a(x-1)^2 +2 가 됌, 여기서 B를 입력하면 9 = 25a +2, a = 7/25가 됌 즉, 두점의 이차방정식은 y = 7/25(x-1)^2+2 가 되니... 여기서 랜덤한 xy를 넣으면 됌

[거붓(ggp02217)]

주의할게 처음 계산하는거라 틀릴 가능성이 높음 조심하셈

[루돌프돌프(jfczvkhgdy2y)]

x와y중에서 1로 만들어야함 이게 점을 둘중 하나가 1이 되도록 이동하는게 아니고 벡터에 상수를 곱하라는거지??

[거붓(ggp02217)]

해깔리니 글써서 코드올림 ㄱㄷ

[루돌프돌프(jfczvkhgdy2y)]

오 매우감사 ㅜㅜㅜㅜ

[루돌프돌프(jfczvkhgdy2y)]

네네 맞습니다! [0, 1] 과 [2, 3]에서 [2,3]의 거리가 더 작으므로 [2,3] 구간이 최종 결과값이 됩니다.

[루돌프돌프(jfczvkhgdy2y)]

오오 감사합니다!!

[거붓(ggp02217)]

https://m.dcinside.com/board/game_dev/108776

[정공개발자(firetruck4545)]

(p0 + p1) / 2, (p1 + p2) /2, ... , (pn + pn+1) / 2 중에 파란점의 좌표와 거리가 제일 가까운게 정답 아닐까 싶어서 반례를 생각해보고 있는데 잘 모르겠다

[정공개발자(firetruck4545)]

반례가 있네 이 방법은 안되겠다

[루돌프돌프(jfczvkhgdy2y)]

그래도 한번 더 생각해보게 됐지 고마워!