Keyhole

A small "extention" to the wonderful polygon clipper library written by Angus J.

What is it?

Other libraries (triangulators, graphics engines, etc.) don't often support polygons with holes. Clipper doesn't support outputting polygons without holes. To solve this, we can use a keyhole/cutline algorithm to generate continuous, simple polygons from Clipper's output.

Usage

Code snippet example:

using namespace ClipperLib;
using namespace Keyhole;

// Usual clipper code
Clipper clipper;

clipper.AddPath(some_polygon, PolyType::ptSubject, true);
clipper.AddPath(another_polygon, PolyType::ptClip, true);

PolyTree solution;
clipper.Execute(ClipType::ctDifference, solution);

// But what if our solution contains holes we can't use?
Paths continuous_polygons;
keyhole_tree(solution, continuous_polygons);

// Now we can convert and use these polygons in almost any other polygon library

Algorithm

(note: need to add visualizations)

The basic goal is to find some non-intersecting line between the parent polygon and the child polygon (hole), called a keyhole or cutline. With this keyhole, you can splice both polygons together creating a continuous polygon with a hole.

The least complicated approach would be to cast a ray outward from a vertex in the child polygon, and make the keyhole using the first intersection point between the ray and the parent polygon. However, because Clipper only works with integer coordinates, using the intersection point may turn a line segment from the parent polygon into two non-collinear line segments. To avoid this, we modify the approach.

The approach this library uses is a simple brute-force algorithm that tries to find keyholes using vertex-vertex pairs between the parent and child polygon. If the generated keyhole segment doesn't intersect the parent, the hole, or any other holes, it is spliced together with the parent polygon.

Current problems

At the moment, this library is completely unoptimized. The current implementation is a brute-force approach. While it works, it gets very slow very quickly.