sweepline-intersections.js 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290
  1. "use strict";
  2. Object.defineProperty(exports, "__esModule", { value: true });
  3. // Inlined from
  4. // https://github.com/rowanwins/sweepline-intersections
  5. // Needed to go through babel to transform ES6 classes
  6. var commonjsGlobal = typeof globalThis !== "undefined"
  7. ? globalThis
  8. : typeof window !== "undefined"
  9. ? window
  10. : typeof global !== "undefined"
  11. ? global
  12. : typeof self !== "undefined"
  13. ? self
  14. : {};
  15. function createCommonjsModule(fn, module) {
  16. return (module = { exports: {} }), fn(module, module.exports), module.exports;
  17. }
  18. var tinyqueue = createCommonjsModule(function (module) {
  19. (function (global, factory) {
  20. module.exports = factory();
  21. })(commonjsGlobal, function () {
  22. var TinyQueue = function TinyQueue(data, compare) {
  23. if (data === void 0)
  24. data = [];
  25. if (compare === void 0)
  26. compare = defaultCompare;
  27. this.data = data;
  28. this.length = this.data.length;
  29. this.compare = compare;
  30. if (this.length > 0) {
  31. for (var i = (this.length >> 1) - 1; i >= 0; i--) {
  32. this._down(i);
  33. }
  34. }
  35. };
  36. TinyQueue.prototype.push = function push(item) {
  37. this.data.push(item);
  38. this.length++;
  39. this._up(this.length - 1);
  40. };
  41. TinyQueue.prototype.pop = function pop() {
  42. if (this.length === 0) {
  43. return undefined;
  44. }
  45. var top = this.data[0];
  46. var bottom = this.data.pop();
  47. this.length--;
  48. if (this.length > 0) {
  49. this.data[0] = bottom;
  50. this._down(0);
  51. }
  52. return top;
  53. };
  54. TinyQueue.prototype.peek = function peek() {
  55. return this.data[0];
  56. };
  57. TinyQueue.prototype._up = function _up(pos) {
  58. var ref = this;
  59. var data = ref.data;
  60. var compare = ref.compare;
  61. var item = data[pos];
  62. while (pos > 0) {
  63. var parent = (pos - 1) >> 1;
  64. var current = data[parent];
  65. if (compare(item, current) >= 0) {
  66. break;
  67. }
  68. data[pos] = current;
  69. pos = parent;
  70. }
  71. data[pos] = item;
  72. };
  73. TinyQueue.prototype._down = function _down(pos) {
  74. var ref = this;
  75. var data = ref.data;
  76. var compare = ref.compare;
  77. var halfLength = this.length >> 1;
  78. var item = data[pos];
  79. while (pos < halfLength) {
  80. var left = (pos << 1) + 1;
  81. var best = data[left];
  82. var right = left + 1;
  83. if (right < this.length && compare(data[right], best) < 0) {
  84. left = right;
  85. best = data[right];
  86. }
  87. if (compare(best, item) >= 0) {
  88. break;
  89. }
  90. data[pos] = best;
  91. pos = left;
  92. }
  93. data[pos] = item;
  94. };
  95. function defaultCompare(a, b) {
  96. return a < b ? -1 : a > b ? 1 : 0;
  97. }
  98. return TinyQueue;
  99. });
  100. });
  101. function checkWhichEventIsLeft(e1, e2) {
  102. if (e1.p.x > e2.p.x)
  103. return 1;
  104. if (e1.p.x < e2.p.x)
  105. return -1;
  106. if (e1.p.y !== e2.p.y)
  107. return e1.p.y > e2.p.y ? 1 : -1;
  108. return 1;
  109. }
  110. function checkWhichSegmentHasRightEndpointFirst(seg1, seg2) {
  111. if (seg1.rightSweepEvent.p.x > seg2.rightSweepEvent.p.x)
  112. return 1;
  113. if (seg1.rightSweepEvent.p.x < seg2.rightSweepEvent.p.x)
  114. return -1;
  115. if (seg1.rightSweepEvent.p.y !== seg2.rightSweepEvent.p.y)
  116. return seg1.rightSweepEvent.p.y < seg2.rightSweepEvent.p.y ? 1 : -1;
  117. return 1;
  118. }
  119. function _classCallCheck(instance, Constructor) {
  120. if (!(instance instanceof Constructor)) {
  121. throw new TypeError("Cannot call a class as a function");
  122. }
  123. }
  124. function _defineProperties(target, props) {
  125. for (var i = 0; i < props.length; i++) {
  126. var descriptor = props[i];
  127. descriptor.enumerable = descriptor.enumerable || false;
  128. descriptor.configurable = true;
  129. if ("value" in descriptor)
  130. descriptor.writable = true;
  131. Object.defineProperty(target, descriptor.key, descriptor);
  132. }
  133. }
  134. function _createClass(Constructor, protoProps, staticProps) {
  135. if (protoProps)
  136. _defineProperties(Constructor.prototype, protoProps);
  137. if (staticProps)
  138. _defineProperties(Constructor, staticProps);
  139. return Constructor;
  140. }
  141. var Event = /*#__PURE__*/ (function () {
  142. function Event(p, featureId, ringId, eventId) {
  143. _classCallCheck(this, Event);
  144. this.p = {
  145. x: p[0],
  146. y: p[1],
  147. };
  148. this.featureId = featureId;
  149. this.ringId = ringId;
  150. this.eventId = eventId;
  151. this.otherEvent = null;
  152. this.isLeftEndpoint = null;
  153. }
  154. _createClass(Event, [
  155. {
  156. key: "isSamePoint",
  157. value: function isSamePoint(eventToCheck) {
  158. return this.p.x === eventToCheck.p.x && this.p.y === eventToCheck.p.y;
  159. },
  160. },
  161. ]);
  162. return Event;
  163. })();
  164. function fillEventQueue(geojson, eventQueue) {
  165. if (geojson.type === "FeatureCollection") {
  166. var features = geojson.features;
  167. for (var i = 0; i < features.length; i++) {
  168. processFeature(features[i], eventQueue);
  169. }
  170. }
  171. else {
  172. processFeature(geojson, eventQueue);
  173. }
  174. }
  175. var featureId = 0;
  176. var ringId = 0;
  177. var eventId = 0;
  178. function processFeature(featureOrGeometry, eventQueue) {
  179. var geom = featureOrGeometry.type === "Feature"
  180. ? featureOrGeometry.geometry
  181. : featureOrGeometry;
  182. var coords = geom.coordinates; // standardise the input
  183. if (geom.type === "Polygon" || geom.type === "MultiLineString")
  184. coords = [coords];
  185. if (geom.type === "LineString")
  186. coords = [[coords]];
  187. for (var i = 0; i < coords.length; i++) {
  188. for (var ii = 0; ii < coords[i].length; ii++) {
  189. var currentP = coords[i][ii][0];
  190. var nextP = null;
  191. ringId = ringId + 1;
  192. for (var iii = 0; iii < coords[i][ii].length - 1; iii++) {
  193. nextP = coords[i][ii][iii + 1];
  194. var e1 = new Event(currentP, featureId, ringId, eventId);
  195. var e2 = new Event(nextP, featureId, ringId, eventId + 1);
  196. e1.otherEvent = e2;
  197. e2.otherEvent = e1;
  198. if (checkWhichEventIsLeft(e1, e2) > 0) {
  199. e2.isLeftEndpoint = true;
  200. e1.isLeftEndpoint = false;
  201. }
  202. else {
  203. e1.isLeftEndpoint = true;
  204. e2.isLeftEndpoint = false;
  205. }
  206. eventQueue.push(e1);
  207. eventQueue.push(e2);
  208. currentP = nextP;
  209. eventId = eventId + 1;
  210. }
  211. }
  212. }
  213. featureId = featureId + 1;
  214. }
  215. var Segment = function Segment(event) {
  216. _classCallCheck(this, Segment);
  217. this.leftSweepEvent = event;
  218. this.rightSweepEvent = event.otherEvent;
  219. };
  220. function testSegmentIntersect(seg1, seg2) {
  221. if (seg1 === null || seg2 === null)
  222. return false;
  223. if (seg1.leftSweepEvent.ringId === seg2.leftSweepEvent.ringId &&
  224. (seg1.rightSweepEvent.isSamePoint(seg2.leftSweepEvent) ||
  225. seg1.rightSweepEvent.isSamePoint(seg2.leftSweepEvent) ||
  226. seg1.rightSweepEvent.isSamePoint(seg2.rightSweepEvent) ||
  227. seg1.leftSweepEvent.isSamePoint(seg2.leftSweepEvent) ||
  228. seg1.leftSweepEvent.isSamePoint(seg2.rightSweepEvent)))
  229. return false;
  230. var x1 = seg1.leftSweepEvent.p.x;
  231. var y1 = seg1.leftSweepEvent.p.y;
  232. var x2 = seg1.rightSweepEvent.p.x;
  233. var y2 = seg1.rightSweepEvent.p.y;
  234. var x3 = seg2.leftSweepEvent.p.x;
  235. var y3 = seg2.leftSweepEvent.p.y;
  236. var x4 = seg2.rightSweepEvent.p.x;
  237. var y4 = seg2.rightSweepEvent.p.y;
  238. var denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
  239. var numeA = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
  240. var numeB = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3);
  241. if (denom === 0) {
  242. if (numeA === 0 && numeB === 0)
  243. return false;
  244. return false;
  245. }
  246. var uA = numeA / denom;
  247. var uB = numeB / denom;
  248. if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
  249. var x = x1 + uA * (x2 - x1);
  250. var y = y1 + uA * (y2 - y1);
  251. return [x, y];
  252. }
  253. return false;
  254. }
  255. function runCheck(eventQueue, ignoreSelfIntersections) {
  256. ignoreSelfIntersections = ignoreSelfIntersections
  257. ? ignoreSelfIntersections
  258. : false;
  259. var intersectionPoints = [];
  260. var outQueue = new tinyqueue([], checkWhichSegmentHasRightEndpointFirst);
  261. while (eventQueue.length) {
  262. var event = eventQueue.pop();
  263. if (event.isLeftEndpoint) {
  264. // debugEventAndSegments(event.p, outQueue.data)
  265. var segment = new Segment(event);
  266. for (var i = 0; i < outQueue.data.length; i++) {
  267. var otherSeg = outQueue.data[i];
  268. if (ignoreSelfIntersections) {
  269. if (otherSeg.leftSweepEvent.featureId === event.featureId)
  270. continue;
  271. }
  272. var intersection = testSegmentIntersect(segment, otherSeg);
  273. if (intersection !== false)
  274. intersectionPoints.push(intersection);
  275. }
  276. outQueue.push(segment);
  277. }
  278. else if (event.isLeftEndpoint === false) {
  279. outQueue.pop(); // const seg = outQueue.pop()
  280. // debugRemovingSegment(event.p, seg)
  281. }
  282. }
  283. return intersectionPoints;
  284. }
  285. function sweeplineIntersections(geojson, ignoreSelfIntersections) {
  286. var eventQueue = new tinyqueue([], checkWhichEventIsLeft);
  287. fillEventQueue(geojson, eventQueue);
  288. return runCheck(eventQueue, ignoreSelfIntersections);
  289. }
  290. exports.default = sweeplineIntersections;