폴리곤 팽창 / 팽창 (오프셋, 버퍼링) 알고리즘

폴리곤 팽창 / 팽창 (오프셋, 버퍼링) 알고리즘

---

다각형을 어떻게 "부 풀리게"합니까? 즉, 나는 이것과 비슷한 것을하고 싶다 :

요구 사항은 새로운 (팽창 된) 다각형의 가장자리 / 점이 모두 기존 (원래의) 다각형과 동일한 일정한 거리에 있어야한다는 것입니다 (예제 그림에서는 팽창 된 정점에 호를 사용해야하므로 지금은 잊어라;)).

내가 찾고있는 것에 대한 수학적 용어는 실제로 안쪽 / 바깥 쪽 다각형 오프셋 입니다. 이것을 지적하기 위해 발린 +1. 다른 이름은 다각형 버퍼링 입니다.

내 검색 결과 :

다음은 몇 가지 링크입니다.

• 다각형 오프셋 전략 조사
• 다각형 오프셋, 문제
• 버퍼링 다각형 데이터

---

나는 잠시 내 자신의 언급 거라고 생각 다각형 클리핑 및 상쇄 라이브러리 - 클리퍼를 .

Clipper 는 주로 다각형 클리핑 작업을 위해 설계 되었지만 다각형 오프셋도 수행합니다. 라이브러리는 Delphi, C ++ 및 C #으로 작성된 오픈 소스 프리웨어 입니다 . 무료 라이센스와 상용 응용 프로그램 모두에서 무료로 사용할 수 있는 매우 강화 된 Boost 라이센스가 있습니다.

다각형 오프셋은 사각형, 원형 ​​및 연귀의 세 가지 오프셋 스타일 중 하나를 사용하여 수행 할 수 있습니다.

---

찾고있는 다각형 을 계산 기하학에서 안쪽 / 바깥 쪽 오프셋 다각형 이라고 하며 직선 골격 과 밀접한 관련이 있습니다.

다음은 복잡한 다각형에 대한 여러 오프셋 다각형입니다.

그리고 이것은 다른 다각형의 직선 골격입니다.

다른 의견에서도 지적했듯이 다각형을 얼마나 "팽창 / 팽창"시킬 계획인지에 따라 출력에 다른 연결성을 가질 수 있습니다.

계산 관점에서 : 일단 직선 골격을 가지면 오프셋 다각형을 비교적 쉽게 구성 할 수 있어야합니다. 공개 소스 및 (비 상업용 무료) CGAL 라이브러리에는 이러한 구조를 구현하는 패키지가 있습니다. CGAL을 사용하여 오프셋 다각형을 계산하려면 이 코드 예제 를 참조하십시오 .

패키지 매뉴얼은 당신이 CGAL를 사용하지 않을 경우에도 이러한 구조를 구성하는 방법에 대한 시작점 당신에게 좋은를 제공하고, 수학적 정의와 속성을 사용하여 논문에 대한 참조를 포함한다 :

CGAL 매뉴얼 : 2D 직선 스켈레톤 및 다각형 오프셋

---

당신이 원하는 것 같아요.

• 정점에서 시작하여 인접한 가장자리를 따라 시계 반대 방향으로 향합니다.
• 가장자리를 기존 가장자리 d의 "왼쪽" 에 떨어진 새 평행 가장자리로 교체하십시오 .
• 모든 모서리에 대해 반복하십시오.
• 새로운 꼭지점을 얻기 위해 새로운 모서리의 교차점을 찾으십시오.
• 교차 다각형이되었는지 감지하고 어떻게해야할지 결정하십시오. 교차점에 새로운 정점을 추가하고 오래된 정점을 제거하십시오. 인접하지 않은 모든 모서리 쌍을 비교하여 두 쌍의 정점 사이에 교차점이 있는지 확인하는 것보다 이것을 감지하는 더 좋은 방법이 있는지 확실하지 않습니다.

결과 다각형은 정점으로부터 "충분한"기존 다각형으로부터 필요한 거리에 있습니다. 정점 근처 d에서 기존 다각형으로부터 떨어진 점 세트는 다각형이 아니므로 명시된 요구 사항을 충족시킬 수 없습니다.

이 알고리즘에 이름, 웹상의 예제 코드 또는 최종 최적화가 있는지는 모르지만 원하는 것을 설명한다고 생각합니다.

---

이런 종류의 것들에 대해서는 보통 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 좌표로 변환하면 다른 모든 항목이 동일합니다. 예:

---

각 선은 평면을 "내부"및 "개요"로 분할해야합니다. 일반적인 내부 제품 방법을 사용하여 찾을 수 있습니다.

모든 선을 일정 거리만큼 바깥쪽으로 이동하십시오.

Consider all pair of neighbor lines (lines, not line segment), find the intersection. These are the new vertex.

Cleanup the new vertex by removing any intersecting parts. -- we have a few case here

(a) Case 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by one, you got this:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 and 4 overlap.. if you see this, you remove this point and all points in between.

(b) case 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by two, you got this:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

to resolve this, for each segment of line, you have to check if it overlap with latter segments.

(c) case 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

expend by 1. this is a more general case for case 1.

(d) case 4

same as case3, but expend by two.

Actually, if you can handle case 4. All other cases are just special case of it with some line or vertex overlapping.

To do case 4, you keep a stack of vertex.. you push when you find lines overlapping with latter line, pop it when you get the latter line. -- just like what you do in convex-hull.

---

Here is an alternative solution, see if you like this better.

1. Do a triangulation, it don't have to be delaunay -- any triangulation would do.

2. Inflate each triangle -- this should be trivial. if you store the triangle in the anti-clockwise order, just move the lines to right-hand-side and do intersection.

3. Merge them using a modified Weiler-Atherton clipping algorithm

---

In the GIS world one uses negative buffering for this task: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

The JTS library should do this for you. See the documentation for the buffer operation: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

For a rough overview see also the Developer Guide: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

---

Big thanks to Angus Johnson for his clipper library. There are good code samples for doing the clipping stuff at the clipper homepage at http://www.angusj.com/delphi/clipper.php#code but I did not see an example for polygon offsetting. So I thought that maybe it is of use for someone if I post my code:

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        foreach (var point in originalPath)
        {
            polygon.Add(new ClipperLib.IntPoint(point.X, point.Y));
        }

        ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset();
        co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);

        List<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        co.Execute(ref solution, offset);

        foreach (var offsetPath in solution)
        {
            foreach (var offsetPathPoint in offsetPath)
            {
                resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y)));
            }
        }

        return resultOffsetPath;
    }

---

One further option is to use boost::polygon - the documentation is somewhat lacking, but you should find that the methods resize and bloat, and also the overloaded += operator, which actually implement buffering. So for example increasing the size of a polygon (or a set of polygons) by some value can be as simple as:

poly += 2; // buffer polygon by 2

---

Based on advice from @JoshO'Brian, it appears the rGeos package in the R language implements this algorithm. See rGeos::gBuffer .

---

There are a couple of libraries one can use (Also usable for 3D data sets).

1. https://github.com/otherlab/openmesh
2. https://github.com/alecjacobson/nested_cages
3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

One can also find corresponding publications for these libraries to understand the algorithms in more detail.

The last one has the least dependencies and is self-contained and can read in .obj files.

Best wishes, Stephan

---

I use simple geometry: Vectors and/or Trigonometry

1. At each corner find the mid vector, and mid angle. Mid vector is the arithmetic average of the two unit vectors defined by the edges of the corner. Mid Angle is the half of the angle defined by the edges.

2. If you need to expand (or contract) your polygon by the amount of d from each edge; you should go out (in) by the amount d/sin(midAngle) to get the new corner point.

3. Repeat this for all the corners

*** Be careful about your direction. Make CounterClockWise Test using the three points defining the corner; to find out which way is out, or in.

참고URL : https://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons