무작위로 생성된 포인트가 지도에서 어느 지역에 속하는지 어떻게 식별합니까?이 질문을 이미 stackoverflow에 게시했습니다. 그러나 답변을 얻을 가능성이 더 높기 때문에 커뮤니티에 지적되었습니다. 내 문제가 무엇을 수반하는지에 대한 그림 표현도 있습니다.
기본적으로 여러 직사각형 영역으로 구성된 "지도"가 있습니다. 각 직사각형 영역의 모든 정점 좌표(x_min, x_max, y_min, y_max)에 액세스할 수 있습니다.
나는 그 지도의 아무 곳에나 있는 점을 무작위로 생성합니다. 나는 그 점(x와 y)의 좌표를 알고 있다. 내가 풀고자 하는 문제는 그 점이 어느 지역에 있는지 알아내는 것이다.
내가 한 것은 점의 x & y 좌표가 모든 영역의 x_min과 x_max 및 y_min과 y_max 사이에 있는지 하나씩 확인하는 큰 조건문을 통과하는 것입니다. 그러나 이 작업을 수행하는 데 보다 확장 가능하고 일반화 가능하며 효율적인 방법이 있어야 한다고 생각하지만 적어도 다른 프로그래밍 언어용 라이브러리에 없는 것은 아닌 방법을 찾을 수 없습니다. 지도를 반으로 쪼개서 반이 어느 부분에 있는지 알아내고, 그 반에 있는 모든 지역을 세고, 한 지역이 남아 있는지 확인하고, 없으면 지도를 다시 반으로 나누고, 다시 과정을 거칩니다. 나는 그것이 어떻게 구현될 수 있는지 그리고 그것이 내가 현재 가지고 있는 방법보다 실현 가능하거나 더 나은지 잘 모릅니다.
스크립팅창Re: 무작위로 생성된 포인트가 지도에서 어느 지역에 속하는지 어떻게 식별합니까?타일링된 직사각형 영역에 대한 알고리즘을 발명했다면 KDTable 함수를 사용하고 모든 모서리 점을 테이블에 로드할 것입니다. 이 같은:
1~4개의 직사각형이 각 모서리를 공유합니다.
KDTable은 쿼리된 xy 위치에 가장 가까운 모서리를 효율적으로 알려줍니다. 해당 점을 공유하는 모든 직사각형의 다른 테이블을 유지하는 경우 최대 4개만 확인하면 됩니다. 데이터를 정렬하는 방법에 따라
KDTable은 K 차원에서 설명한 대로 거의 수행하고 있습니다. xy 데이터의 경우 K==2입니다.
Re: 무작위로 생성된 포인트가 지도에서 어느 지역에 속하는지 어떻게 식별합니까?아니면 더 어려울 수도 있습니다.
이것은 잘못된 모서리를 찾을 것입니다.
Re: 무작위로 생성된 포인트가 지도에서 어느 지역에 속하는지 어떻게 식별합니까?얼마나 많은 해상도가 필요합니까? 10K x 10K 비트맵이면 충분하고 다각형이 16E6 미만인 경우 고유한 색상(2^24 색상은 1600만 색상)으로 사각형을 비트맵에 그리고 둥근 xy 픽셀을 즉시 쿼리할 수 있습니다. 나는 에서 그런 일을했다. ESP32 클록의 JSL BLOB 시간대 지도에서 GPS 조회를 위해. 제 경우에는 시간대 경계 근처에서 1-2마일 정도의 해상도를 얻었습니다. 작은 컴퓨터에 맞게 비트맵을 실행 길이로 인코딩할 수 있는 것만큼 속도가 필요하지 않았습니다.
편집 : 분명히 나는 비트 맵을 이렇게 크게 만들었습니다.
composition = J( 16000, 30000, 0 );
메모리가 부족하거나 더 커지면 픽셀 제한을 초과했습니다... +/- 90도 위도에 16000을 사용하고 +/- 180도 경도에 30K(32K 아님)를 사용했습니다. 압축되지 않은 GB가 넘습니다. JPG가 아닌 PNG 파일이 필요합니다. JPG는 색상을 유지하지 않습니다.
Re: 무작위로 생성된 포인트가 지도에서 어느 지역에 속하는지 어떻게 식별합니까?직사각형이 회전하지 않고 겹치지 않기 때문에:
네 가지 검사/루프와 일치하지 않는 항목은 항상 제거합니다.
1. x_min이 점의 x보다 작은 모든 사각형을 확인합니다.
2. x_max가 포인트의 x보다 큰 나머지 모든 사각형에서 확인
3. y_min이 포인트의 y보다 작은 남은 모든 사각형에서 확인
4. y_max가 포인트의 y보다 큰 나머지 모든 사각형에서 확인
그리고 한 칸만 남으면 이 중 어느 지점에서든 멈출 수 있습니다. JMP의 경우 Loc()을 사용하여 이 작업을 수행할 수 있습니다.
또는 모든 제곱 최소값을 반복하고 다음과 일치하는 항목을 찾으면 중단합니다.
:xmin < x < :xmax & :ymin < y < :ymax
관련이 있고 더 멋진 가능한 솔루션이 있는 몇 가지 링크:
https://stackoverflow.com/questions/1897779/test-if-point-is-in-some-rectangle
https://www.reddit.com/r/programming/comments/80dlc/i_have_a_set_of_rectangles_and_need_to_determine/
