2D 오목 선체를 생성하는 효율적인 알고리즘이 있습니까?
GIS 파일 (도시지도)에서 일련의 (2D) 점이 있으면 해당지도 (경계)의 '윤곽'을 정의하는 다각형을 생성해야합니다. 입력 매개 변수는 포인트 세트와 '최대 가장자리 길이'입니다. 그런 다음 해당 (아마 볼록하지 않은) 다각형을 출력합니다.
지금까지 찾은 최상의 솔루션은 Delaunay 삼각형을 생성 한 다음 최대 가장자리 길이보다 긴 외부 가장자리를 제거하는 것입니다. 모든 외부 가장자리가 그보다 짧으면 내부 가장자리를 제거하고 원하는 다각형을 얻습니다. 문제는 이것은 매우 시간이 많이 걸리고 더 나은 방법이 있는지 궁금합니다.
이 백서에서는 평면에있는 점 집합의 모양을 특성화하기위한 간단한 다각형 의 효율적인 생성에 대해 설명 하고 알고리즘을 제공합니다. 여기에 동일한 알고리즘을 사용하는 Java 애플릿도 있습니다 .
우리 연구실의 이전 학생 중 한 명이 박사 학위 논문에 적용 가능한 기술을 사용했습니다. 나는 그들 중 하나가 "알파 모양"이라고 생각하며 다음 논문에서 참조됩니다.
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
이 논문은 당신이 따를 수있는 몇 가지 추가 참고 자료를 제공합니다.
여기에 있는 사람들 은 "점의 수에 거의 선형 적으로"행동하는 점 집합의 오목한 선체를 결정하기 위해 가장 가까운 이웃 접근 방식을 개발했다고 주장합니다. 슬프게도 그들의 논문은 매우 잘 보호되어있는 것 같아서 그들 에게 요청 해야 할 것입니다.
다음 은 위 의 내용 을 포함하고 더 나은 접근 방식을 찾도록 유도 할 수 있는 좋은 참고 자료 입니다.
답은 다른 사람에게는 여전히 흥미로울 수 있습니다. 행진 사각형 알고리즘 의 변형을 적용하고 (1) 오목한 선체 내에서 적용한 다음 (2) (예 : 3) 평균 밀도에 의존하는 다른 척도에 적용 할 수 있습니다. 포인트들. 스케일은 서로 정수배 여야하므로 효율적인 샘플링에 사용할 수있는 그리드를 구축 할 수 있습니다. 이를 통해 빈 샘플 = 정사각형, 점의 "클러스터 / 구름"내에 완전히 포함 된 샘플 및 그 사이에있는 샘플을 빠르게 찾을 수 있습니다. 후자의 범주는 오목한 선체의 일부를 나타내는 폴리선을 쉽게 결정하는 데 사용할 수 있습니다.
이 접근 방식에서는 모든 것이 선형이며 삼각 측량이 필요하지 않으며 알파 모양을 사용하지 않으며 여기에 설명 된 상용 / 특허 제품과 다릅니다 ( http://www.concavehull.com/ )
빠른 근사 솔루션 (볼록 껍질에도 유용함)은 각각의 작은 요소 동서에 대한 북쪽 및 남쪽 경계를 찾는 것입니다.
원하는 세부 정보의 양에 따라 상한 / 하한의 고정 크기 배열을 만듭니다. 각 포인트에 대해 어느 EW 열에 있는지 계산 한 다음 해당 열의 상한 / 하한을 업데이트합니다. 모든 포인트를 처리 한 후 누락 된 열에 대해 상위 / 하위 포인트를 보간 할 수 있습니다.
매우 길고 얇은 모양을 미리 확인하고 빈 NS 또는 Ew를 결정할 가치가 있습니다.
간단한 해결책은 다각형의 가장자리를 걷는 것입니다. 경계 연결 지점 P0 및 P1의 현재 가장자리가 주어지면 경계 P2의 다음 지점은 가능한 가장 작은 A가있는 지점이됩니다.
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
그런 다음 설정
P0 <- P1
P1 <- P2
시작한 곳으로 돌아갈 때까지 반복합니다.
이것은 여전히 O (N ^ 2)이므로 포인트 목록을 약간 정렬하고 싶을 것입니다. 예를 들어 도시 중심으로부터의 방위를 기준으로 점을 정렬하는 경우 각 반복에서 고려해야하는 점 집합을 제한 할 수 있습니다.
좋은 질문! 나는 이것을 전혀 시도하지 않았지만 첫 번째 샷은 다음과 같은 반복적 인 방법입니다.
- 세트 N ( "포함되지 않음")을 만들고 세트의 모든 포인트를 N에 추가합니다.
- N에서 3 개의 점을 무작위로 선택하여 초기 다각형 P를 형성합니다. N에서 제거합니다.
- 사용하여 몇 가지 포인트 인 폴리곤 알고리즘 이 이제 P에 포함되어있는 경우 N의 각 포인트에 대한 N.에 지점 및보고, 당신은 여전히 P에 포함되지 않은 N에 지점을 발견하면 곧 N.로에서 제거 , 4 단계를 계속하십시오. N이 비어 있으면 완료된 것입니다.
- 찾은 지점 A를 호출하십시오. P에서 A에 가장 가까운 선을 찾아 그 중간에 A를 추가하십시오.
- 3 단계로 돌아 가기
충분히 잘 수행되는 한 작동 할 것이라고 생각합니다. 초기 3 점에 대한 좋은 휴리스틱이 도움이 될 수 있습니다.
행운을 빕니다!
이 플러그인으로 QGIS에서 할 수 있습니다. https://github.com/detlevn/QGIS-ConcaveHull-Plugin
데이터와 상호 작용하는 데 필요한 방법에 따라 여기에서 어떻게 수행되었는지 확인할 가치가 있습니다.
Bing Maps V8 대화 형 SDK에는 고급 모양 작업 내에 오목한 선체 옵션이 있습니다.
ArcGIS 10.5.1 내에서 3D Analyst 확장에는 오목 선체, 구, 봉투 또는 볼록 선체의 지오메트리 유형이 포함 된 최소 경계 볼륨 도구가 있습니다. 모든 라이선스 수준에서 사용할 수 있습니다.
오목한 선체 알고리즘이 있습니다 : https://github.com/mapbox/concaveman
광범위하게 채택 된 참조로서 PostGIS는 볼록한 껍질로 시작하여 그것을 안으로 넣습니다. 여기에서 볼 수 있습니다.
'development' 카테고리의 다른 글
| MSBuild ProjectReference : private ( "로컬 복사")-허용되는 값과 동작은 무엇입니까? (0) | 2020.12.09 |
|---|---|
| 일부 텍스트가 포함 된 소스 jar 내부를 검색하기 위해 Eclipse "파일 검색"을 만드는 방법은 무엇입니까? (0) | 2020.12.09 |
| docker는 VM이 아닙니다. 컨테이너에 기본 이미지 OS가 필요한 이유는 무엇입니까? (0) | 2020.12.09 |
| 명령형 대 일반 이전 하위 유형 (0) | 2020.12.09 |
| 인덱스로 인해 레코드 수가 증가함에 따라 SQLite 삽입 속도가 느려집니다. (0) | 2020.12.09 |