vrd / js-intersect Goto Github PK

I used the following set of data, and found that the data would cause the browser to crash, and debugging found that the polygonate function was stuck in an infinite loop

var range = 50;
var examples = {
  first: [
    { x: -3*range,  y: 3*range  },
    { x: 3*range, y: 3*range   },
    { x: 3*range, y: -3*range  },
    { x: -3*range, y: -3*range }
  ],
  second: [
    { x: -3*range,  y: 3*range  },
    { x: 2.2*range, y: 3*range   },
    { x: 2.2*range, y: -3*range  },
    { x: -3*range, y: -3*range }
  ]

};`

Hello,
I'm using this script for a project and it's very useful, however it seems to have issues with some polygons (or maybe I do something wrong). Here is an example of two intersecting polygons where the script doesn't find any intersection :

[{x:-38383.11684890961,y:975822.2939549877},{x:-38383.08019699532,y:975824.4200341334},{x:-38381.523363302535,y:975824.3935903418},{x:-38381.46925809573,y:975827.5166057295},{x:-38379.9211510492,y:975827.4901618769},{x:-38378.91933205856,y:975827.4742955655},{x:-38379.01183450892,y:975822.2278456159},{x:-38380.21087570504,y:975822.2463562398},{x:-38380.18120510776,y:975823.9942891567},{x:-38380.844430223515,y:975824.0075110482},{x:-38380.874100820794,y:975822.2542893642}]

[{x:-38383.08019699532,y:975824.4200341334},{x:-38381.523363302535,y:975824.3935903418},{x:-38380.823486272486,y:975824.3909459626},{x:-38380.844430223515,y:975824.0075110482},{x:-38380.874100820794,y:975822.2542893642},{x:-38383.11684890961,y:975822.2939549877}]

Hope someone can help me with that

Hi again!

First, I'd like to thank you for your amazing support and for kindely putting your project under the MIT license. Super nice of you!

I'm sorry to come at you again but I'm afraid that there's a couple more bugs. I'll only file one at a time in case your fix would fix them all.

If I use the following 2 polygons :

var poly0 = [
  {x: 926, y: 0},
  {x: 600, y: 500},
  {x: 600, y: 600},
  {x: 799, y: 600},
  {x: 1000, y: 559},
  {x: 1000, y: 0}
];

var poly1 = [
  {x: 1000, y: 400},
  {x: 400, y: 200},
  {x: 200, y: 200},
  {x: 200, y: 300},
  {x: 449, y: 800},
  {x: 1000, y: 800}
];

The intersect() methods return 2 polygons as a result, where it should only return 1, really. (In fact, it returns the proper intersection AND what's left of one of the 2 initial polygons)

I don't know how much more time you want to spend on that lib, but a fix would (of course) be super awesome.

Have a nice day!

Hi guys!

First I'd like to say how cool your lib is! Pretty hard to find that kind of stuff on the web. Great job.

What license is this code under?

Then I'd like to report a bug (hope you're still willing to fix it). The intersect() method crashes for the following polygons :

var poly0 = [
  {x: 358, y: 0},
  {x: 600, y: 600},
  {x: 800, y: 600},
  {x: 800, y: 500},
  {x: 652, y: 0}
];

var poly1 = [
  {x: 1000, y: 400},
  {x: 400, y: 200},
  {x: 200, y: 200},
  {x: 200, y: 300},
  {x: 449, y: 800},
  {x: 1000, y: 800}
];

They are simple polygons so I see no reason why this should crash. The console trace is : "Polygon.js:155 Uncaught TypeError: Cannot read property 'x' of undefined (solution.js:155)"

If you guys could help me there it would be pretty awesome.

Thanks a lot!

Hi again!

The intersect() method is caught in infinite loops sometimes... Works with these 2 polygons :

var poly0 = [
  {x: 1000, y: 800},
  {x: 800, y: 500},
  {x: 600, y: 500},
  {x: 474, y: 800},
  {x: 1000, y: 800}
];

var poly1 = [
  {x: 1000, y: 400},
  {x: 400, y: 200},
  {x: 200, y: 200},
  {x: 200, y: 300},
  {x: 449, y: 800},
  {x: 1000, y: 800}
];

Any idea why those 2 particular polygons would cause that?

Thanks!

Hello! Thanks for this library. I was wondering if you'd be able to help me figure out why some inputs result in an infinite loop, e.g. here are two examples:

Example 1

const b = [{"x":1,"y":0},{"x":1.0000000000000002,"y":1},{"x":0.29289321881345287,"y":1.7071067811865477},{"x":0.2928932188134526,"y":0.7071067811865477}];
const c = [{"x":0.29289321881345254,"y":0.7071067811865476},{"x":1.0000000000000002,"y":1.414213562373095},{"x":2.220446049250313e-16,"y":1.4142135623730951},{"x":-0.7071067811865476,"y":0.7071067811865479}];

intersect(b, c); // infinite loop

In case it's relevant: I've found that if I multiply all the coordinates by 100, this example does return the correct intersection:

const b2 = b.map(p => ({x:p.x*100, y:p.y*100}));
const c2 = c.map(p => ({x:p.x*100, y:p.y*100}));

intersect(b2, c2); // returns the correct result

Example 2

const square = [{"x":99.99999999999999,"y":0},{"x":200,"y":-1.2246467991473532e-14},{"x":200,"y":99.99999999999999},{"x":100,"y":100.00000000000003}];
const octagon = [{"x":0,"y":0},{"x":200,"y":0},{"x":270.71067811865476,"y":70.71067811865476},{"x":270.71067811865476,"y":270.71067811865476},{"x":200,"y":341.4213562373095},{"x":0,"y":341.4213562373095},{"x":-70.71067811865476,"y":270.71067811865476},{"x":-70.71067811865476,"y":70.71067811865474}];

intersect(square, octagon); // infinite loop

My environment

I am using solution.js from the current latest version of the gh-pages branch (with debug code at the end commented out) : https://github.com/vrd/js-intersect/blob/fd759a8d5c21d63b14120eae7c621364dc587858/solution.js

I've tested intersect(b, c), intersect(b2, c2), and intersect(square, octagon) on Chrome and Firefox on MacOS.

In certain circumstances, intersect returns an empty array when there is definitely an intersection. For example:

var rect = [
  { x:  5.35328472172063, y:  3.3464605876540254 },
  { x: 31.10025450900146, y:  3.3464605876540254 },
  { x: 31.10025450900146, y: 38.65353941234598   },
  { x:  5.35328472172063, y: 38.65353941234598   }
];
var triangle = [
  { x: 31.10025450900146, y: 6.964961212615723  },
  { x:  5.35328472172063, y: 3.3464605876540254 },
  { x: 26.64671527827937, y: 38.65353941234598  }
];

console.log(intersect(rect, triangle)); // prints empty array

If we show these input polygons as an SVG it's clear that they fully overlap.

<svg>
  <polygon points="5.35328472172063,3.3464605876540254 31.10025450900146,3.3464605876540254 31.10025450900146,38.65353941234598 5.35328472172063,38.65353941234598" style="fill: purple;"/>
  <polygon points="31.10025450900146,6.964961212615723 5.35328472172063,3.3464605876540254 26.64671527827937,38.65353941234598" style="fill: pink;"/>
</svg>

But this bug can also occur with polygons that partially overlap as well:

var rect = [
  { x: 10.143593539448977, y: 18.143593539448986 },
  { x: 37.856406460551014, y: 18.143593539448986 },
  { x: 37.856406460551014, y: 45.856406460551014 },
  { x: 10.143593539448977, y: 45.856406460551014 }
];
var triangle = [
  { x: 37.856406460551014, y: 18.14359353944898  },
  { x: 10.143593539448977, y:  2.143593539448986 },
  { x: 21.85640646055102,  y: 45.856406460551014 }
];

console.log(intersect(rect, triangle)); // prints empty array

<svg>
  <polygon points="10.143593539448977,18.143593539448986 37.856406460551014,18.143593539448986 37.856406460551014,45.856406460551014 10.143593539448977,45.856406460551014" style="fill: purple;"/>
  <polygon points="37.856406460551014,18.14359353944898 10.143593539448977,2.143593539448986 21.85640646055102,45.856406460551014" style="fill: pink;"/>
</svg>

I personally have no idea what the cause of this bug is, but I've only skimmed the source code of js-intersect.

Hello,

Abs() is taken for each term, but I think it should only be taken for the final sum. It makes a difference.

  for (var i = 0; i < len; i++) {
     s += Math.abs((p[i % len].x * p[(i + 1) % len].y) - (p[i % len].y * p[(i + 1) % len].x));
  }
  return s/2;

becomes

  for (var i = 0; i < len; i++) {
     s += (p[i % len].x * p[(i + 1) % len].y) - (p[i % len].y * p[(i + 1) % len].x);
  }
  return Math.abs(s/2);

Hi!

Here are two polygons that should overlap but seem to return area=0 / zero nodes for intersect call.

When calling var result = intersect(smallcircle, largehalfcircle) it returns 0 while some polygon of some size would be expected.

The polygons looks like this in array form:

smallcircle=[
{ x: 10, y: 0 },
{ x: -10, y: 1.2246467991473533e-15 },
{ x: -10, y: 1.2246467991473533e-15 },
{ x: -9.92546151641322, y: 1.2186934340514755 },
{ x: -9.702957262759965, y: 2.4192189559966772 },
{ x: -9.335804264972015, y: 3.5836794954530067 },
{ x: -8.82947592858927, y: 4.694715627858907 },
{ x: -8.191520442889919, y: 5.73576436351046 },
{ x: -7.431448254773944, y: 6.691306063588581 },
{ x: -6.560590289905072, y: 7.547095802227721 },
{ x: -5.591929034707467, y: 8.290375725550417 },
{ x: -4.5399049973954675, y: 8.910065241883679 },
{ x: -3.420201433256687, y: 9.396926207859085 },
{ x: -2.249510543438648, y: 9.743700647852352 },
{ x: -1.0452846326765333, y: 9.945218953682733 },
{ x: 0.174524064372836, y: 9.998476951563912 },
{ x: 1.3917310096006545, y: 9.902680687415703 },
{ x: 2.5881904510252074, y: 9.659258262890683 },
{ x: 3.746065934159122, y: 9.271838545667872 },
{ x: 4.848096202463371, y: 8.746197071393958 },
{ x: 5.877852522924732, y: 8.090169943749475 },
{ x: 6.819983600624985, y: 7.313537016191704 },
{ x: 7.66044443118978, y: 6.4278760968653925 },
{ x: 8.386705679454241, y: 5.44639035015027 },
{ x: 8.98794046299167, y: 4.383711467890774 },
{ x: 9.455185755993169, y: 3.255681544571567 },
{ x: 9.781476007338057, y: 2.079116908177593 },
{ x: 9.961946980917455, y: 0.8715574274765816 },
{ x: 10, y: 0 }
]
largehalfcircle=[
{ x: -3.4641016151399997, y: 3.6399999999999997 },
{ x: -2.7767585183349683, y: 3.5979602952570557 },
{ x: -2.099662123957873, y: 3.47246789619662 },
{ x: -1.4429063797045063, y: 3.265393605444218 },
{ x: -0.816282001027576, y: 2.979824423724347 },
{ x: -0.22913051412010077, y: 2.620017529789913 },
{ x: 0.30979500472396015, y: 2.1913368156925035 },
{ x: 0.7924604173164336, y: 1.70017292350646 },
{ x: 1.211670294070434, y: 1.1538479755750122 },
{ x: 1.5611751812823944, y: 0.5605064185310433 },
{ x: 1.8357647660925234, y: -0.07100639164322864 },
{ x: 2.031345550248726, y: -0.7312760535006015 },
{ x: 2.1450018747370607, y: -1.4104594671704347 },
{ x: 2.1750393855420467, y: -2.0984315723062843 },
{ x: 2.1210102925624557, y: -2.7849362894147713 },
{ x: 1.9837200451303452, y: -3.4597394143782165 },
{ x: 1.7652153246166802, y: -4.112781186865746 },
{ x: 1.468753533126192, y: -4.7343262581893395 },
{ x: 1.0987542331347027, y: -5.315108822929549 },
{ x: 0.6607332619921222, y: -5.84647075075249 },
{ x: 0.16122050349208106, y: -6.320490659191036 },
{ x: -0.3923374576552501, y: -6.730102003212193 },
{ x: -0.9916883472496036, y: -7.069198421127302 },
{ x: -1.6278972240016387, y: -7.332724766380148 },
{ x: -2.2914796789278418, y: -7.516752468138664 },
{ x: -2.97254322604321, y: -7.618538097237445 },
{ x: -3.6609347765421094, y: -7.636564264387699 },
{ x: -4.3463919979669035, y: -7.570562240956576 },
{ x: -5.018696301947874, y: -7.4215159650921185 },
{ x: -5.667825179819504, y: -7.1916473734717625 },
{ x: -6.284101615140003, y: -6.884383277344233 },
{ x: -6.858338345717552, y: -6.504304276666732 },
{ x: -7.381974824528745, y: -6.057076473909991 },
{ x: -7.847204837757316, y: -5.549367005521084 },
{ x: -8.247092877462244, y: -4.988744650275275 },
{ x: -8.575677534026706, y: -4.383566996217544 },
{ x: -8.828060367044666, y: -3.742855848274705 },
{ x: -9.000478929784824, y: -3.076162733923712 },
{ x: -9.09036285860541, y: -2.393426511916864 },
{ x: -9.096372191155796, y: -1.7048252067897969 },
{ x: -9.018417342128853, y: -1.0206242779585133 },
{ x: -8.85766043877152, y: -0.3510235853637631 },
{ x: -8.616497996244268, y: 0.2939946669475142 },
{ x: -8.298525191099912, y: 0.9048147424927064 },
{ x: -7.908482265481911, y: 1.4723307208367133 },
{ x: -7.452183861032127, y: 1.988082245892128 },
{ x: -6.936432335976713, y: 2.4443806503419117 },
{ x: -6.368916357632706, y: 2.8344235759599137 },
{ x: -5.758096282087513, y: 3.1523963811042695 },
{ x: -5.113078029776235, y: 3.39355882363152 },
{ x: -4.443477337181487, y: 3.554315726988853 },
{ x: -3.7592764083502024, y: 3.632270576015796 },
{ x: -3.4641016151399997, y: 3.6399999999999997 }
]

Thanks for your help!

Sincere Regards
Marcus