mrfclip

A Tcl implementation of the Martinez et al polygon clipping algorithm: http://www.cs.ucr.edu/~vbz/cs230papers/martinez_boolean.pdf

Install

Download and directly load into Tcl

lappend auto_path /path/to/mrfclip
package require mrfclip

Features

• Supports the following boolean operations
  • AND - intersection
  • OR - union
  • NOT - difference
  • XOR - (A NOT B) OR (B NOT A)
• Supports degenerate cases
• Supports holes*
• Runs in O((n + k) log n) time*, where n is the number of input vertices and k is the number of intersections

Examples

• AND, OR, NOT, and XOR

• Self-intersecting (second image showing holes, though improperly drawn)

• Degenerate

See Tests for more example cases.

Usage

Clipping is done by forming expressions with mrfclip::clip.

set poly1 {0 0 0 10 10 10 10 0}
set poly2 {5 5 5 15 15 15 15 5}
set result [mrfclip::clip $poly1 AND $poly2]
# {10.0 10.0 10.0 5.0 5.0 5.0 5.0 10.0}

Expressions can be strung together

set poly3 {0 2.5 20 2.5 20 7.5 0 7.5}
mrfclip::clip $poly1 AND $poly2 OR $poly3
# {20.0 7.5 20.0 2.5 0.0 2.5 0.0 7.5 5.0 7.5 5.0 10.0 10.0 10.0 10.0 7.5}

and embedded

mrfclip::clip $poly1 AND [mrfclip::clip $poly2 OR $poly3]
# {10.0 10.0 10.0 2.5 0.0 2.5 0.0 7.5 5.0 7.5 5.0 10.0}

Multiple polygon (possibly disjoint) input is supported

set poly1 {{0 0 0 10 10 10 10 0} {10 10 10 20 20 20 20 10}}
set poly2 {5 5 5 15 15 15 15 5}
mrfclip::clip $poly1 AND $poly2
# {10.0 10.0 10.0 5.0 5.0 5.0 5.0 10.0} {15.0 15.0 15.0 10.0 10.0 10.0 10.0 15.0}

Polygons are clipped strictly left to right. Use command substitution as shown above to achieve the desired clipping.

Polygon Format

Polygons must be specified as a flat list of coordinates.

set poly {0 0 10 0 10 10 0 10 0 0}

They can be specified in either form:

• closed: The first and last coordinate are the same.

set closed   {0 0 10 0 10 10 0 10 0 0}

• unclosed: The first and last coordinate are automatically connected.

set unclosed {0 0 10 0 10 10 0 10}

The result will always be in unclosed form.

Multiple Polygons

Clipping may result in multiple polygons, in which case a list of polygons is returned (a multi-polygon). For this reason, the return value of mrfclip::clip is always a list of list(s) regardless of the actual result, and multi-polygons can also be used directly as input to mrfclip::clip

Known Issues

• Polygons with self-overlapping edges are supported, but it has not been exhaustively tested.
• While holes are supported as input and output, there is no special handling when returning holes. Holes and their enclosing polygons are not associated, and may be returned in any order.
• The last part of the algorithm is currently implemented in O(n²) time in the worst case. The worst case occurs when the result is a single or few long chain(s). I plan to change the algorithm to work in O(n log n) time or better in the near future™.

Tests

    cd tests
    make all
    make png

See tests/README.md for more details.