About

Library polyclip-go is a pure Go, MIT-licensed implementation of an algorithm for Boolean operations on 2D polygons (invented by F. Martínez, A.J. Rueda, F.R. Feito) -- that is, for calculation of polygon intersection, union, difference and xor.

The original paper describes the algorithm as performing in time O((n+k) log n), where n is number of all edges of all polygons in operation, and k is number of intersections of all polygon edges.

Limitations

• Although the algorithm will not produce self-intersecting polygons, it is not designed to handle them either. To remove self-intersections from polygons, use MakeValid().

Example

Simplest Go program using polyclip-go for calculating intersection of a square and triangle:

// example.go
package main

import (
    "fmt"
    "github.com/ctessum/polyclip-go"
)

func main() {
    subject := polyclip.Polygon{{{1, 1}, {1, 2}, {2, 2}, {2, 1}}} // small square
    clipping := polyclip.Polygon{{{0, 0}, {0, 3}, {3, 0}}}        // overlapping triangle
    result := subject.Construct(polyclip.INTERSECTION, clipping)

    // will print triangle: [[{1 1} {1 2} {2 1}]]
    fmt.Println(result)
}

To compile and run the program above, execute the usual sequence of commands:

go get github.com/akavel/polyclip-go  # or: bitbucket.org/...
go build example.go
./example      # Windows: example.exe

For full package documentation, run locally godoc github.com/akavel/polyclip-go, or visit online documentation for polyclip-go.

See also

• Online docs for polyclip-go.
• Microsite about the original algorithm, from its authors (with PDF, and public-domain code in C++).
• The as3polyclip library -- a MIT-licensed ActionScript3 library implementing this same algorithm (it actually served as a base for polyclip-go). The page also contains some thoughts with regards to speed of the algorithm.