Run results for: point in triangle

Run details:

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36

Browser: Chrome 58

Operating system: Linux

Device Platform: Other

Date tested: 7 years ago

Test name	Executions per second
winding	212920.8 Ops/sec
bary	377547.8 Ops/sec
bary2	319438.4 Ops/sec
half planes	203060.2 Ops/sec
half planes with normal	179106.9 Ops/sec
half planes with normal and vars	186834.0 Ops/sec

Script Preparation code:

/*  var polygon = [{x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}];
  px = Math.random();
  py = Math.random();
var v0x = polygon[1].x-polygon[0].x;
var v0y = polygon[1].y-polygon[0].y;
var v1x = polygon[2].x-polygon[0].x;
var v1y = polygon[2].y-polygon[0].y;

// if v0 cross v1 is positive, triangle is counter clockwise when viewed from above.
var normal = v0x*v1y - v1x*v0y;

point {x: 47.87142596679951, y: -6.500680708968048}
triangle
"{"a":{"x":-40.49496078491211,"y":-8.738582611083984},
  "b":{"x":-41.94913723574891,"y":-6.313193949870829},
  "c":{"x":-41.94775545887751,"y":-6.315498584878696}
*/
debugger;

Tests:

winding
var polygon = [{x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}]; px = Math.random(); py = Math.random(); var v0x = polygon[1].x-polygon[0].x; var v0y = polygon[1].y-polygon[0].y; var v1x = polygon[2].x-polygon[0].x; var v1y = polygon[2].y-polygon[0].y; // if v0 cross v1 is positive, triangle is counter clockwise when viewed from above. var normal = v0x*v1y - v1x*v0y; var length = polygon.length; var windingNumber = 0; var i = 0; var l = polygon.length - 1; var edgePoint1 = polygon[l]; var edgePoint2; for (; i <= l; i++) { edgePoint2 = polygon[i]; var edgePoint1x = edgePoint1.x; var edgePoint1y = edgePoint1.y; var edgePoint2x = edgePoint2.x; var edgePoint2y = edgePoint2.y; // if it passes the point going upward if ( edgePoint1y <= py && edgePoint2y > py) { // and the point is to the left // EQUATION COPIED FROM GeometryUtils.isLeft for performance reasons if ((edgePoint2x - edgePoint1x) * (py - edgePoint1y) - (px - edgePoint1x) * (edgePoint2y - edgePoint1y) > 0 ) { // increment windingNumber windingNumber++; } } // else if it passes the point going down else if ( edgePoint1y > py && edgePoint2y <= py) { // and the point is to the right if ((edgePoint2x - edgePoint1x) * (py - edgePoint1y) - (px - edgePoint1x) * (edgePoint2y - edgePoint1y) < 0) { // decrement windingNumber windingNumber--; } } edgePoint1 = edgePoint2; } // the point is inside the polygon as long as the winding number isn't zero. return windingNumber !== 0;
bary
var polygon = [{x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}]; px = Math.random(); py = Math.random(); var v0x = polygon[1].x-polygon[0].x; var v0y = polygon[1].y-polygon[0].y; var v1x = polygon[2].x-polygon[0].x; var v1y = polygon[2].y-polygon[0].y; // if v0 cross v1 is positive, triangle is counter clockwise when viewed from above. var normal = v0x*v1y - v1x*v0y; var a = polygon[0]; var b = polygon[1]; var c = polygon[2]; // Compute vectors var v0x = c.x - a.x; var v0y = c.y - a.y; var v1x = b.x - a.x; var v1y = b.y - a.y; var v2x = px - a.x; var v2y = py - a.y; var dot00 = v0x * v0x + v0y * v0y; var dot01 = v0x * v1x + v0y * v1y; var dot02 = v0x * v2x + v0y * v2y; var dot11 = v1x * v1x + v1y * v1y; var dot12 = v1x * v2x + v1y * v2y; var denom = dot00 * dot11 - dot01 * dot01; var u = (dot11 * dot02 - dot01 * dot12) / denom; var v = (dot00 * dot12 - dot01 * dot02) /denom; // Check if point is in triangle return (u >= 0) && (v >= 0) && (u + v < 1);
bary2
var polygon = [{x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}]; px = Math.random(); py = Math.random(); var v0x = polygon[1].x-polygon[0].x; var v0y = polygon[1].y-polygon[0].y; var v1x = polygon[2].x-polygon[0].x; var v1y = polygon[2].y-polygon[0].y; // if v0 cross v1 is positive, triangle is counter clockwise when viewed from above. var normal = v0x*v1y - v1x*v0y; var a = polygon[0]; var b = polygon[1]; var c = polygon[2]; var ax = a.x; var ay = a.y; // Compute vectors var v0x = c.x - ax; var v0y = c.y - ay; var v1x = b.x - ax; var v1y = b.y - ay; var v2x = px - ax; var v2y = py - ay; var dot00 = v0x * v0x + v0y * v0y; var dot01 = v0x * v1x + v0y * v1y; var dot02 = v0x * v2x + v0y * v2y; var dot11 = v1x * v1x + v1y * v1y; var dot12 = v1x * v2x + v1y * v2y; var denom = dot00 * dot11 - dot01 * dot01; var u = (dot11 * dot02 - dot01 * dot12) / denom; var v = (dot00 * dot12 - dot01 * dot02) /denom; // Check if point is in triangle return (u >= 0) && (v >= 0) && (u + v < 1) && (normal > 0);
half planes
var polygon = [{x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}]; px = Math.random(); py = Math.random(); var v0x = polygon[1].x-polygon[0].x; var v0y = polygon[1].y-polygon[0].y; var v1x = polygon[2].x-polygon[0].x; var v1y = polygon[2].y-polygon[0].y; // if v0 cross v1 is positive, triangle is counter clockwise when viewed from above. var normal = v0x*v1y - v1x*v0y; var ax = polygon[0].x; var bx = polygon[1].x; var cx = polygon[2].x; var ay = polygon[0].y; var by = polygon[1].y; var cy = polygon[2].y; var b1 = (px - bx) * (ay - by) - (ax - bx) * (py - by); var b2 = (px - cx) * (by - cy) - (bx - cx) * (py - cy); var b3 = (px - ax) * (cy - ay) - (cx - ax) * (py - ay); return (b1==b2) && (b2==b3);
half planes with normal
var polygon = [{x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}]; px = Math.random(); py = Math.random(); var v0x = polygon[1].x-polygon[0].x; var v0y = polygon[1].y-polygon[0].y; var v1x = polygon[2].x-polygon[0].x; var v1y = polygon[2].y-polygon[0].y; // if v0 cross v1 is positive, triangle is counter clockwise when viewed from above. var normal = v0x*v1y - v1x*v0y; var ax = polygon[0].x; var bx = polygon[1].x; var cx = polygon[2].x; var ay = polygon[0].y; var by = polygon[1].y; var cy = polygon[2].y; if (((px - ax) * (by - ay) - (bx - ax) * (py - ay)) > 0 == normal > 0) return true; if (((px - bx) * (cy - by) - (cx - bx) * (py - by)) > 0 == normal > 0) { return true; } return ((px - cx) * (ay - cy) - (ax - cx) * (py - cy)) > 0 == normal > 0;
half planes with normal and vars
var polygon = [{x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}, {x:Math.random(), y:Math.random()}]; px = Math.random(); py = Math.random(); var v0x = polygon[1].x-polygon[0].x; var v0y = polygon[1].y-polygon[0].y; var v1x = polygon[2].x-polygon[0].x; var v1y = polygon[2].y-polygon[0].y; // if v0 cross v1 is positive, triangle is counter clockwise when viewed from above. var normal = v0x*v1y - v1x*v0y; var a = polygon[0]; var b = polygon[1]; var c = polygon[2]; var ax = a.x; var bx = b.x; var ay = a.y; var by = b.y; var pxax = px-ax; var byay = by-ay; var bxax = bx-ax; var pyay = py-ay; if ((pxax * byay - bxax * pyay) * normal > 0) return true; var cx = c.x; var cy = c.y; var pxbx = px-bx; var cyby = cy-by; var cxbx = cx-bx; var pyby = py-by; if ((pxbx * cyby - cxbx * pyby) * normal > 0) return true; var pxcx = px-cx; var aycy = ay-cy; var axcx = ax-cx; var pycy = py-cy; return ((pxcx * aycy - axcx * pycy) * normal) > 0;

Run results for: point in triangle

winding

bary

bary2

half planes

half planes with normal

half planes with normal and vars