점이 직사각형 안에 있는지 테스트하십시오.
https://stackoverflow.com/questions/1897779
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 모두 같은 크기의 많은 직사각형 컬렉션을 가지고 있습니다.나는 이 직사각형에 속하지 않아야 하는 임의의 점을 생성하고 있으므로 생성된 점이 직사각형 중 하나에 있는지 테스트하고 그렇다면 새 점을 생성하는 것입니다.
R-트리를 사용하는 것은 효과가 있는 것처럼 보이지만 실제로는 점이 아닌 직사각형을 위한 것입니다.포인트에서도 작동하는 R-트리 알고리즘의 수정된 버전을 사용할 수 있지만 이미 더 나은 솔루션이 있다면 바퀴를 재발명하지 않는 것이 좋습니다.저는 데이터 구조에 익숙하지 않습니다. 그렇다면 제 문제에 맞는 구조가 이미 존재할까요?
요약하자면, 기본적으로 제가 묻는 것은 Python에서 작동하고 점이 주어진 직사각형 세트의 직사각형에 있는지 확인하는 데 사용할 수 있는 좋은 알고리즘을 아는 사람이 있는지입니다.
편집하다:이것은 2D이고 직사각형은 회전되지 않습니다.
해결책
이 Reddit 스레드는 문제를 해결합니다.
직사각형 세트가 있고 그 안에 점이 포함되어 있는지 확인해야 합니다.빠른 조회가 중요한 경우 이를 수행하기 위한 좋은 데이터 구조는 무엇입니까?
우주가 정수이거나 정밀도 수준이 잘 알려져 있고 너무 높지 않은 경우 다음을 사용할 수 있습니다. 아벨슨색상을 사용하여 O(1) 조회를 사용하는 스레드의 제안:
평소와 같이 시간 동안 공간을 교환 할 수 있습니다 ..다음은 상수가 매우 낮은 O (1) 조회입니다.초기화:모든 사각형을 충분히 정밀하게 둘러 볼 수있을만큼 큰 비트 맵을 만듭니다.사각형 흰색을 포함하는 모든 픽셀을 색칠하십시오.o (1) 조회 :점 (x,y)는 흰색입니까?그렇다면 사각형이 맞았습니다.
해당 게시물로 이동하여 자세히 읽어 보시기 바랍니다. 모던로닌의 답변이 가장 많이 받아들여졌습니다.여기에 붙여넣었습니다.
첫째, 미시적인 문제이다.임의로 회전 된 사각형과 포인트가 있습니다.직사각형 내부의 요점입니까?
이를 수행하는 방법에는 여러 가지가 있습니다.그러나 가장 좋은 것은 2D 벡터 크로스 제품을 사용하는 것입니다.먼저, 사각형의 지점이 시계 방향으로 저장되어 있는지 확인하십시오.그런 다음 1) 측면의 두 지점에 의해 형성된 벡터와 2) 측면의 첫 번째 지점에서 테스트 포인트까지 벡터를 사용하여 벡터 크로스 생성물을 수행합니다.결과의 부호를 확인하십시오 - 양의 긍정적 인 것은 측면의 오른쪽에 있고, 부정적인 것은 외부에 있습니다.네면 모두에 있으면 사각형 안에 있습니다.또는 동등하게, 측면 외부에 있으면 사각형 외부에 있습니다. 자세한 설명은 여기.
이 방법은 벡터 당 3 번의 빼기 * 측면 당 2 벡터와 측면 당 1 개의 크로스 제품이 3 개의 곱하기 및 2 개의 추가 기능입니다.측면 당 11 개의 플롭, 사각형 당 44 개의 플롭.
크로스 제품이 마음에 들지 않으면 다음과 같은 작업을 수행 할 수 있습니다.각 직사각형에 대해 새겨 져 있고 서두르는 서클을 알아 내고 내부의 포인트가 있는지 확인하십시오.그렇다면 사각형에도 있습니다.그렇지 않은 경우, 외울 된 사각형 외부에 있는지 확인하십시오.그렇다면 사각형 외부에도 있습니다.그것이 두 원 사이에 떨어지면, 당신은 f **** d이고 당신은 그것을 어려운 방법으로 확인해야합니다.
2D의 원이 내부에있는 경우 2 개의 뺄셈과 2 개의 제곱 (= 곱하기)이 발생한 다음 거리 제곱을 비교하여 제곱근을 수행하지 않아도됩니다.그것은 4 개의 플롭이고, 두 개의 원은 8 개의 플롭입니다. 그러나 때로는 여전히 알지 못합니다.또한 이는 CPU 시간을 지불하지 않는 것으로 가정 또는 새겨진 원을 계산하거나 사각형 세트에서 수행 할 사전 계산의 양에 따라 사실이거나 그렇지 않을 수도 있습니다.
어쨌든, 특히 1 억 개의 사각형이있는 경우 모든 사각형에 대해 포인트를 테스트하는 것은 좋은 생각이 아닙니다.
매크로 문제가 발생합니다.세트의 모든 직사각형에 대한 점을 테스트하는 방법은 무엇입니까?2d에서는 아마도 아마도 a 일 것입니다 쿼드트리문제.3d에서는 generic_handle이 말한 것 -Ctree.내 머리 꼭대기에서 나는 아마도 그것을 B+ 트리.d = 5를 사용하려는 유혹이되므로 각 노드는 최대 4 명의 어린이를 가질 수 있습니다. 쿼드 트리 추상화에 맵이 너무 멋져지기 때문입니다.그러나 직사각형 세트가 너무 크면 메인 메모리에 맞지 않을 가능성이 높으면 디스크 블록과 같은 크기의 노드를 갖는 것이 아마도 갈 수있는 방법 일 것입니다.
동일한 지점에 센터가있는 거의 동일한 직사각형을 가진 일부 데이터 세트와 같이 성가신 퇴화 케이스를 조심하십시오.:피
이 문제가 왜 중요한가요?컴퓨터 그래픽에서 광선이 다각형과 교차하는지 확인하는 것이 유용합니다.즉, 저격 소총 샷이 방금 촬영중인 사람을 때렸습니까?Say GPS 장치와 같은 실시간 맵 소프트웨어에서도 사용됩니다.GPS는 귀하가있는 좌표를 알려주지 만 MAP 소프트웨어는 그 지점이 많은 양의 맵 데이터의 위치를 찾아서 초당 여러 번 수행해야합니다.
다시 한 번, 신용 모던로닌...
다른 팁
축과 정렬 된 직사각형의 경우, 사각형을 식별하기 위해 2 점 (4 개의 숫자) 만 있으면됩니다. 주어진 지점 여부를 설정하기 위해 (x테스트, y테스트) 사각형과 겹칩니다 (xBl, yBl, xTr, yTr) 둘 다 테스트함으로써 :
- 엑스테스트 > = xBl && x테스트 <= xTr
- 와이테스트 > = yBl && y테스트 <= yTr
분명히, 테스트 할 충분한 포인트 세트의 경우, 이것은 상당히 시간이 많이 걸릴 수 있습니다. 문제는 테스트를 최적화하는 방법입니다.
분명히, 하나의 최적화는 모든 사각형 (경계 박스)을 둘러싼 상자의 최소 및 최대 x 및 y 값을 설정하는 것입니다.
- 엑스테스트 > = x최소 && x테스트 <= x맥스
- 와이테스트 > = y최소 && y테스트 <= y맥스
사각형으로 덮인 총 표면적의 양에 따라 사각형이 포함 된 겹치지 않는 하위 지역을 찾을 수 있으며, 그 점을 겹치는 사각형을 포함 할 수없는 하위 지역을 검색하는 것을 피할 수 있습니다. 적합한 데이터 구조의 사전 계산 비용으로 검색하는 동안 비교 저장. 직사각형 세트가 충분히 드물다면 겹치지 않을 수 있으며,이 경우 이것은 무차별 검색으로 퇴보합니다. 마찬가지로, 사각형 세트가 너무 조밀하여 경계 상자에 직사각형을 깨지 않고 분할 될 수있는 서브 범위가 없다면.
그러나, 당신은 또한 경계 영역을 분기 (각 방향의 절반)로 임의로 분해 할 수 있습니다. 그런 다음 원래 세트보다 더 많은 상자를 포함하는 상자 목록을 사용합니다 (임의의 경계 중 하나를 겹친 각 상자에 대해 2 ~ 4 개의 상자). 이점의 장점은 검색에서 4 분기 중 3 개를 제거하여 보조 저장 공간을 희생하여 총 검색의 양을 줄일 수 있다는 것입니다.
따라서 시공간 트레이드 오프가 있습니다. 및 사전 계산 대 검색 절충. 운이 좋지 않으면 사전 계산은 아무것도 달성하지 못합니다 (예 : 두 개의 상자 만 있고 두 축에는 겹치지 않습니다). 반면에, 그것은 상당한 검색 시간 이점을 얻을 수 있습니다.
나는 당신이 살펴 보는 것이 좋습니다 BSP 나무 (그리고 가능한 쿼드 트리 또는 옥 트리, 해당 페이지에서 사용할 수있는 링크도 있습니다). 그것들은 전체 공간을 재귀 적으로 분할하는 데 사용되며 당신이 당신이 전혀 확인 해야하는 직사각형을 신속하게 확인할 수 있습니다.
최소한 하나의 큰 파티션이 있고 모든 사각형을 점검해야합니다. 최대의 파티션이 너무 작아서 단일 사각형의 크기로 내려갑니다. 물론 파티션이 더 세밀하게 입자가 될수록 확인하려는 사각형을 찾기 위해 나무를 걸어야합니다.
그러나 포인트를 확인하기에 적합한 몇 개의 사각형 수를 자유롭게 결정한 다음 해당 구조를 만들 수 있습니다.
그래도 겹치는 사각형에주의를 기울이십시오. 어쨌든 BSP 트리를 사전 계산해야하므로 그 시간 동안 겹침을 제거 할 수 있으므로 명확한 파티션을 얻을 수 있습니다.
R-Tree 접근 방식은 내가 아는 최선의 접근법입니다 (R- 트리가 귀하의 경우에 구축하기가 편리한 것처럼 보이므로 쿼드 트리, B+ 나무 또는 BSP 트리에서 선택할 접근법입니다). 경고 : 나는 고등학교 대학의 알고리즘 클래스에서 몇 가지를 기억하지만 전문가는 아닙니다!
이것을 시도해 보지 않겠습니까? 계산과 메모리 모두에서 오히려 가벼운 것 같습니다.
공간의 기본선에 모든 사각형의 투영을 고려하십시오. 라인 간격 세트를 다음과 같이 나타냅니다
{[Rl1, Rr1], [Rl2, Rr2],..., [Rln, Rrn]}, ordered by increasing left coordinates.
이제 포인트가 (x, y)라고 가정하고 포인트 x가 포함 된 선 간격에 도달 할 때 까지이 세트의 왼쪽에서 검색을 시작하십시오.
아무도 없다면, 당신의 포인트 (x, y)는 모든 사각형 외부에 있습니다.
일부는 [rlk, rrk], ..., [rlh, rrh], (k <= h)라고 말하면 y가 이러한 직사각형의 수직 범위 내에 있는지 확인하십시오.
완료.
행운을 빕니다.
존 도너
