Intersection Bug

[carmandrew]

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.

[akavel]

Thanks for the report. Unfortunately I must warn that I can't promise when I'll be able to investigate it, as it's purely a hobby project of mine, and one I haven't much personal uses for currently, so not actively pursued. That said, I'm occasionally trying to attend to it, when I find enough time and motivation. Please note I'm certainly grateful for your report, and that you cared to include the picture.

I'm also updating the README now, to make it clear that the library has known bugs, unfortunately, which I haven't been able to squash easily for the time being.

[carmandrew]

No worries, totally understand. Thanks for updating the readme and replying to the issue so promptly!

[ctessum]

Is the winding order correct for both polygons? I think if one clockwise and the other is counterclockwise, or they are both winding in the wrong direction (although I don't remember which is the correct direction), that may cause the problem.

[akavel]

I seem to believe that winding should be irrelevant for the algorithm; although as I believe I wrote elsewhere, I can't really say I 100% understand all of its details (otherwise I could probably resolve the #3, which might have a chance of resolving this one too [or not]).

[ctessum]

I've added a test in #10. It doesn't return an empty polygon, but it also doesn't exactly return the inner polygon as expected.

[boyand]

Hey guys. Did anyone manage to get to the bottom of this ? Or perhaps have an idea for alternative solutions ?

[carmandrew]

We ended up using https://github.com/paulsmith/gogeos instead, along with the command line tool http://www.gdal.org/ogr2ogr.html to get the files into the appropriate format.

[rahulbasu]

@carmandrew I haven't checked out the library yet but I think your polygon definitions are in clockwise order. In many libraries the points need to be CCW (i.e., the polygon vertices need to be positively oriented)