README
¶
About
Library polyclip-go is a pure Go, MIT-licensed implementation of an [algorithm for Boolean operations on 2D polygons] fmartin (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.
Example
Simplest Go program using polyclip-go for calculating intersection of a square and triangle:
// example.go
package main
import (
"fmt"
"github.com/akavel/polyclip-go" // or: bitbucket.org/...
)
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.
Documentation
¶
Overview ¶
Package op provides implementation of algorithms for geometry operations. For further details, consult the description of Polygon.Construct method.
Index ¶
- func Area(g geom.Geom) float64
- func Centroid(g geom.Geom) (geom.Point, error)
- func Clone(p geom.Polygon) geom.Polygon
- func Construct(subject, clipping geom.Geom, operation Op) (geom.Geom, error)
- func Distance(a, b geom.Geom) float64
- func FixOrientation(g geom.Geom) error
- func Length(g geom.Geom) float64
- func PointEquals(p1, p2 geom.Point) bool
- func PointOnSurface(g geom.Geom) (geom.Point, error)
- func Simplify(g geom.Geom, tolerance float64) (geom.Geom, error)
- func Within(inner, outer geom.Geom) (bool, error)
- type InfiniteLoopError
- type Op
- type SimplifyInfiniteLoopError
- type UnsupportedGeometryError
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Area ¶
Function Area returns the area of a polygon, or the combined area of a MultiPolygon, assuming that none of the polygons in the MultiPolygon overlap and that nested polygons have alternating winding directions.
func Centroid ¶
Calculate the centroid of a polygon, from wikipedia: http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon. The polygon can have holes, but each ring must be closed (i.e., p[0] == p[n-1], where the ring has n points) and must not be self-intersecting. The algorithm will not check to make sure the holes are actually inside the outer rings.
func Construct ¶
Function Construct computes a 2D polygon, which is a result of performing specified Boolean operation on the provided pair of polygons (p <Op> clipping). It uses an algorithm described by F. Martínez, A. J. Rueda, F. R. Feito in "A new algorithm for computing Boolean operations on polygons" - see: http://wwwdi.ujaen.es/~fmartin/bool_op.html The 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. "subject" and "clipping" can both be of type geom.Polygon, geom.MultiPolygon, geom.LineString, or geom.MultiLineString.
func Distance ¶
Distance returns the distance between the closest parts of two geometries. Currently, only points are supported.
func FixOrientation ¶
Change the winding direction of the outer and inner rings so the outer ring is counter-clockwise and nesting rings alternate directions.
func Length ¶
Function Length returns the length of a LineString, or the combined length of a MultiLineString.
func PointEquals ¶
Equals returns true if both p1 and p2 describe the same point within a tolerance limit.
func PointOnSurface ¶
Function PointOnSurface returns a point guaranteed to lie on the surface of the shape. It will usually be the centroid, except for when the centroid is not with the shape.
func Simplify ¶
Simplify simplifies a line, multiline, polygon, or multipolygon by removing points according to the tolerance parameter, while ensuring that the resulting shape is not self intersecting (but only if the input shape is not self intersecting).
It is based on the algorithm: J. L. G. Pallero, Robust line simplification on the plane. Comput. Geosci. 61, 152–159 (2013).
Types ¶
type InfiniteLoopError ¶
type InfiniteLoopError struct {
// contains filtered or unexported fields
}
func (InfiniteLoopError) Error ¶
func (e InfiniteLoopError) Error() string
type SimplifyInfiniteLoopError ¶
type SimplifyInfiniteLoopError struct {
// contains filtered or unexported fields
}
SimplifyInfiniteLoopError indicates that the Simplify function has fallen into an infinite loop.
func (SimplifyInfiniteLoopError) Error ¶
func (e SimplifyInfiniteLoopError) Error() string
type UnsupportedGeometryError ¶
func (UnsupportedGeometryError) Error ¶
func (e UnsupportedGeometryError) Error() string
Source Files