modeling/src/geometries/poly2/arePointsInside.js

  1. const measureArea = require('./measureArea')
  2. const flip = require('./flip')
  3. /**
  4. * Determine if the given points are inside the given polygon.
  5. *
  6. * @param {Array} points - a list of points, where each point is an array with X and Y values
  7. * @param {poly2} polygon - a 2D polygon
  8. * @return {Integer} 1 if all points are inside, 0 if some or none are inside
  9. * @alias module:modeling/geometries/poly2.arePointsInside
  10. */
  11. const arePointsInside = (points, polygon) => {
  12. if (points.length === 0) return 0 // nothing to check
  13. const vertices = polygon.vertices
  14. if (vertices.length < 3) return 0 // nothing can be inside an empty polygon
  15. if (measureArea(polygon) < 0) {
  16. polygon = flip(polygon) // CCW is required
  17. }
  18. const sum = points.reduce((acc, point) => acc + isPointInside(point, vertices), 0)
  19. return sum === points.length ? 1 : 0
  20. }
  21. /*
  22. * Determine if the given point is inside the polygon.
  23. *
  24. * @see http://erich.realtimerendering.com/ptinpoly/ (Crossings Test)
  25. * @param {Array} point - an array with X and Y values
  26. * @param {Array} polygon - a list of points, where each point is an array with X and Y values
  27. * @return {Integer} 1 if the point is inside, 0 if outside
  28. */
  29. const isPointInside = (point, polygon) => {
  30. const numverts = polygon.length
  31. const tx = point[0]
  32. const ty = point[1]
  33. let vtx0 = polygon[numverts - 1]
  34. let vtx1 = polygon[0]
  35. let yflag0 = (vtx0[1] > ty)
  36. let insideFlag = 0
  37. let i = 0
  38. for (let j = (numverts + 1); --j;) {
  39. /*
  40. * check if Y endpoints straddle (are on opposite sides) of point's Y
  41. * if so, +X ray could intersect this edge.
  42. */
  43. const yflag1 = (vtx1[1] > ty)
  44. if (yflag0 !== yflag1) {
  45. /*
  46. * check if X endpoints are on same side of the point's X
  47. * if so, it's easy to test if edge hits or misses.
  48. */
  49. const xflag0 = (vtx0[0] > tx)
  50. const xflag1 = (vtx1[0] > tx)
  51. if (xflag0 && xflag1) {
  52. /* if edge's X values are both right of the point, then the point must be inside */
  53. insideFlag = !insideFlag
  54. } else {
  55. /*
  56. * if X endpoints straddle the point, then
  57. * the compute intersection of polygon edge with +X ray
  58. * if intersection >= point's X then the +X ray hits it.
  59. */
  60. if ((vtx1[0] - (vtx1[1] - ty) * (vtx0[0] - vtx1[0]) / (vtx0[1] - vtx1[1])) >= tx) {
  61. insideFlag = !insideFlag
  62. }
  63. }
  64. }
  65. /* move to next pair of vertices, retaining info as possible */
  66. yflag0 = yflag1
  67. vtx0 = vtx1
  68. vtx1 = polygon[++i]
  69. }
  70. return insideFlag
  71. }
  72. module.exports = arePointsInside