특정 점을 둘러싼 경계 폴리곤 결정

Question

저는 폴리곤에만 점이 포함되도록 다른 점 집합 (세트 B)에서 특정 점 집합 (세트 A) 주위의 경계 폴리곤을 결정하는 방법을 알아 내려고 노력했습니다. 단순함을 위해, 다각형이 볼록하다고 가정 할 수 있으며, 집합 A는 2 점만 포함하고 솔루션은 주어진 데이터로부터 존재할 것입니다.

예를 들어, 주어진 : these points, 빨간 포인트에서 파란색 점 주위에 다각형을 만들려합니다. this. 이것은 가장 큰 각도의 다음 점을 찾아 파란색 점을 통과하지 않고 수행 할 수 있습니다. 그러나 결과는 this과 같이 너무 작지 않기를 바랍니다.

이 문제를 해결하기위한 제안이나 알고리즘은 무엇입니까?

Answer 1

모든 점 (적색과 청색)에 대해 삼각형을 계산하면 파란색 꼭지점이 포함 된 삼각형이 필요한 영역의 첫 번째 근사를 형성하는 것처럼 보입니다. 이 근사치는 일반적으로 오목하므로 "귀"를 잘라야합니다.

결과가 너무 작 으면 바깥 쪽 테두리 삼각형의 세 번째 꼭지점을 볼록 함을 위반하지 않으면 추가 할 수 있습니다.