[기타] 점이 삼각형 안에 있는지 확인하기

문제

프로그램은 세 좌표의 값이 필요합니다.

> P1 (x1, y1)
> P2 (x2, y2)
> P3 (x3, y3)

다른 좌표 P (x, y)와이 점이 위의 3 점에서 형성된 삼각형 내부에 있는지 여부를 결정합니다.

 

해결

이를 수행하는 올바른 방법은 삼각형의 세 점이 주어지는 네 번째 점의 barycentric coordinates을 계산하는 것입니다. 이들을 계산하는 수식은 “중심 좌표로 변환”단원 끝 부분에 나와 있습니다. 그러나 여기서보다 적은 수학적 설명을 제공하기를 바랍니다.

단순성을 위해 struct x, y 값을 가진 struct가 있다고 가정합니다. 포인트를 다음과 같이 정의했습니다.

point p1(x1, y1); 
point p2(x2, y2); 
point p3(x3, y3); 

point p(x,y); //You are checking if this point lies in the triangle.

이제 일반적으로 알파, 베타, 감마라고하는 중심 좌표가 다음과 같이 계산됩니다.

float alpha = ((p2.y - p3.y)*(p.x - p3.x) + (p3.x - p2.x)*(p.y - p3.y)) / 
				((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y)); 
float beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) / 
				((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y)); 
float gamma = 1.0f - alpha - beta;

알파, 베타 및 감마가 모두 0보다 큰 경우 점 p는 점 p1, p2 및 p3으로 이루어진 삼각형 내에 있습니다.

이것의 뒤에있는 설명은 삼각형 내부의 점이 삼각형의 점과 세 개의 계수 ([0,1] 범위의 각 점에 하나씩)를 사용하여 설명 될 수 있다는 것입니다.

p = (alpha)*p1 + (beta)*p2 + (gamma)*p3

이 함수를 다시 배열하면 중심 좌표를 계산하는 수식이 주어 지지만 그렇게해야 할 단계가 문제의 범위를 벗어날 수 있다고 생각합니다. 그것들은 위키피디아 페이지에 링크되어 있습니다.

점 p가 세 점에 의해 기술 된 영역 내에 있도록 각 계수는 0보다 커야합니다.

 

 

Reference

https://codeday.me/ko/qa/20190316/79032.htmlhttps://codeday.me/ko/qa/20190316/79032.html

수학 – 점이 삼각형 안에 있는지 결정 - 코드 로그

https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle

How to determine if a point is in a 2D triangle?

https://codeday.me/ko/qa/20190417/352960.html

알고리즘 – 점이 2D에서 많은 수의 삼각형 안에 있는지 여부를 효율적으로 검사합니다. - 코드 로그