akavel / polyclip-go Goto Github PK

Go library for Boolean operations on 2D polygons.

Go 100.00%

polygon go csg polygon-intersection geometry xy polyclip planar buggy mit

polyclip-go's Introduction

WARNING

The library is KNOWN TO HAVE BUGS!!! Unfortunately, currently I don't have resources to investigate them thoroughly enough and in timely fashion. In case somebody is interested in taking ownership of the library, I'm open to ceding it. That said, the issues totally haunt me and occasionally I stubbornly try to come back to them and pick the fight up again. In particular:

#3 was confirmed to be an omission in the original paper/algorithm. As far as I understand, it surfaces when one of the polygons used has self-overlapping edges (e.g. when an edge (0,0)-(1,1) is used twice in the same polygon). I believe it should be possible to fix, but it requires thorough analysis of the algorithm and good testing. One attempt I made at a fix which seemed OK initially was later found to break the library even more and thus I reverted it.
#8 was reported recently and I haven't yet had time to even start investigating it.

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.

polyclip-go's People

Contributors

Stargazers

Watchers

Forkers

slash2314 ctessum cjmxp preng69 vbenso oceanful peterwilliams97 cotati sun1752709589 rileydutton fungkd fbigabig hookttg

polyclip-go's Issues

XOR bug

case XOR:

subject:  [[{0 0} {2 0} {2 2} {0 2} {0 0}] [{4 0} {6 0} {6 2} {4 2} {4 0}]]

clipping: [[{1 1} {5 1} {5 3} {1 3} {1 1}]]

expected: [[{0 0} {2 0} {2 1} {1 1} {1 2} {0 2} {0 0}] [{4 0} {6 0} {6 2} {5 2} {5 1} {4 1} {4 0}] [{1 2} {2 2} {2 1} {2 1} {4 1} {4 2} {5 2} {5 3} {1 3}]]

got:      [[{4 1} {5 1} {5 2} {4 2}] [{0 0} {2 0} {2 1} {1 1} {1 2} {0 2}] [{1 2} {2 2} {2 1} {4 1} {4 0} {6 0} {6 2} {5 2} {5 3} {1 3}]]

This appears to be another issue of the algorithm getting the right points but connecting them in the wrong way.

Contour Overlaps support?

I am looking for an implementation to find out if a Contour overlaps with another contour. I hacked in something just so I could get an idea working (https://github.com/lateefj/geostream/blob/master/geo.go#L56) but I am sure there is a better algorithm. Any plans to add an overlaps support anytime soon?

Operations Fail

I have been working with this library a lot the last couple weeks. I am working on an application that draws SVG files based on dynamic input. I have been having a lot of issues with this library, but I have been having a hard time isolating the problem.

I have written a small test application to allow me to enter different configuration details to try to isolate why the library is failing. Hopefully you guys can help me figure out what is going on. If we can figure out why things are failing I am up for working on a pull request.

Alright, lets get down to business...

I wrote a test application called polycliptest and I have made everything available here: https://objects-east.cloud.ca/v1/5ef827605f884961b94881e928e7a250/polycliptest/polycliptest.zip
This includes the application cross compiled for all OS's as well as the src and a few sample SVG files.

The core of the test is based around a function I wrote which allows you to create a dynamic polygon circle. The function takes coordinates, a radius and the number of line segments for each 90º of the circle. So if segments=1, a diamond will be drawn. If segments=3, then a 12 sided 'circle' will be created. This allows me to easily create different polygons to test the polyclip library. The test basically creates a rectangle and a circle with one edge of the rectangle centered in the circle. I then run each of the polyclip operations on the two polygons. Then via the command line, I can change the number of segments which make up the circle to find cases where everything fails.

The default configuration is a simple working example to show how the test works. This is just to give a foundation for how the test works. The output for this test is polycliptest_default_ok.svg. Here are a bunch of examples for how the test application works...

All of the details of the contours and polygons being drawn are also output to the terminal for inspection.

Test Examples:

$ ./polycliptest -h
Usage of ./polycliptest:
  -add_right_circle=false: add an additional circle on the right side of the rectangle
  -radius=8: the radius of the circles at the ends of the slot
  -segments=1: the number of segments per 1/4 circle at the ends of the slot

$ ./polycliptest
=> polycliptest_default_ok.svg
=> this example works correctly

$ ./polycliptest -segments=3
=> polycliptest_seg-3_ok.svg
=> this example works correctly

$ ./polycliptest -segments=15
=> polycliptest_seg-15_fails.svg
=> this example fails on all operations

$ ./polycliptest -add_right_circle
=> polycliptest_default_add_ok.svg
=> in this example, we add an additional circle to the right of the rectangle.
=> this is working (even though it may be a bit confusing what is polygon and what is empty space)

As I said before, I am willing to put in some time to try to solve these problems and providing a pull request, but I need some help understanding why things are failing. I thought it might have to do with the points being too close together, but I proved that incorrect with the following:

$ ./polycliptest -radius=3 -segments=17  ==> OK
$ ./polycliptest -radius=3 -segments=18  ==> FAILS
$ ./polycliptest -radius=3 -segments=19  ==> OK

I am looking forward to some fresh eyes on this problem. :)

Let me know if you have any issues running my test application or if you need help compiling it (it depends on my fork of the svgo library which adds floating point support).

Cheers...

Intersection Bug

I'm using this library to determine which ZIP codes are within a given area. Unfortunately, it seems to be incorrectly calculating INTERSECTION some of the time. Here is an example:

func main() {
    inner := polyclip.Polygon{{{-118.265137, 33.953797}, {-118.265134, 33.954691}, {-118.265132, 33.955589}, {-118.265129, 33.956488}, {-118.265126, 33.957423}, {-118.265124, 33.958072}, {-118.265124, 33.958316}, {-118.265121, 33.959223}, {-118.265118, 33.96013}, {-118.262929, 33.96014}, {-118.261025, 33.960148}, {-118.260753, 33.960149}, {-118.260754, 33.959772}, {-118.258575, 33.959577}, {-118.258573, 33.96016}, {-118.256393, 33.960171}, {-118.256261, 33.96017}, {-118.255899, 33.960169}, {-118.255114, 33.960167}, {-118.253959, 33.960162}, {-118.253962, 33.959701}, {-118.252067, 33.959706}, {-118.251372, 33.959711}, {-118.250541, 33.959716}, {-118.250002, 33.959719}, {-118.249708, 33.959715}, {-118.249199, 33.959708}, {-118.248886, 33.959708}, {-118.24852, 33.959721}, {-118.248057, 33.959708}, {-118.247225, 33.9597}, {-118.247237, 33.959175}, {-118.246653, 33.959177}, {-118.246648, 33.959637}, {-118.246276, 33.959647}, {-118.245409, 33.95965}, {-118.244994, 33.959648}, {-118.244995, 33.959785}, {-118.24499, 33.960148}, {-118.244396, 33.960147}, {-118.244156, 33.960147}, {-118.243842, 33.960146}, {-118.243399, 33.960136}, {-118.243328, 33.960136}, {-118.243243, 33.960139}, {-118.243139, 33.96014}, {-118.243054, 33.960141}, {-118.242619, 33.960144}, {-118.242509, 33.960144}, {-118.241957, 33.960142}, {-118.24176, 33.960143}, {-118.241369, 33.960144}, {-118.240794, 33.960148}, {-118.240367, 33.960146}, {-118.240226, 33.960143}, {-118.239675, 33.960139}, {-118.239085, 33.960145}, {-118.238951, 33.960146}, {-118.238527, 33.960146}, {-118.237949, 33.96015}, {-118.237949, 33.959732}, {-118.237944, 33.958904}, {-118.237943, 33.958518}, {-118.23771, 33.958519}, {-118.23737, 33.958521}, {-118.237377, 33.958902}, {-118.237376, 33.958996}, {-118.237366, 33.960152}, {-118.23682, 33.960153}, {-118.236218, 33.960144}, {-118.235942, 33.960145}, {-118.235688, 33.960146}, {-118.235191, 33.960152}, {-118.235091, 33.960153}, {-118.234652, 33.960161}, {-118.234606, 33.960188}, {-118.234555, 33.96021}, {-118.234014, 33.960142}, {-118.233752, 33.960145}, {-118.23325, 33.960141}, {-118.232829, 33.960142}, {-118.232203, 33.960144}, {-118.231599, 33.960146}, {-118.231722, 33.960819}, {-118.231777, 33.961072}, {-118.231885, 33.961565}, {-118.231626, 33.961594}, {-118.231497, 33.961608}, {-118.230013, 33.961768}, {-118.229694, 33.961492}, {-118.229543, 33.96138}, {-118.229366, 33.961248}, {-118.229647, 33.9612}, {-118.231485, 33.960938}, {-118.230857, 33.958577}, {-118.230677, 33.957687}, {-118.230648, 33.957581}, {-118.230618, 33.957428}, {-118.230287, 33.955894}, {-118.230276, 33.955861}, {-118.230059, 33.954899}, {-118.229939, 33.954349}, {-118.229834, 33.953884}, {-118.229699, 33.953293}, {-118.229574, 33.952702}, {-118.229349, 33.95165}, {-118.229216, 33.951085}, {-118.229148, 33.950778}, {-118.228966, 33.949909}, {-118.228937, 33.949773}, {-118.228783, 33.949085}, {-118.228533, 33.948001}, {-118.228367, 33.947223}, {-118.228237, 33.946625}, {-118.228065, 33.945824}, {-118.228021, 33.945621}, {-118.227476, 33.943091}, {-118.227405, 33.942705}, {-118.227354, 33.94253}, {-118.227323, 33.942394}, {-118.227206, 33.94181}, {-118.227038, 33.940938}, {-118.227021, 33.940855}, {-118.226979, 33.940605}, {-118.226906, 33.940167}, {-118.226803, 33.940162}, {-118.226702, 33.939263}, {-118.226605, 33.938729}, {-118.226507, 33.938196}, {-118.226571, 33.938003}, {-118.226922, 33.937956}, {-118.22691, 33.937885}, {-118.226842, 33.937532}, {-118.226772, 33.937096}, {-118.228255, 33.936958}, {-118.228311, 33.936951}, {-118.228374, 33.937366}, {-118.229213, 33.937331}, {-118.229038, 33.937917}, {-118.22896, 33.93818}, {-118.228753, 33.938874}, {-118.22964, 33.938877}, {-118.230678, 33.938881}, {-118.231717, 33.938885}, {-118.232532, 33.938888}, {-118.232758, 33.938888}, {-118.233796, 33.938892}, {-118.234834, 33.938896}, {-118.235872, 33.9389}, {-118.236911, 33.938904}, {-118.23795, 33.938907}, {-118.239021, 33.938911}, {-118.239023, 33.938414}, {-118.239023, 33.938259}, {-118.239024, 33.937895}, {-118.240034, 33.93858}, {-118.2401, 33.938583}, {-118.240444, 33.938283}, {-118.242742, 33.938456}, {-118.242759, 33.938529}, {-118.242774, 33.93865}, {-118.242777, 33.938717}, {-118.242705, 33.939789}, {-118.24318, 33.941513}, {-118.243172, 33.941171}, {-118.243212, 33.940957}, {-118.243239, 33.940775}, {-118.243263, 33.940553}, {-118.243297, 33.940268}, {-118.243339, 33.940043}, {-118.24341, 33.939532}, {-118.243644, 33.938217}, {-118.24369, 33.938}, {-118.243742, 33.937853}, {-118.243999, 33.937852}, {-118.246256, 33.937842}, {-118.246949, 33.937839}, {-118.246961, 33.938337}, {-118.251314, 33.938346}, {-118.254167, 33.938272}, {-118.254161, 33.938817}, {-118.254156, 33.939249}, {-118.256534, 33.939258}, {-118.256533, 33.938755}, {-118.258676, 33.938811}, {-118.260566, 33.938862}, {-118.260694, 33.93875}, {-118.260819, 33.938762}, {-118.26082, 33.939275}, {-118.262726, 33.939282}, {-118.262965, 33.939283}, {-118.263128, 33.939283}, {-118.265158, 33.939292}, {-118.265158, 33.940145}, {-118.265158, 33.941025}, {-118.265159, 33.941825}, {-118.265087, 33.941916}, {-118.264992, 33.942047}, {-118.26499, 33.943506}, {-118.26499, 33.943754}, {-118.264704, 33.943741}, {-118.26443, 33.943712}, {-118.264159, 33.943667}, {-118.263775, 33.943582}, {-118.263776, 33.945463}, {-118.264364, 33.945455}, {-118.264588, 33.945605}, {-118.264884, 33.945601}, {-118.265161, 33.945599}, {-118.265158, 33.94643}, {-118.265158, 33.946512}, {-118.265157, 33.946839}, {-118.265156, 33.947262}, {-118.265156, 33.947448}, {-118.265153, 33.948344}, {-118.26515, 33.949231}, {-118.265148, 33.94966}, {-118.265147, 33.950207}, {-118.265145, 33.951107}, {-118.265143, 33.951536}, {-118.265142, 33.951909}, {-118.265142, 33.952}, {-118.265139, 33.9529}, {-118.265137, 33.953797}}}
    outer := polyclip.Polygon{{{-118.8858033, 34.1845418}, {-118.8610874, 34.236767}, {-118.8748169, 34.2889919}, {-118.8614273, 34.3261425}, {-118.666763299999985, 34.3218895}, {-118.45047, 34.335215}, {-118.3059311, 34.3349315}, {-117.9890442, 34.198741}, {-117.8709412, 34.1561363}, {-117.8125763, 34.1544316}, {-117.708892800000015, 34.1635227}, {-117.649841, 34.164091}, {-117.651201499999985, 34.0594229}, {-117.652588, 34.031038}, {-117.810516, 34.025348}, {-117.846222, 33.999166}, {-117.934113, 33.993473}, {-118.02475, 34.032176}, {-118.0673412, 34.0011525}, {-118.098908100000017, 33.9430755}, {-118.1016541, 33.8746915}, {-118.192993, 33.872134}, {-118.208771, 33.827075}, {-118.224935, 33.791549}, {-118.242623, 33.775203}, {-118.2439614, 33.7603111}, {-118.227138600000018, 33.7060626}, {-118.343353300000018, 33.6637822}, {-118.834991499999987, 33.9775311}, {-118.902282700000015, 34.0390047}, {-118.8858033, 34.1845418}}}
    result := inner.Construct(polyclip.INTERSECTION, outer)
    fmt.Println(result)
}

For reference on a map, these polygons look like:

The intersection should be the entire inner polygon, however it returns an empty intersection.

Infinite loop

Hello,

I have found a bug. Adding the test below to bugs_test.go causes an infinite loop.

    {
        subject: polyclip.Polygon{{{1.427255375e+06, -2.3283064365386963e-10},
            {1.4271285e+06, 134.7111358642578}, {1.427109e+06, 178.30108642578125}}},
        clipping: polyclip.Polygon{{{1.416e+06, -12000}, {1.428e+06, -12000},
            {1.428e+06, 0}, {1.416e+06, 0}, {1.416e+06, -12000}}},
        result: polyclip.Polygon{},
    },

Uncommenting the text below fixes the infinite loop, but it causes some of the other bug tests to fail.

////if numIntersections == 2 && e1.p.Equals(e2.p) {
//if numIntersections == 2 && e1.polygonType == e2.polygonType {
//  return // the line segments overlap, but they belong to the same polygon
//}

I've been trying to find a way to fix both problems at the same time, but it seems to be over my head. If you have time to take a look at it I'd be grateful!

Detect holes

Is there an easy way to detect if one of the polygons returned by the clipper in DIFFERENCE mode is a hole? Used to a convention from another clipper library where holes are clockwise and non-holes are counter-clockwise, but that doesn't seem to be the case here.

I'll have to add hole detection externally if that's not something provided by this library.

Union bug

package main

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

func main() {
    subject  := polyclip.Polygon{{{1,1}, {1,2}, {2, 2}, {2, 1}}}
    clipping := polyclip.Polygon{{{2,1}, {2,2}, {3, 2}, {3, 1}},
                                 {{1,2}, {1,3}, {2, 3}, {2, 2}},
                                 {{2,2}, {2,3}, {3, 3}, {3, 2}}}
    result := subject.Construct(polyclip.UNION, clipping)
    fmt.Println(result)
}

prints:

[[{2 2} {2 3} {1 3} {1 2} {1 1} {2 1} {3 1} {3 2}]]

which looks incorrect...

(4 touching rectangles, the upper right one is lost after union)