## Geometry-Free Polygon Splitting

### Abstract

A polygon splitting algorithm is a combinatorial recipe. The
description and the implementation of polygon splitting should not
depend on the embedding geometry. Whether a polygon is being split
in Euclidean, in spherical, in oriented projective, or in hyperbolic
geometry should not be part of the description of the algorithm. The
algorithm should be purely combinatorial, or *geometry free*.

The geometry ultimately needs to be specified, and the geometric
predicates can only be implemented after specifying the coordinate
type and the number type. But the geometry, along with the
coordinates and number type in that geometry, remain a late
"plug-in", to be added only to the finished algorithm.

We describe a kernel for hyperbolic geometry. Once classes and
predicates in that geometry are developed, hyperbolic geometry can
be used as a plug-in to polygon splitting alongside other
geometries.

We also describe an algorithm for the splitting of a polygon
represented using its bounding lines. The use of this dual
representation ensures that all predicates are computed directly
from input data. This remains the case even if the same polygon is
split multiple times, as occurs in BSP tree construction.

### Files

back