Connect Holes discussion

[lemmih]

CGAL has an implementation of connect holes that cut straight up from each hole to the nearest wall.

I'd like to add something like:

connectHoles :: (Ord r, Num r, Fractional r) => MultiPolygon p r -> SimplePolygon () r
connectHoles = connectHolesLinear (Vector2 0 1)
connectHolesLinear :: (Ord r, Num r, Fractional r) => Vector 2 r -> MultiPolygon p r -> SimplePolygon () r

Those functions connect the maximum extreme point (given by the vector) of each hole in a straight line. The extra data p is lost, though, since cutting adds new nodes rather than just new edges.

Are there other algorithms for cutting out holes? Perhaps a faster algorithm if the polygon has been triangulated? Is there an efficient way of making the shortest cuts possible? Is there an efficient way of cutting out holes without adding new nodes?

[noinia]

That sounds like a useful suggestion. There should be a fairly simple O(n log n) time sweepline algorithm to do something like that:

Assume for ease of exposition that the direction in which we want to connect is horizontal and "leftwards"

1. for every hole find the leftmost point on the hole,

we will essentially want to shoot a ray from that point to the left and see what edge we hit (which might be another hole). We use a sweep line algorithm to compute those edges:

2. sort the vertices on decreasing y-coordinate. We sweep a horizontal line while maintaining the edges of the polygon intersected by the sweep line in a balanced BST (in our case a Set)

3. at every leftmost vertex; use a predecessor query to find the edge hit by the ray.

4. After the sweep we found all segments that we want to add; add them and connect everything back into a single polygon.

Steps 1 and 4 are linear time. Steps 2 and 3 are O(n log n) as we have n events (vertices of the polygon), each taking O(log n) time per piece.

I think I already implemented something along these lines in the algorithm for constructing the planar subdivision. Since we need more or less the same there (see e.g. Chapter 2 of "the yellow book" (Computational Geometry, Applications & Practice).

edit: forgot to add: making the shortest cuts (in that given direction) should probably be possible by extending the above algorithm.

if we dont' want to add new vertices we can just select a subset of the triangulation edges. (but given a direction there may not a solution using only existing vertices of course)