it-swarm-ko.tech

2D 오목 선체를 생성하는 효율적인 알고리즘이 있습니까?

GIS 파일 (도시 맵)에서 (2D) 점 세트를 가지면 해당 맵의 '윤곽'을 정의하는 다각형 (경계)을 생성해야합니다. 입력 매개 변수는 설정 한 점과 '최대 가장자리 길이'입니다. 그런 다음 해당하는 볼록 다각형을 출력합니다.

지금까지 찾은 가장 좋은 해결책은 들로네 삼각형을 생성 한 다음 최대 가장자리 길이보다 긴 외부 가장자리를 제거하는 것입니다. 모든 외부 모서리가 그보다 짧으면 내부 모서리를 제거하고 원하는 다각형을 얻습니다. 문제는 시간이 많이 걸리고 더 좋은 방법이 있는지 궁금합니다.

59
Fabio Ceconello

우리 실험실의 이전 학생들 중 한 명이 그의 박사 학위 논문에 적용 가능한 기술을 사용했습니다. 나는 그중 하나가 "알파 셰이프"라고 믿으며 다음 논문에서 참조됩니다.

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

이 문서는 당신이 따를 수있는 몇 가지 참고 자료를 제공합니다.

10
nsanders

대답은 다른 사람에게는 여전히 흥미로울 수 있습니다. 마칭 제곱 알고리즘의 변형, (1) 오목 선체 내에 적용하고 (2) 다음에 (예 : 3) 다른 scales 내 점의 평균 밀도에 의존합니다. 스케일은 서로의 배수 여야하므로 효율적인 샘플링에 사용할 수있는 그리드를 구축 할 수 있습니다. 이를 통해 빈 샘플 = 제곱, 점의 "클러스터/클라우드"내에있는 샘플 및 그 사이에있는 샘플을 빠르게 찾을 수 있습니다. 후자의 범주는 오목 선체의 일부를 나타내는 폴리 라인을 쉽게 결정하는데 사용될 수있다.

이 방법에서는 모든 것이 선형이며 삼각 분할이 필요하지 않으며 알파 셰이프를 사용하지 않으며 여기에 설명 된 상용/특허 제안과 다릅니다 ( http://www.concavehull.com/ )

2
monnoo

녀석들 here 는 "거의 개수에 거의 선형 적으로"행동하는 일련의 점들의 오목 선체를 결정하기위한 k 개의 가장 가까운 이웃 접근법을 개발했다고 주장한다. 슬프게도 그들의 논문은 잘 보호 된 것으로 보이며 them 을 요구해야합니다.

위의 내용을 포함하고 더 나은 접근 방식을 찾게 할 수있는 좋은 참조 집합 입니다.

2
Vinko Vrsalovic

Bing Maps V8 대화식 SDK에는 고급 모양 작업 내에 오목 선체 옵션이 있습니다.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

ArcGIS 10.5.1 내에서 3D Analyst 확장에는 형상 유형의 오목 선체, 구, 봉투 또는 볼록 선체와 함께 최소 경계 볼륨 도구가 있습니다. 모든 라이센스 수준에서 사용할 수 있습니다.

여기에 오목 선체 알고리즘이 있습니다 : https://github.com/mapbox/concaveman

1
Jaybird64

간단한 해결책은 다각형의 가장자리를 따라 걷는 것입니다. 경계를 연결하는 지점 P0 및 P1에 현재 Edge가 주어지면 경계 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)이므로 포인트 목록을 약간 정렬하고 싶을 것입니다. 예를 들어 도시의 중심으로부터의 점을 기준으로 점을 정렬하는 경우 각 반복에서 고려해야 할 점 세트를 제한 할 수 있습니다.

1
Mike F

이 플러그인을 사용하여 QGIS에서 수행 할 수 있습니다. https://github.com/detlevn/QGIS-ConcaveHull-Plugin

데이터와 상호 작용하는 데 필요한 방법에 따라 여기에서 어떻게 수행되었는지 확인할 가치가 있습니다.

1
Cameron

빠른 근사 솔루션 (볼록 껍질에도 유용함)은 동서 각 작은 요소의 북쪽과 남쪽 경계를 찾는 것입니다.

원하는 정도를 기준으로 고정 된 크기의 상한/하한 배열을 만듭니다. 각 포인트에 대해 어떤 E-W 열이 있는지 계산 한 다음 해당 열의 상한/하한을 업데이트하십시오. 모든 점을 처리 한 후 놓친 열에 대해 위/아래 점을 보간 할 수 있습니다.

또한 매우 긴 얇은 모양을 미리 확인하고 bin NS 또는 Ew)로 결정하는 것이 좋습니다.

1
Martin Beckett

좋은 질문! 나는 이것을 전혀 시도하지 않았지만 첫 번째 샷은이 반복적 인 방법입니다.

  1. 세트 N ( "포함되지 않음")을 만들고 세트의 모든 점을 N에 추가합니다.
  2. N에서 3 개의 점을 무작위로 골라 초기 다각형 P를 만듭니다. N에서 점을 제거합니다.
  3. 일부 다각형 내 알고리즘 을 사용하고 N의 점을 봅니다. N의 각 점에 대해 이제 P에 포함되어 있으면 N에서 제거합니다. N에서 점을 찾 자마자 여전히 P에 포함되어 있지 않으면 4 단계를 계속하십시오. N이 비어 있으면 완료된 것입니다.
  4. 찾은 점을 A라고 부릅니다. A에서 가장 가까운 P의 선을 찾아 가운데에 A를 추가합니다.
  5. 3 단계로 돌아 가기

나는 그것이 충분히 잘 작동하는 한 효과가있을 것이라고 생각합니다. 초기 3 점에 대해 좋은 휴리스틱이 도움이 될 것입니다.

행운을 빕니다!

1
Rob Dickerson

널리 채택 된 참조로서 PostGIS는 볼록으로 시작하여 동굴에 들어가면 여기서 볼 수 있습니다.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

0
Evan Carroll