[algorithm] 폴리곤 팽창 / 팽창 (오프셋, 버퍼링) 알고리즘
다각형을 어떻게 “부 풀리게”합니까? 즉, 나는 이것과 비슷한 것을하고 싶다 :
요구 사항은 새로운 (팽창 된) 다각형의 가장자리 / 점이 모두 기존 (원래의) 다각형과 같은 일정한 거리에 있어야한다는 것입니다 (예제에서는 그렇지 않습니다. 지금은 잊어라;)).
내가 찾고있는 것에 대한 수학적 용어는 실제로 안쪽 / 바깥 쪽 다각형 오프셋 입니다. 이것을 지적하기 위해 발린 +1. 다른 이름은 다각형 버퍼링 입니다.
내 검색 결과 :
다음은 몇 가지 링크입니다.
답변
나는 잠시 내 자신의 언급 거라고 생각 다각형 클리핑 및 상쇄 라이브러리 – 클리퍼를 .
Clipper 는 주로 다각형 클리핑 작업을 위해 설계 되었지만 다각형 오프셋도 수행합니다. 라이브러리는 Delphi, C ++ 및 C #으로 작성된 오픈 소스 프리웨어 입니다 . 무료 라이센스와 상용 응용 프로그램 모두에서 무료로 사용할 수 있는 매우 강화 된 Boost 라이센스가 있습니다.
다각형 오프셋은 사각형, 원형 및 연귀의 세 가지 오프셋 스타일 중 하나를 사용하여 수행 할 수 있습니다.
답변
찾고있는 다각형 을 계산 기하학에서 안쪽 / 바깥 쪽 오프셋 다각형 이라고 하며 직선 골격 과 밀접한 관련이 있습니다.
다음은 복잡한 다각형에 대한 여러 오프셋 다각형입니다.
그리고 이것은 다른 다각형의 직선 골격입니다.
다른 의견에서도 지적했듯이 다각형을 얼마나 “팽창 / 팽창”시킬 계획인지에 따라 출력에 다른 연결성을 가질 수 있습니다.
계산 관점에서 : 일단 직선 골격을 가지면 오프셋 다각형을 비교적 쉽게 구성 할 수 있어야합니다. 공개 소스 및 (비 상업용 무료) CGAL 라이브러리에는 이러한 구조를 구현하는 패키지가 있습니다. CGAL을 사용하여 오프셋 다각형을 계산하려면 이 코드 예제 를 참조하십시오 .
패키지 매뉴얼은 당신이 CGAL를 사용하지 않을 경우에도 이러한 구조를 구성하는 방법에 대한 시작점 당신에게 좋은를 제공하고, 수학적 정의와 속성을 사용하여 논문에 대한 참조를 포함한다 :
CGAL 매뉴얼 : 2D 직선 스켈레톤 및 다각형 오프셋
답변
이런 종류의 것들에 대해서는 보통 JTS를 사용 합니다. 데모 목적으로 JSTS (JavaScript port of JTS) 를 사용하는 이 jsFiddle 을 작성했습니다 . 필요한 좌표를 JSTS 좌표로 변환하면됩니다.
function vectorCoordinates2JTS (polygon) {
var coordinates = [];
for (var i = 0; i < polygon.length; i++) {
coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
}
return coordinates;
}
결과는 다음과 같습니다.
추가 정보 : 나는 일반적으로지도에 그려진 다각형 (리플렛 또는 Google지도)에 반경으로 경계를 설정하기 위해이 유형의 팽창 / 수축 (내 목적에 약간 수정)을 사용합니다. (lat, lng) 쌍을 JSTS 좌표로 변환하면 다른 모든 항목이 동일합니다. 예:
답변
당신이 원하는 것 같아요.
- 정점에서 시작하여 인접한 가장자리를 따라 시계 반대 방향으로 향합니다.
- 모서리를 기존 모서리
d의 “왼쪽” 에 떨어진 새 평행 모서리로 교체하십시오 . - 모든 모서리에 대해 반복하십시오.
- 새로운 꼭지점을 얻기 위해 새로운 모서리의 교차점을 찾으십시오.
- 교차 다각형이되었는지 감지하고 그에 대한 조치를 결정하십시오. 교차점에 새로운 정점을 추가하고 오래된 정점을 제거하십시오. 인접하지 않은 모든 모서리 쌍을 비교하여 두 쌍의 정점 사이에 교차점이 있는지 확인하는 것보다 이것을 감지하는 더 좋은 방법이 있는지 확실하지 않습니다.
결과 다각형은 정점에서 “충분한”기존 다각형으로부터 필요한 거리에 있습니다. 정점 근처 d에서 기존 다각형으로부터 떨어진 점 세트는 다각형이 아니므로 명시된 요구 사항을 충족시킬 수 없습니다.
이 알고리즘에 이름, 웹상의 예제 코드 또는 최종 최적화가 있는지는 모르지만 원하는 것을 설명한다고 생각합니다.
답변
GIS 세계에서는이 작업에 네거티브 버퍼링을 사용합니다 :
http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf
JTS 라이브러리는 당신을 위해이 작업을 수행해야합니다. 버퍼 조작에 대한 문서를 참조하십시오. http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html
대략적인 개요는 개발자 안내서를 참조하십시오 :
http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf
답변
각 선은 평면을 “내부”및 “개요”로 분할해야합니다. 일반적인 내부 제품 방법을 사용하여 찾을 수 있습니다.
모든 선을 일정 거리만큼 바깥쪽으로 이동하십시오.
모든 인접 선 쌍 (선 세그먼트가 아닌 선)을 고려하고 교차점을 찾으십시오. 이들은 새로운 정점입니다.
교차하는 부분을 제거하여 새 정점을 정리하십시오. -여기 몇 가지 사례가 있습니다
(a) 사례 1 :
0--7 4--3
| | | |
| 6--5 |
| |
1--------2
하나만 소비하면 다음과 같은 결과를 얻습니다.
0----a----3
| | |
| | |
| b |
| |
| |
1---------2
7과 4가 겹칩니다.이 경우이 점과 그 사이의 모든 점이 제거됩니다.
(b) 사례 2
0--7 4--3
| | | |
| 6--5 |
| |
1--------2
두 개를 소비하면 다음과 같은 결과를 얻습니다.
0----47----3
| || |
| || |
| || |
| 56 |
| |
| |
| |
1----------2
이 문제를 해결하려면 각 선분에 대해 후자의 선분과 겹치는 지 확인해야합니다.
(c) 사례 3
4--3
0--X9 | |
| 78 | |
| 6--5 |
| |
1--------2
이것은 1로 소비됩니다. 이것은 사례 1의 경우보다 일반적인 경우입니다.
(d) 사례 4
case3과 동일하지만 2만큼 소비됩니다.
실제로 사례 4를 처리 할 수있는 경우 다른 모든 사례는 선이나 정점이 겹치는 특수한 경우입니다.
경우 4를 수행하기 위해 정점 스택을 유지합니다. 후행과 겹치는 선을 찾을 때 푸시하고 후자의 선을 가져올 때 팝합니다. -볼록 껍질에서하는 것과 같습니다.
답변
다음은 대체 솔루션입니다. 더 좋아하는지 확인하십시오.
-
DO가 삼각 측량을 , 그것은 들로네가 될 필요가 없습니다 – 어떤 삼각 측량 할 것입니다.
-
각 삼각형을 부 풀리십시오-이것은 사소한 것입니다. 시계 반대 방향으로 삼각형을 저장하는 경우 선을 오른쪽으로 이동하고 교차로를 수행하십시오.
-
수정 된 Weiler-Atherton 클리핑 알고리즘을 사용하여 병합
