Given a list of polygons, construct Polygon with Holes

0
votes

For polygon, the points are given in counter clock wise manner. For holes, the points are given in clock wise manner. So given a list of polygons, how to construct all the polygon with holes?

Here are a few precondition of the polygon list:

  1. One polygon can contain multiple holes, but a hole must be contained inside a polygon.
  2. A hole cannot contain one or more polygon.
  3. All the holes must be located inside polygon, and not outside of it
  4. Hole's edge can touch on polygon's.
  5. And all the polygons and holes must not intersect with other polygons/holes, although they can touch one another.
  6. The polygon/ hole can be either convex or concave.

How to devise an algorithm that construct polygons with holes?

I am looking for a general algorithm, so any code in the form of C#, C++ and matlab are welcomed.

Edit: This is my input ( in C#)

public class PolygonWithHoles
{
   public List<Point> OuterBoundary;
   public List<List<Point>> Holes;
}


//input: a list of point list. If the point list constructs a polygon in Counter clock wise, then it is a general polygon, else it is a holes
public List<PolygonWithHoles> ConstuctPolyHoles(List<List<Point>> Polys)
{
}
1
c#c++matlabgeometrycomputational-geometry
It is not clear to me what output you want. Could you give an example? – Emond Erno
@Erno, sample input/output added – Graviton
Are the polygons and/or holes convex? – Emond Erno
@Erno, it can be convex or concave, does it matter? – Graviton
Yes, I think it does. Because when they can be concave it is hard to findout if a list of points is a hole or a polygon. – Emond Erno

1 Answers

2
votes

Point in polygon tests are vulnerable due to floating point rounding errors. They usually only work for non-trivial polygons.

A more robust approach should be based on a scan-line algorithm, where vertices are first sorted according to their x and y values. A scan (or sweep) line then moves eg. from left to right. The algorithm then typically maintains a list of lines intersecting the scan line by adding a line when its left vertex "hits" the scan line, and removing it when its right vertex hits the line.

After each move of the scan line, the intersections of the current lines with the scan line is updated, and the lines re-ordered according to the y value of the intersection. Whenever two lines need to be re-ordered during the sorting operation, then this means that they have an intersection, which can then be recorded.

After finding all the intersections, contours and holes can be identified reliably.

The following projects use this approach:

There are others, and the following site (which promotes the PolyBoolean library) compares the most important ones: http://www.complex-a5.ru/polyboolean/comp.html.

Just as a warning: I myself have implemented a polygon library supporting Boolean operations as well as hole detection. This library is being used in a commercial product, and I spent several years (!) to fine-tune the algorithm to ensure a correct result for any given input polygon in a little time as possible (other libraries may be a few % faster, but fail with some input data). In fact, a single approach algorithm may not be capable of solving all possible problems, so I had to implement several ones.

Good luck!