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 succesfuly tested on some UNIX platforms using GNU C++ compiler v2.7.

Basic data types

Platform dependent

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

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);
    }
} // main