# PolyBoolean C++ Library v0.0

Developer's Guide

## The Library Files

The library source code distribution consists of the following files (not including supplementary files):

ObjHeap.h Sort.h pbarea.h pbdefs.h pbgeom.h pbgeom.inl pbimpl.h pbtria.h polybool.h pbgeom.cpp pbpolys.cpp pbsweep.cpp polybool.cpp triacons.cpp triamono.cpp

## Platform and compiler requirements

The compiler you use shall support the C++ standard features like templates, exceptions etc. Also it must support a 64-bit integer type. The library was developed using Microsoft Visual C++ compiler and successfully tested on some UNIX platforms using GNU C++ compiler v2.7.

## Basic data types

### Platform dependent

INT32 | 32-bit signed integer type |

UINT32 | 32-bit unsigned integer type |

INT64 | 64-bit signed integer type |

This types should be defined in `pbdefs.h`. In case of Microsoft Visual C++ compiler they are already defined. Otherwise they are to be defined after the following comment line

// insert platform specific sized integer types here

### Platform independent

struct GRID2 { INT32 x, y; };

`x` and `y` are integers representing point coordinates. The values of `x` and `y `shall be in range [-524288, +524287].

struct VNODE2 { VNODE2 * next; VNODE2 * prev; UINT32 Flags; union { VECT2 p; GRID2 g; }; };

This structure represents a polygon vertex. `next` and `prev` are pointers to the neighbour vertices in a doubly linked list. `Flags` can be used to store additional information. It is guaranteed that the library routines can change only the last 8 bits of this value. `g` represents vertex coordinates. `p` can be used to simplify possible conversions between integer and floating point vertex representations.

struct PLINE2 { PLINE2 * next; VNODE2 * head; UINT32 Count; UINT32 Flags; union { VECT2 vMin; GRID2 gMin; }; union { VECT2 vMax; GRID2 gMax; }; };

This structure represents a closed contour. `next` is a pointer to the next contour in PAREA. `head` is a pointer to head of cyclic doubly linked list of the contour vertices in counter-clockwise order for an outer contour and in clockwise order for a hole. `Count` is the number of the contour vertices. `Flags` contain information about contour orientation. In case of outer contour ` ((Flags & PLINE2::ORIENT) == PLINE2::DIR)`. In case of hole

`((Flags & PLINE2::ORIENT) == PLINE2::INV)`.

`gMin`and

`gMax`contain respectively minimum and maximum coordinates of vertices in the contour, i.e. they determine the contour bounding box.

`vMin`and

`vMax`can be used to simplify possible conversions between integer and floating point vertex representations.

struct PAREA { PAREA * f; PAREA * b; PLINE2 * cntr; PTRIA * tria; UINT32 tnum; };

This structure represents a polygon with possible holes in the plane. `f` and `b` are pointers to the neighbour polygons in a cyclic doubly linked list describing a set of distinct polygons. `cntr` is a pointer to the null-terminated single linked list of polygon contours. The first contour in the list is the polygon outer contour. Next contours are the polygon holes. `tria` and `tnum` are used to store the polygon triangulation. In case of the library version without triangulation routines `(tria == NULL)` and `(tnum == 0)`.

Thus to describe a set of polygons with holes one should use a pointer to `PAREA` structure. The pointer is `NULL` in case of empty polygon. The examples and exact definitions on the polygon description are given in our paper about the polygon Boolean algorithm.

## The library error handling

In case of some errors the library routines throw exceptions. The exception type is *int* and the exception codes are:

err_no_memory | Not enough memory to complete operation |

err_bad_parm | Bad input parameters |

err_io | File I/O error |

## Construction of polygons

The library provides a set of routines for polygon construction. Here are described the most convenient routines.

static void PLINE2::Incl(PLINE2 ** pline, const GRID2 & g);

This routine includes into the contour *pline* new vertex *g*. If `(*pline == NULL)` a new contour is created with first vertex *g* and the pointer to it is assigned to `*pline`.

bool PLINE2::Prepare();

After all vertices are included into a contour, the validation method should be called. It calculate the contour orientation and bounding box and removes coincident vertices and those lying on the same line. The routine returns *true* if the contour has more than 2 vertices after validation and bounds a non-empty area, i.e. the contour is valid.

static void PAREA::InclPline(PAREA ** area, PLINE2 * pline);

This routine includes into the set of polygons *parea* new contour *pline*.

The action depends on *pline*'s orientation (it can be determined by calling `PLINE2::IsOuter()` method and changed by calling `PLINE2::Invert()` method).

- If
*pline*is an outer contour, a new polygon is created and*pline*becomes its outer contour. If`(*area == NULL)`the pointer to the new polygon is assigned to`*area`. Otherwise the new polygon is tied into*area*'s doubly linked list. - If
*pline*is a hole, the smallest container polygon for the hole is searched for. If the search fails, the library exception with code*err_bad_parm*is thrown.

static void PAREA::Del(PAREA ** area);

This routine destroys the contour ***area and sets *area* *to NULL.

PAREA * PAREA::Copy() const;

This method makes a copy of *this *and returns it.

## Boolean operations and triangulation

For polygon Boolean operations the library provides 2 main routines:static int PAREA::Boolean(const PAREA * a, const PAREA * b, PAREA ** r, PAREA::PBOPCODE nOpCode);

This routine performs a Boolean operation *nOpCode* with two sets of polygons *a* and *b*. After the operation is performed, *r* will point to the resulting set of polygons.

static int PAREA::Boolean0(PAREA * a, PAREA * b, PAREA ** r, PAREA::PBOPCODE OpCode);

The difference of this routine from the previous one is that it changes input polygons *a* and *b*. This routine can be used to avoid unnecessary copying of polygons in case of repeated polygon operations.

static int PAREA::Triangulate(PAREA * area);

This routine triangulates *area* and assigns its *tria* and *tnum* fields. *tria* is the array of triangles each consisting of 3 pointers to corresponding vertices in *area*.

## Restrictions

All restrictions of the current version of library described **here**.

## Example of use

Here is the example piece of code for performing Boolean operation XOR with the polygons shown in figure below.

#include "polybool.h" using namespace POLYBOOLEAN; int main() { static const GRID2 a1[4] = { {-7, 8}, {-7, -3}, {2, -3}, {2, 8} }; static const GRID2 a2[4] = { {-5, 6}, {0, 6}, {0, 0}, {-5, 0} }; static const GRID2 b[11] = { {-5, -6}, {7,-6}, {7, 4}, {-5, 4}, {0, 0}, {0, 2}, {5, 2}, {5, -4}, {0, -4}, {0, 0}, {-5, 0} }; PAREA * A = NULL; // construct 1st polygon { PLINE2 * pline = NULL; for (i = 0; i < 4; i++) PLINE2::Incl(&pline, a1[i]); pline->Prepare(); { // make sure the contour is outer if (not pline->IsOuter()) pline->Invert(); } PAREA::InclPline(&A, pline); pline = NULL; for (int i = 0; i < 4; i++) PLINE2::Incl(&pline, a2[i]); pline->Prepare(); { // make sure the contour is a hole if (pline->IsOuter()) pline->Invert(); } PAREA::InclPline(&A, pline); } PAREA * B = NULL; // construct 2nd polygon { PLINE2 * pline = NULL; for (int i = 0; i < 11; i++) PLINE2::Incl(&pline, b[i]); pline->Prepare(); { // make sure the contour is outer if (not pline->IsOuter()) pline->Invert(); } PAREA::InclPline(&B, pline); } // do Boolean operation XOR PAREA * R = NULL; int err = PAREA::Boolean(A, B, &R, PAREA::XR); // do some things with R // ..................... // delete all polygons { PAREA::Del(&A); PAREA::Del(&B); PAREA::Del(&R); } }