0
Polygon2D 클래스를 기반으로하는 이중 연결 목록을 검색 및 수정해야하며 충돌 감지와 같은 다양한 유틸리티를위한 게임 엔진에 사용되며 그래픽 모양을 정의 할 수 있습니다. 텍스처 좌표. 다각형은 오목하거나 볼록 할 수 있어야하지만 교차 할 수는 없습니다.2D 다각형에 점 추가
다각형과 교차하지 않도록 점을 삽입하는 방법을 고민 중입니다. 내가 뭘했는지는 머리 부분에서 시작하여 별도의 방향으로 반복하는 두 개의 노드 포인터를 사용하여 삽입 할 지점에 가장 가까운 가장자리를 검색하는 것입니다. 둘 중 하나의 "다음"노드가 다른 포인터 일 때, 검색은 완료되고 포인트는 둘 사이에 삽입됩니다. 그렇지 않으면 앞으로 반복하는 노드는 지금까지 가장 가까운 점에 도달 할 때까지 이동하고 (다음 노드가 다른 포인터 인 경우 중지됨) "뒤로"반복하는 노드는 동일한 작업을 수행합니다.
불행하게도, 앞쪽 반복 포인터 앞의 가장자리 나 뒤쪽 반복 포인터 뒤의 가장자리가 새 점을 삽입 할 때 생성 된 새 가장자리와 교차하는 경우에도 교차가 발생합니다. 그 후 더 많은 교차로가 쉽게 빠질 수 있습니다.
Here is the insert method's code.
이 알고리즘을 개선하면서도 계속 O (n)로 유지하거나 더 좋은 방법이 있습니까?
"findClosest [Edge] (vec2 pt)"검색은 약간 수정 된 알고리즘 버전을 사용하지만 더 많은 메모리를 사용하지 않고 이러한 검색을 수행 할 수있는 효과적인 방법이 필요합니다. 시각.
나는 당신이 성취하려는 것을 얻는 지 확신하지 못합니다. 새 점을 삽입 할 때 점에 가장 가까운 ** 모서리 **에 자동으로 삽입해야합니다. 이것은 하나의 가장자리를 제거하고 두 개의 새로운 가장자리로 대체합니다. 맞습니까? 링크하는 코드는 모서리가 아닌 꼭지점까지의 거리를 최소화하는 것처럼 보입니다. 이를 위해 가장자리에 수직 인 선상에 새로운 점의 유클리드 거리를 계산해야합니다. 교차점의 제거는 여전히 다른 문제입니다. – Oncaphillis
가장 가까운 가장자리의 두 점 사이에 삽입해야합니다. 이것은 적어도 교차점의 기회를 최소화 할 것입니다 (실제로 논리를 정확하게 이해한다면 완전히 제거해야합니다). 그리고 네, 그것은 하나의 가장자리를 "깰"더 두 개를 만들 것입니다. 가장 가까운 가장자리까지의 유클리드 거리를 계산하려면 어떻게해야합니까 (매번 거리를 계산하지 않고 가장 가까운 가장자리를 찾는 것이 이상적입니까). 또는 어떤 이유로 교차로를 제거하지 않으면 교차점을 만들지 않고 점을 삽입하는 방법은 무엇입니까? –