Polyclip: Fast Clipping for Arbitrary Polygons

Introduction

polyclip is a library for fast clipping (intersection) of polygons, written in C++. It supports arbitrarily shaped polygons, including multi-part, self-intersecting and holed polygons. Degenerate cases such as touching and overlapping polygons are also handled. polyclip is free software, available under the GNU LGPL license.

Download

polyclip can be downloaded from its SourceForge repository. The tarball consists of the C++ source files and a few illustrative examples.

Requirements

polyclip is written entirely in C++, and makes extensive use of the Standard Template Library (STL); the only real requirement is a recent C++ compiler e.g., GCC 4.0 or later. It might even work with earlier versions of GCC, but this hasn’t been tested. polyclip has been compiled and tested on GNU/Linux and OS X. On Windows, it is expected that a UNIX-like environment like cygwin should be sufficient.

Installation

Simply extract the tarball, change to the src directory and type make. This will result in a binary named polyclip. After building, type make check to verify the build.

Usage

polyclip expects two polygon data files as inputs; the target polygon file, and the clipping polygon file. The target should be one polygon (either a single-part or multi-part polygon); the clipping polygon can be one or more polygons, each single or multi-part. The usage is:

polyclip <target polygon file> <clipping polygon file> [log file]

polyclip will then calculate the intersection of the target polygon with each clipping polygon. Each polygon data file should be of the following format:

#polygon data file
<num-polys>
# polygon 1 data follows
<poly 1 id> <num parts>
<part 1 id> <type> <num vertices>
# part 1 vertices follow
x1 y1
x2 y2
.
.
.
# part 2 vertices follow
<part 2 id> <type> <num vertices>
x1 y1
.
.
# polygon 2 data follows
 <poly 2 id> <type> <num vertices>
# and so on ..

Lines starting with ‘#’ will be treated as comments and ignored. All other lines will be treated as input data. Data that does not adhere to the above format will result in an error as polyclip is very picky about input format. The output from polyclip is in the same format as above.

Notes:

• <poly id>, <num Parts>, <part id> and <num vertices> should all be integers
• <type> should be either 1 (for solid polygons) or 0 (for holes)
• x and y can be floats or integers.
• Each polygon part should be a single closed polygon i.e first and last points should be the same. A polygon part cannot itself be a multi-part polygon
• [log file] is an optional argument and requires the Google logging framework, and requires some minor modifications to the Makefile (see the Makefile for instructions). Warning: Logging can severely degrade performance.
• Since intersection is a symmetric operation, which polygon is the target and which one is the clipping polygon doesn’t really matter if each input file has only one multi-part polygon.

Examples

Look inside test directory for usage examples.

License

polyclip is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

polyclip was written by Sunil Thulasidasan.