Advertisement
Guest User

Untitled

a guest
Aug 19th, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.21 KB | None | 0 0
  1. function mergeAngleRanges (ranges) {
  2. const TWO_PI = 2 * Math.PI;
  3. const DELTA = Math.PI / 1000 // maximum tolerance in radians of gap between overlapping edges.
  4.  
  5. function normAngle (angle) {
  6. // returns an equivalent angle in (-pi, pi]
  7. while (angle <= -Math.PI) angle += TWO_PI;
  8. while (angle > Math.PI) angle -= TWO_PI;
  9. return angle;
  10. }
  11.  
  12. function normMin (range) {
  13. // returns an equivalent range such that min is in (-pi, pi] and 0 < (max - min) <= 2pi
  14. range = {min:normAngle(range.min), max:range.max};
  15. while (range.max <= range.min) range.max += TWO_PI;
  16. while ((range.max - range.min) > TWO_PI) range.max -= TWO_PI;
  17. return range;
  18. }
  19.  
  20. function normMax (range) {
  21. // returns an equivalent range such that max is in (-pi, pi] and 0 < (max - min) <= 2pi
  22. range = {min:range.min, max:normAngle(range.max)};
  23. while (range.max <= range.min) range.min -= TWO_PI;
  24. while ((range.max - range.min) > TWO_PI) range.min += TWO_PI;
  25. return range;
  26. }
  27.  
  28. function normRange (range) {
  29. // returns an equivalent range with both angles in (-pi, pi]
  30. return {min:normAngle(range.min), max:normAngle(range.max)};
  31. }
  32.  
  33. function merge (range1, range2) {
  34. // returns the union of two ranges if they overlap, or null if they do not.
  35. return ((range1.max >= (range2.min - DELTA)) && (range1.min <= (range2.max + DELTA)))
  36. ? {min:Math.min(range1.min, range2.min), max:Math.max(range1.max, range2.max)} : null;
  37. }
  38.  
  39. // make a copy of ranges and sort by min
  40. ranges = ranges.slice().sort(function (a, b) { return a.min - b.min; });
  41.  
  42. // for each range with straddles pi, split into two ranges: one adjusted using normMin (left in
  43. // place) and one adjusted using normMax (prepended to the list, preserving sortedness), so that
  44. // ranges straddling pi can merge with other ranges from sides of the boundary.
  45. var prepend = [];
  46. ranges = prepend.concat(ranges.map(function (range) {
  47. if (range.max <= range.min) {
  48. prepend.push(normMax(range));
  49. return normMin(range);
  50. } else return range;
  51. }));
  52.  
  53. // fold each range in from the left, merging with the last value if they overlap
  54. var merged, last;
  55. ranges = ranges.reduce(function (list, next) {
  56. last = list[list.length - 1];
  57. if ((merged = merge(last, next)) !== null) list.splice(-1, 1, merged)
  58. else list.push(next);
  59. return list;
  60. }, ranges.splice(0, 1));
  61.  
  62. var first = ranges[0], last = ranges.slice(-1)[0];
  63.  
  64. // check if the result is a full circle
  65. if ((first === last) && ((first.max - first.min) >= (TWO_PI - DELTA))) return [{min:0, max:0}];
  66.  
  67. if ((merged = merge(normMin(first), normMin(last))) !== null) {
  68. // the first and last ranges overlap; merge them
  69. ranges.shift();
  70. ranges.splice(-1, 1, normRange(merged));
  71. } else {
  72. // the first and last ranges do not overlap; just normalise them
  73. ranges[0] = normRange(first);
  74. ranges.splice(-1, 1, normRange(last));
  75. }
  76.  
  77. return ranges;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement