mapbox / lineclip

A very fast JavaScript polyline and polygon clipping library
ISC License
173 stars 25 forks source link

Polygon Returning Incorrect Result #6

Open srt19170 opened 7 years ago

srt19170 commented 7 years ago

For this test case polygon() seems to return an incorrect result:

// Bounding box var bbp = [-123.5006568260586, -268.5301901840667, -113.19703085688374, -261.59299895444263]; // Test polygon var poly = [ [-127.7861230010377, -316.24149777631044], [-116.70896693414316, -294.6055724833417], [-112.85776301568613, -270.41743161420106], [-108.94104548638926, -246.3102843974042], [-113.9284569854127, -222.40054013470888], [-100.48054530104075, -224.3864178730988], [-95.49313380201731, -248.2961621357941], [-99.40985133131419, -272.40330935259095], [-103.26105524977122, -296.5914502217316], [-114.33821131666575, -318.2273755147003] ]; let t1 = lineclip.polyclip(poly, bb); // t1 = [[-113.19703085688374, -268.5301901840667], [-113.19703085688374, -261.59299895444263], [-113.19703085688374, -261.59299895444263], [-113.19703085688374, -268.5301901840667]]; Note that the x coordinate of the intersection box is exactly xmax. It looks to me like the polygon hits the bounding box in exactly the upper right corner. I think that case should return no intersection or just the point intersection, but what actually gets returned is the entire right side of the bounding box.

paulmach commented 7 years ago

I get the same issue, but worse, I think it is when the first (and maybe last) edge of the polygon crosses into the bounding box.

Here is code:

lineclip = require('lineclip');

var r1 = lineclip.polygon(
    [[0, 2], [2, 0], [4, 2], [2, 4], [0, 2]], // diamond that clips the corners of the bound.
    [0.5, 0.5, 3.5, 3.5]);

console.log('diamond staring on right', r1);

var r2 = lineclip.polygon(
    [[4, 2], [2, 4], [0, 2], [2, 0], [4, 2]],
    [0.5, 0.5, 3.5, 3.5]);

console.log('diamond staring on left', r2);

results:

diamond staring on right
 [ [ 0.5, 1.5 ],
  [ 1.5, 0.5 ],
  [ 2.5, 0.5 ],
  [ 3.5, 1.5 ],
  [ 3.5, 2.5 ],
  [ 2.5, 3.5 ],
  [ 1.5, 3.5 ],
  [ 0.5, 2.5 ] ]
diamond staring on left
 [ [ 3.5, 2.5 ],
  [ 2.5, 3.5 ],
  [ 1.5, 3.5 ],
  [ 0.5, 2.5 ],
  [ 0.5, 1.5 ],
  [ 1.5, 0.5 ],
  [ 2.5, 0.5 ],
  [ 3.5, 1.5 ] ]

Note: that while the input is closed polygon ring, the output endpoints do not match.

paulmach commented 7 years ago

Sorry, my issue is different. I had a similar related issue but got confused :(