삼각형의 어떤 점을 찾는 가장 빠른 방법 2D

Question

2D에서 삼각형 안의 어떤 점 (가장 자리가 아닌 점)을 찾는 가장 빠른 방법이 필요합니다. 어떤 도움이 필요합니까?

Answer 1

삼각형을 점으로 표시하면 모든 좌표 그래서 Steve Jessop의 대답은 거의 최적입니다.

실제로해야 할 일은 한 지점에서 시작하여 다른 두 사람에게 제한된 양만큼 충돌시키는 것입니다. 그것이 평균화가 달성하는 것이지만 매우 구체적인 방법입니다.

추가가 빠릅니다. 플랫폼 및 컴파일러에 따라 부서가 느릴 수 있습니다. 변수는 정수 컴파일러가 제대로 예정된 경우입니다 비트의 변화에 ​​분열을 최적화해야하는 경우

xm = (x0 + (x1 + x2)/2)/2 
ym = (y0 + (y1 + y2)/2)/2 

:이 버전 평균 이상 어떤 일을 선택할 것 현대 ARM 코어에 예를 들어

, ARM에서는 무료입니다. 변수가 부동 또는 복소수이면 컴파일러는 간단한 지수 감소에 최적화해야합니다. 부동 소수점 분할은 상대적으로 느린 것으로 알려져 있습니다.

궁극적으로 테스트하고 확인하십시오. 상대적으로 낮은 수준의 코드 최적화를 수행하지 않는 한 차이점을 보지 못할 것입니다. 다른 한편으로, 만약 당신이 꽉 안쪽 루프 에서이 사용하고 있습니다.

이것이 작동하는 이유에 대한 약간의 직관을 제공하려면 : 먼저 (x1, y1)과 (x2, y2)으로 형성된 선분의 중간 점을 찾습니다. 그런 다음 에 의해 형성된 선분과 점과 (x0, y0) 사이의 중간 점을 찾습니다. 삼각형 다이어그램을 그려서 이렇게하면 즉시 작동한다는 것을 알 수 있습니다.

Answer 2

세 개의 정점 (중심)의 "평균"은 삼각형 안의 한 점이며, 다른 어떤 것과 마찬가지로 계산하는 것이 빠릅니다.

정점이 동일 직사각형 인 축퇴의 경우에만 가장자리에 있습니다. 이 경우 삼각형의 모든 점은 모서리에 놓여 있으므로 해결책이 없습니다.

Answer 3

또는 : 먼저 삼각형의 표면을 계산할 수 있습니다. 그러면 세 번째 다른 삼각형에 삼각형이 그려지는 두 번째 계산이 수행됩니다. 이 3 개의 부 극형의 표면이 더 큰 경우, 사용자의 점이 삼각형 영역 밖에 있습니다. 내가 무슨 뜻인지 알 겠어?

Answer 4

정점 A, B, C

벡터

AB = BA

AC = CA

P = A + t의 * AB + 유 *

AC

t, u - 범위 [0..1]의 모든 숫자 (임의?) 및 t + u < = 1