This 2D geometry “puzzle” came up recently in a project I’ve been working on. On the face of it, the problem is extremely simple, but it turns out that it’s not at all easy to arrive at the answer in general using a computer program. It’s the sort of thing that’s much easier to explain to a child than to a compiler. Here it is:
Start with n arbitrary polygons in the plane. To illustrate, I’ll be using two triangles, but the algorithm should be able to handle any number of polygons, including concave polygons such as star shapes.
Each polygon has one colour and one edge colour. In a program, the polygons would be given as an array of (x, y) points – one per corner – as well as a colour and and an edge colour. The polygons may overlap, in which case one polygon may partially or fully hide another (just like if you cut out polygons out of paper and place them on top of each other).
Two overlapping triangles △ABC and △DEF. Their edges meet at points P, Q, R and S.
The region □PQRS is contained in both triangles, but that portion of △ABC is obscured by △DEF.
The task is simple:
Find all visible boundaries between two colours, finding for each one the start point, end point, left-hand colour, right hand colour, and edge colour.
Wherever the colour on either side of a boundary changes, the boundary must be split into two (or more) shorter boundaries. All edges are assumed to be infinitely thin. For the purposes of solving this on a computer, the coordinates are given as pairs of floating-point numbers.
The boundaries the algorithm should be able to find for our example.
The edges are:
| edge | colour | left | right |
|---|---|---|---|
| [AB] | blue | blue | ∅ |
| [BQ] | blue | blue | ∅ |
| [RC] | blue | blue | ∅ |
| [CS] | blue | blue | ∅ |
| [PA] | blue | blue | ∅ |
| [DP] | orange | yellow | ∅ |
| [PQ] | orange | yellow | blue |
| [QE] | orange | yellow | ∅ |
| [EF] | orange | yellow | ∅ |
| [FR] | orange | yellow | ∅ |
| [RS] | orange | yellow | blue |
| [SD] | orange | yellow | ∅ |
Can you figure out an algorithm to solve this?
I’m pretty sure I have a solution – it’s not very elegant and takes up a few hundred lines of code, but I think it’s correct. Situations that were initially hard to get right included corners touching edges, points where more than two edges meet, and certain configurations of more than two polygons overlapping.
Have fun!