# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Decompose a pair of polygons into disjoint fragments

Contributed by:
Bradley Klee

ResourceFunction["PlanarPolygonFragmentation"][ combines simple polygons |

To fragment polygons *p*_{1} and *p*_{2}, we join their combined edge and vertex sets, adding new vertices wherever an edge of *p*_{1} crosses an edge of *p*_{2}. The new set of edges and vertices bounds a finite set of simple polygons* *(i.e. topological disks), also called “fragments” of *p*_{1} and *p*_{2}.

Fragments are extracted and returned in two classes. One class contains the intersection(s) and union of *p*_{1} and *p*_{2}, while the other contains the pairwise complements between *p*_{1} and *p*_{2}.

If the vertices of *p*_{1} and *p*_{2}, have the same circularity (or handedness), then the intersection/union class falls under the True key, while differences fall under the False key.

There are several polygon clipping algorithms. Transposition for opposite-handedness is consistent with set operations when considering circularity as the determining measure of whether the polygon's filled area is either interior or exterior to the boundary. Such a convention is relatively common in high-power clipping algorithms, and it is also a feature of the wedge product in symplectic geometry.

If the combination of *p*_{1} and *p*_{2} encloses a polygonal hole, it will become a fragment in the same class as the intersection(s). In this case the union needs a more complicated form, Polygon[*frag*_{1}→*frag*_{2}], where *frag*_{1} and *frag*_{2} are outer and inner boundaries respectively. Considering the outer boundary as enclosing the figure's exterior (including the point at infinity), the union of all fragments should be an exact cover of the entire plane.

ResourceFunction["PlanarPolygonFragmentation"] takes one option "BinCount" → *n*, with default value *n *= 1. When *n* is set to a positive integer greater than 1, the input vertices and edges are discretized into approximately *n*^{2} bins, which allows intersections to be solved locally. For polygons with many edge segments, this saves considerable time by avoiding unnecessary, brute force calculation via Outer. This improves speed, but in pathological cases can lead to incorrect results.

Even in cases where discretization is necessary, a law of diminishing returns applies. There is usually a best choice for "BinCount", which may require experimentation or heuristics to find. In the case of inputs with few edges, setting "BinCount" greater than 1 is not necessary.

Self-intersecting polygons and polygons with holes are not valid inputs. Should one desire, they can be broken up into lists of simple polygons, which can then be folded through the fragmentation process.

Due to the undecidability of zero testing, exact coincidence calculations often need to be evaluated numerically. Currently, all such calculations are done at MachinePrecision, with zero-threshold set to 2^{6}$MachineEpsilon. PrecisionGoal may be added as an option in a future version.

ResourceFunction["PlanarPolygonFragmentation"] can be used to solve planar clipping problems. Our algorithm is already more powerful and can be faster than the numerical standard Greiner-Hormann. In utilizing discrete methods, ResourceFunction["PlanarPolygonFragmentation"] goes below the naive order O(*n***m*) complexity limit, which was carried through the subsequent work "Clipping simple polygons with degenerate intersections" (see references below).

A Venn diagram formed from two polygons:

In[1]:= |

Out[2]= |

Fragment into separate regions:

In[3]:= |

Out[3]= |

Coincident vertices are not problematic:

In[4]:= |

Out[4]= |

Obtain the union of two adjacent hexagons:

In[5]:= |

Out[5]= |

The union happens to be the first of the True element:

In[6]:= |

Out[6]= |

Specify the order of points in the polygon:

In[7]:= |

Out[7]= |

Concave polygons can lead to hole fragments:

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

Get the boundary and hole:

In[10]:= |

The union is then written as:

In[11]:= |

Out[11]= |

Get the outline of France:

In[12]:= |

Out[12]= |

Create an intersecting circle:

In[13]:= |

Out[13]= |

Difficult cases with many vertices can still be computed efficiently by setting “BinCount”.

In[14]:= |

Out[14]= |

Changing the discretization parameter only affects timings:

In[15]:= |

Out[15]= |

Get the union by choosing the region with the largest area:

In[16]:= |

Out[16]= |

Output coordinates retain infinite precision:

In[17]:= |

Out[17]= |

Compare with RegionUnion which does not compute a single polygon:

In[18]:= |

Out[18]= |

An explicit result can be approximated using DiscretizeRegion:

In[19]:= |

Out[19]= |

But vertex coordinates are given only to machine precision:

In[20]:= |

Out[20]= |

Obtain the intersection of two polygons:

In[21]:= |

Out[21]= |

RegionIntersection is noticeably slower:

In[22]:= |

Out[22]= |

The underlying issue seems to be symbolic swell:

In[23]:= |

Out[23]= |

Obtain the remainder of the first polygon after subtracting the second:

In[24]:= |

Out[24]= |

RegionDifference spends considerable time to obtain a BooleanRegion result:

In[25]:= |

Out[25]= |

Generate random polygons:

In[26]:= |

In[27]:= |

Out[27]= |

Compute the fragmentation for all possible combinations of circularity:

In[28]:= |

Verify the invariant transformation property:

In[29]:= |

Out[29]= |

Verify the covariant transformation property:

In[30]:= |

Out[30]= |

Self-intersecting polygons will typically not give meaningful results:

In[31]:= |

Out[31]= |

Polygons with holes are not guaranteed to work:

In[32]:= |

Out[32]= |

In[33]:= |

Out[33]= |

In[34]:= |

Out[34]= |

Adding seams can allow computation of correct complements::

In[35]:= |

Out[35]= |

In[36]:= |

Out[36]= |

The intersection can also be extracted:

In[37]:= |

Out[37]= |

Combine a pair of hat tiles:

In[38]:= |

Out[38]= |

Compare options for adding another tile to the fragment:

In[39]:= |

Out[39]= |

Choose the one valid candidate, and obtain the next largest fragment:

In[40]:= |

Out[40]= |

- Checking a dodecagon mistake at OEIS
- [WSS23] Hat tiling space reduction and grow function implementation
- [WSS23] HatGame: a journey through the hat tile configuration space

Wolfram Language 13.0 (December 2021) or above

- 1.0.0 – 15 September 2023

This work is licensed under a Creative Commons Attribution 4.0 International License