Module Gg_kit.Pgon2

2D polygons.

A polygon is defined by a list of Ring2.ts. Polygon surface is determined by the even-odd rule.


type t

The type for polygons.

val of_rings : Gg__ring2.t list -> t

of_rings rs is a polygon from the list of rings rs.

val empty : t

empty is an empty polygon.


val rings : t -> Gg__ring2.t list

rings p are the rings of p.

val box : t -> Gg.Box2.t

box p is a bounding box for the polygon.


val is_empty : t -> bool

is_empty p is true iff p is empty.

Boolean operations

Boolean operations are implemented using this algorithm.

Input polygons can be concave and self-interesting the only constraint is that no two ring edges should overlap in a single input polygon. The orientation of the rings does not matter for the algorithm it determines holes using the even-odd rule: any ring included in an odd number of rings bounds a hole.

Overlap between input polygons is supported.

type holes = int list list

The type for the rings holds, one list per ring in the order of fold_contours. The list has the position of holes in the order of fold_contours. FIXME forget about that and return correctly oriented polygons.

type bool_op_error = [
  1. | `Edge_overlap

    The input polygons have overlapping edges

  2. | `Topology_panic of string

    Internal error, please report the test case.

type bool_op_result = (t * holes, (t * holes) * bool_op_error) Stdlib.result

The type for boolean operation results. Error (_, _, `Edge_overlap) is returned if two contour edges overlap in a single input polygon. In that case there are two edges that overlap in either input polygon. In this case you should be suspicious about the result.

The result polygon is a polygon whose surface can be determined both by the even oddrule and the non-zero winding rule (i.e. contours of holes are clockwise and other contours are counter clockwise). This means that the signed area of contours can be used to compute the resulting surface.


  • The result can contain contours that self intersect seems it only happens with xor. This likely affects surface computation.
  • Holes are not computed for now. Simply interpret the result with the even-odd rule.
val union : t -> t -> bool_op_result

union p0 p1 is the union of p0 and p1.

val diff : t -> t -> bool_op_result

diff p0 p1 is p0 minus p1.

val inter : t -> t -> bool_op_result

inter p0 p1 is the intersection of p0 and p1.

val xor : t -> t -> bool_op_result

xor p0 p1 is the exclusive union of p0 and p1.


val fold_rings : (Gg__ring2.t -> 'a -> 'a) -> t -> 'a -> 'a

fold_rings f p acc folds on the rings of p.