많은 수의 볼록 쿼드 (4 개의 주어진 x, y 포인트)를 가장 효율적인 방법으로 array/list를 실행 한 다음 해당 쿼드의 테두리 내에 또는 그 포인트가있는 경우 해당 쿼드를 확인합니다.포인트가 볼록 쿼드 다각형 안에 있는지 또는 가장 위에 있는지 확인하는 가장 효율적인 방법
원래 레이 캐스팅을 사용해 보았지만 모든 폴리곤이 쿼드이고 모두 볼록하다는 것을 알고 있기 때문에 약간의 과잉이라고 생각했습니다.
현재 각 쿼드를 가장자리를 공유하는 두 개의 삼각형으로 분할 한 다음 해당 영역을 사용하는 두 개의 삼각형 각각이 켜져 있는지 확인합니다. 예 삼각형 ABC 및 테스트 포인트에 대한 P.
경우 (areaPAB areaPAC + + areaPBC == areaABC) {TRUE를 반환; }
체크를 실행하기 위해 4 개의 다른 삼각형의 면적을 계산해야하므로 쿼드의 첫 번째 삼각형이 false를 반환하는 경우 조금 더 느리게 실행될 수 있습니다.이 경우 4 개의 더 많은 영역을 가져야합니다. (나는 부동 소수점 오류를 보완하기 위해 수표에 약간의 엡실론을 포함시킨다)
쿼드에 대해 한 번에 한 번씩 점검하는 것이 더 빠른 방법이되기를 바라고있다. 두 개의 삼각형으로
다각형을 배열 [,]에 넣어 검사 수를 줄이려고했습니다. 다각형을 추가 할 때 최소 및 최대 x 및 y 값을 확인한 다음이를 사용하여 동일한 폴리를 올바른 배열 위치에 배치합니다. 사용 가능한 다각형에 대해 점을 검사하면 배열 목록에서 적절한 목록을 검색합니다.
나는 비슷한 질문을 통해 검색해 왔으며 지금 내가 사용하고있는 것은 포인트가 삼각형인지 알아내는 가장 빠른 방법 일 수 있다고 생각하지만 더 좋은 테스트 방법이 있다고 기대한다. 항상 볼록한 쿼드입니다. 내가 다 봤던 모든 다각형 테스트는 여러면을 가지고 있거나 불규칙한 모양의 다각형에 대해 테스트하는 것 같습니다.
시간이 오래 걸리는 질문을 읽어서 간단한 문제에 대해 감사드립니다.
제안 해 주셔서 감사합니다. 나는 두 번째 방법을 시도했지만 현재 사용하고있는 방법보다 계산량이 적지 만 간신히 계산합니다. 첫 번째 방법을 좀 더 설명 할 수 있기를 바랬는데 더 나은 결과를 얻을 수없는지를보기 위해 dmuir에서 언급 한 모서리 방정식을 저장하는 것과 함께 사용할 수 있습니다. – Steve
원래 게시물의 설명을 보내 주셔서 감사합니다. 귀하의 수식을 적용했는데 다른 방법보다 빠르게 실행되고있는 것 같지만 문제가 발생했습니다. 포인트가 내부에있는 것이 아니라 가장자리에 놓여있는 경우에도 수표가 반환되어야합니다. 어딘가에서 엡실론을 사용하여 조정할 수있는 방법이 있습니까? 현재 구현 된 방법은 다음과 같습니다. – Steve
나는 항상 폴리곤에서 4 점을 가지므로 [i] 대신에 수동으로 선언하고 4 개의 EV와 PV를 채우고 십자가 결과에 대한 수레를 사용하여 똑같이합니다. 그렇다면 모든 4 개의 교차 결과가 모두> 0 또는 <0인지 확인합니다. 0과 비교하여 작은 숫자로 체크를 변경하는 것이 효과가있는 것 같지만 이것이 잘못된 방법인지 궁금합니다. . 도와 주셔서 다시 한 번 감사드립니다! – Steve