modeling/src/operations/hulls/hullPoints2.js

  1. const vec2 = require('../../maths/vec2')
  2. /**
  3. * Create a convex hull of the given set of points, where each point is an array of [x,y].
  4. * @see https://en.wikipedia.org/wiki/Graham_scan
  5. *
  6. * @param {Array} uniquePoints - list of UNIQUE points from which to create a hull
  7. * @returns {Array} a list of points that form the hull
  8. * @alias module:modeling/hulls.hullPoints2
  9. */
  10. const hullPoints2 = (uniquePoints) => {
  11. // find min point
  12. let min = vec2.fromValues(Infinity, Infinity)
  13. uniquePoints.forEach((point) => {
  14. if (point[1] < min[1] || (point[1] === min[1] && point[0] < min[0])) {
  15. min = point
  16. }
  17. })
  18. // gather information for sorting by polar coordinates (point, angle, distSq)
  19. const points = []
  20. uniquePoints.forEach((point) => {
  21. // use faster fakeAtan2 instead of Math.atan2
  22. const angle = fakeAtan2(point[1] - min[1], point[0] - min[0])
  23. const distSq = vec2.squaredDistance(point, min)
  24. points.push({ point, angle, distSq })
  25. })
  26. // sort by polar coordinates
  27. points.sort((pt1, pt2) => pt1.angle !== pt2.angle
  28. ? pt1.angle - pt2.angle
  29. : pt1.distSq - pt2.distSq)
  30. const stack = [] // start with empty stack
  31. points.forEach((point) => {
  32. let cnt = stack.length
  33. while (cnt > 1 && ccw(stack[cnt - 2], stack[cnt - 1], point.point) <= Number.EPSILON) {
  34. stack.pop() // get rid of colinear and interior (clockwise) points
  35. cnt = stack.length
  36. }
  37. stack.push(point.point)
  38. })
  39. return stack
  40. }
  41. // returns: < 0 clockwise, 0 colinear, > 0 counter-clockwise
  42. const ccw = (v1, v2, v3) => (v2[0] - v1[0]) * (v3[1] - v1[1]) - (v2[1] - v1[1]) * (v3[0] - v1[0])
  43. // Returned "angle" is really 1/tan (inverse of slope) made negative to increase with angle.
  44. // This function is strictly for sorting in this algorithm.
  45. const fakeAtan2 = (y, x) => {
  46. // The "if" is a special case for when the minimum vector found in loop above is present.
  47. // We need to ensure that it sorts as the minimum point. Otherwise, this becomes NaN.
  48. if (y === 0 && x === 0) {
  49. return -Infinity
  50. } else {
  51. return -x / y
  52. }
  53. }
  54. module.exports = hullPoints2