.net (충돌 감지)에서 다각형의 거대한 데이터 세트 포인트

Question

나는 보통 삼각형이지만 때로는 사각형 인 다각형과 꽤 큰 메쉬를 가지고있다. 메쉬의 각 점에는 값이 있습니다 (값은 좌표와 관련이 없습니다).

이제 이전 메쉬와 동일한 좌표 공간에 두 번째 메쉬가 생성됩니다. 이제 이전 메쉬의 값을 사용하여 새 메쉬의 모든 점 (정점)에 대한 값을 보간하고 싶습니다.

이제 새로운 메쉬의 각 폴리곤을 루프 처리하고 2 차원 충돌 감지를 통해 각 폴리곤에있는 이전 정점을 감지 할 수 있습니다. (심지어이 경우에도 제대로 작동하지 않으므로 아무도 2 차원 충돌 감지 (삼각형이면 충분) 나는 그것을 기꺼이 본다.)

그러나 다시 내 주요 지점에. 각각의 새로운 폴리곤에 대해 각 이전 버텍스를 루핑하는 것이 효율적이지 않은 것 같습니다. 거기에 더 좋은 방법이 있습니까?

Answer 1

문제의 발견 적 방법에 대한 추가 지식없이 내가 제시 한 해결책은 다음과 같습니다. 전체 풍경의 직사각형 경계를 결정한 다음이 영역을 동일한 직사각형 파티션으로 분할합니다. 100x100. 각 파티션에 대해이 파티션에 정점이있는 이전 폴리곤 목록을 유지할 수 있습니다 (이전 폴리곤의 "해싱"과 같은). 그런 다음 각 새 다각형을 반복하고 어떤 파티션이 접할 지 결정합니다 (다각형의 경계 사각형과 그 사이의 모든 파티션의 꼭지점을 사용하는 것이 좋을 것입니다). 미리 만들어진 목록을 검색하여 후보인 해당하는 이전 버텍스를 찾습니다 정확한 충돌 탐지.

정확한 충돌 감지 계산에 소요되는 시간이 줄어들지 만 확실히 메모리 소비가 증가합니다. 그래서 당신의 정확한 문제에 따라 이것은 좋은 해결책이 될 수도 있고 단지 비실용적 일 수도 있습니다.