polygol

Boolean polygon clipping/overlay operations (union, intersection, difference, xor) on Polygon and MultiPolygon geometry. A Go port of the mfogel/polygon-clipping JS library.

Quickstart

A := [][][][]float64{{{{0.0, 0.0}, {0.0, 6.0}, {6.0, 6.0}, {6.0, 0.0}, {0.0, 0.0}}}}
B := [][][][]float64{{{{5.0, 1.0}, {5.0, 5.0}, {7.0, 5.0}, {7.0, 1.0}, {5.0, 1.0}}}}
C := [][][][]float64{{{{3.0, -2.0}, {3.0, 2.0}, {9.0, 2.0}, {9.0, -2.0}, {3.0, -2.0}}}}

union, _ := polygol.Union(A, B, C)
intersection, _ := polygol.Intersection(A, B, C)
difference, _ := polygol.Difference(A, B, C)
xor, _ := polygol.XOR(A, B, C)

API

polygol only has a single type Geom which represents the coordinate structure of a MultiPolygon:

type Geom [][][][]float64

Each Boolean operation (union, intersection, difference and XOR) takes in one subject Geom with any number of clipping Geom's and then returns a single result Geom:

func polygol.Union(geom polygol.Geom, moreGeoms ...polygol.Geom) (polygol.Geom, error)

Note that particularly large geometries may cause errors that will suggest increasing environment variables POLYGOL_MAX_QUEUE_SIZE and POLYGOL_MAX_SWEEPLINE_SEGMENTS.

Examples

The examples page includes some information on how polygol can interface with Go geometry libraries like paulmach/go.geojson, paulmach/orb and twpayne/go-geom.

Test coverage

At the moment, polygol aims to have 100% test coverage relative to polygon-clipping; all unit and end-to-end tests have been ported over to Go.

Dependencies

polygol only has a single dependency: engelsjk/splay-tree. This is a Go port of the JS library w8r/splay-tree which is used in polygon-clipping. BST splay trees are used for the coordinate rounder, the sweep event priority queue and the sweep line itself.

Why `polygon-clipping`?

The polygon-clipping library is a well-tested implementation of the Martínez-Rueda-Feito algorithm and is also currently used behind-the-scenes in both TurfJS and the OpenStreetMap iD editor. Naively porting this library from JS to Go is intended to provide a fairly robust polygon clipping capability in Go without the need for GEOS bindings.

Improvements

Future improvements may include algorithm restructuring and built-in interfaces to common Go geometry libraries.

Performance

The Martínez-Rueda-Feito polygon clipping algorithm computes the Boolean operations in O((n+k)*log(n)) time, where n is the total number of edges of all polygons and k is the number of intersections between edges.

References

The algorithm implemented here and in polygon-clipping is based on the following paper:

A new algorithm for computing Boolean operations on polygons by Francisco Martínez, Antonio J. Rueda, Francisco R. Feito (2009)

Additional information can also be found in the follow-up paper:

A simple algorithm for Boolean operations on polygons by Francisco Martínez, Carlos Ogayar, Juan R. Jiménez and Antonio J. Rueda (2013)

Implementation survey of the Martínez-Rueda-Feito algorithm

Language	URL	Notes
C++	fmartin/bool_op	original implementation
JavaScript	w8r/martinez	an extension of the original algorithm
JavaScript	mfogel/polygon-clipping	originally forked from w8r/martinez, notably used here and here
JavaScript	mapbox/polyclip	by mourner! archived though
JavaScript	velipso/polybooljs	"based somewhat" on the original
Go	engelsjk/polygol	this one, a port of mfogel/polygon-clipping
Go	toanqng/martinez-rueda	based on kudm761/martinez-rueda-php
Go	akavel/polyclip-go	"known to have bugs"
Rust	21re/rust-geo-booleanop	closely follows w8r/martinez
Python	lycantropos/martinez	port of the original
Python	lycantropos/clipping
PHP	kudm761/martinez-rueda-php	based on the original
C/ActionScript3	akavel/martinez-src	copy of the original with an AS3 port
Scala	JonMcPherson/martinez-polygon-clipper	ported from w8r/martinez

union bug

hello,i meet a bug when unoin polygons
ploygona = [[[116.46277925748878,39.88599],[116.46327,39.88599],[116.46327121548828,39.886109220211566],[116.46431140000675,39.88610711457489],[116.46437815770724,39.88610553470714],[116.46437821516655,39.88610675825216],[116.46437798719191,39.886019937380794],[116.46449012423405,39.88601728357566],[116.465193,39.886019],[116.46520508527627,39.886019012615826],[116.465205,39.886002],[116.46584660810673,39.886000300375876],[116.46595733806026,39.88599648210394],[116.46595682983767,39.88595148862629],[116.466,39.88595],[116.46663,39.88595],[116.4671,39.88594],[116.46709942832697,39.88589866765154],[116.467261,39.885898],[116.46726128624843,39.88594],[116.4679,39.88594],[116.46805881008105,39.88595684350834],[116.468043,39.886048],[116.46815974241039,39.886054984588654],[116.46815777083641,39.88607577565319],[116.46815788779723,39.886075783508765],[116.46815384274812,39.88611558570732],[116.468129,39.886114],[116.46792,39.886295],[116.467879,39.88629483526067],[116.467879,39.886422],[116.467864,39.886578],[116.46784403501898,39.88657731712968],[116.467839,39.886627],[116.4678267404138,39.886723675594055],[116.46778,39.88672],[116.4677801555936,39.886717277112126],[116.46764,39.886712],[116.467014,39.886706],[116.46692,39.886765],[116.466925,39.887255],[116.467228,39.887255],[116.467557,39.887252],[116.46770983916338,39.88726160836621],[116.46769,39.88746],[116.46768690541188,39.88767971575692],[116.46771,39.88768],[116.467711,39.887696],[116.46770801472468,39.88823533974078],[116.46767156440872,39.88823507456137],[116.46761,39.88871],[116.46761,39.88878],[116.46761473983558,39.88888860676638],[116.46760846016662,39.88888874291529],[116.46749545690462,39.88887846989132],[116.46749783782663,39.88886234889874],[116.467406,39.888854],[116.46562163217507,39.888857145646234],[116.46513720883907,39.888850509710124],[116.46513646130968,39.88889586425838],[116.465099,39.891529],[116.46509902876262,39.89152985233281],[116.46509382233967,39.89164750296356],[116.46505847429681,39.89164644112512],[116.46505,39.89166],[116.46504218543848,39.89218357562194],[116.46439781209806,39.892186892859215],[116.46437700037785,39.8921867880231],[116.46437799934012,39.891626370191105],[116.46433003220054,39.89162612856142],[116.46432913903807,39.89154727507503],[116.46418,39.89154],[116.46402,39.89153],[116.46402131828314,39.891488080779375],[116.463751,39.891482],[116.46374671152233,39.891513895753334],[116.4635903,39.8915009],[116.46338,39.89145],[116.4632133,39.8913735],[116.4630362,39.8912531],[116.46301444387001,39.89121807797685],[116.46296532973061,39.891141337364424],[116.4629665,39.8911409],[116.4629477,39.8910689],[116.462941,39.8909845],[116.4629343,39.8908868],[116.4629263,39.8907324],[116.4629142,39.8903707],[116.4629082,39.8900314],[116.4629076,39.8899751],[116.4629047,39.8897277],[116.4629065,39.8896535],[116.4629060377541,39.889344521631685],[116.46289971817896,39.88934449737274],[116.46290084273836,39.889185559645384],[116.4629017869734,39.889185567331936],[116.46290295416163,39.88902060283474],[116.4629,39.88885],[116.4629,39.88877],[116.46289532422891,39.88857001059088],[116.462902,39.887829],[116.46290193254518,39.88782389379261],[116.4628762206468,39.887823976702784],[116.46287400232684,39.88782366764997],[116.46287476934253,39.8877141122413],[116.46287,39.88752],[116.46287,39.88711],[116.4628600101224,39.88647064783323],[116.46278,39.88647],[116.46278,39.8861],[116.46277925748878,39.88599]]]
polygonb = [[[116.458553,39.88791],[116.45857094384326,39.88790553563427],[116.45856,39.88788],[116.4585554,39.887848],[116.45856448239947,39.88781221907734],[116.4587112,39.8878347],[116.4591606,39.8878296],[116.45952,39.8878296],[116.45987912842851,39.887820731401185],[116.4598813171811,39.88786572522166],[116.46016837242065,39.88786341614056],[116.4601663,39.8877617],[116.4602998,39.8877604],[116.46066780447438,39.887752718692184],[116.4606703,39.8878119],[116.4606736,39.8878444],[116.46067457705385,39.88785934421506],[116.460966,39.887857],[116.4610304829428,39.88785653927355],[116.4610285,39.8877514],[116.46124888556602,39.88774876594252],[116.46143624152896,39.8877471103319],[116.46144,39.88792],[116.46144,39.88813],[116.46162616602014,39.88812731264462],[116.46162644189089,39.88813614050829],[116.461844,39.888133],[116.462701,39.888107],[116.46288437670745,39.88810507620295],[116.46289951156183,39.88810521663731],[116.46289532422891,39.88857001059088],[116.4629,39.88877],[116.46290002476694,39.88885143029087],[116.46290295416163,39.88902060283474],[116.4629017869734,39.889185567331936],[116.46290084263367,39.889185576001445],[116.46289971814569,39.889344502074465],[116.46273834940025,39.88934400268843],[116.462497,39.889345],[116.46248448325267,39.889345124362634],[116.46248426575583,39.88936692289501],[116.46248073326008,39.88936695799271],[116.461774,39.88936],[116.46176887366315,39.88925767831632],[116.46165,39.88926071363079],[116.46147137010163,39.88926000543263],[116.46147137010163,39.889328505081636],[116.46128,39.88933],[116.46128,39.88938087151887],[116.46106,39.88938000041751],[116.46106,39.889386707395175],[116.46104787153232,39.88938665937188],[116.46104741421834,39.88938050047763],[116.4609066,39.8893861],[116.46081,39.88939],[116.46075,39.88939],[116.46051,39.8894],[116.4604,39.8894],[116.46001,39.88941],[116.45977,39.88942],[116.45964,39.88943],[116.4593013,39.8894392],[116.45863305962509,39.889449950776175],[116.45863182188327,39.889413562334404],[116.45864,39.88925],[116.45864,39.88919],[116.45867,39.88908],[116.45870000018292,39.88904999987805],[116.45873,39.88903],[116.45879557236869,39.88896442771095],[116.458585,39.888791],[116.45861712636355,39.88853572565184],[116.45862172063282,39.88849707042791],[116.45859959426923,39.88849534476924],[116.45861503309332,39.88836544569761],[116.4586208207688,39.88828984423715],[116.45862073675784,39.88828973863373],[116.4586294031725,39.88817653337766],[116.458631,39.888143],[116.458617,39.888064],[116.458553,39.88791]]]
log is :union error: Unable to complete output ring starting at [116.458553, 39.887910].
Last matching segment found ends at [116.462908, 39.889975].

engelsjk / polygol Goto Github PK

polygol's Introduction

polygol

Quickstart

API

Examples

Test coverage

Dependencies

Why polygon-clipping?

Improvements

Performance

References

Implementation survey of the Martínez-Rueda-Feito algorithm

polygol's People

Contributors

Stargazers

Watchers

Forkers

polygol's Issues

Recommend Projects

Recommend Topics

Recommend Org

Why `polygon-clipping`?