index.js 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136
  1. import { point } from "@turf/helpers";
  2. /**
  3. * Takes a {@link LineString|linestring}, {@link MultiLineString|multi-linestring},
  4. * {@link MultiPolygon|multi-polygon} or {@link Polygon|polygon} and
  5. * returns {@link Point|points} at all self-intersections.
  6. *
  7. * @name kinks
  8. * @param {Feature<LineString|MultiLineString|MultiPolygon|Polygon>} featureIn input feature
  9. * @returns {FeatureCollection<Point>} self-intersections
  10. * @example
  11. * var poly = turf.polygon([[
  12. * [-12.034835, 8.901183],
  13. * [-12.060413, 8.899826],
  14. * [-12.03638, 8.873199],
  15. * [-12.059383, 8.871418],
  16. * [-12.034835, 8.901183]
  17. * ]]);
  18. *
  19. * var kinks = turf.kinks(poly);
  20. *
  21. * //addToMap
  22. * var addToMap = [poly, kinks]
  23. */
  24. export default function kinks(featureIn) {
  25. var coordinates;
  26. var feature;
  27. var results = {
  28. type: "FeatureCollection",
  29. features: [],
  30. };
  31. if (featureIn.type === "Feature") {
  32. feature = featureIn.geometry;
  33. }
  34. else {
  35. feature = featureIn;
  36. }
  37. if (feature.type === "LineString") {
  38. coordinates = [feature.coordinates];
  39. }
  40. else if (feature.type === "MultiLineString") {
  41. coordinates = feature.coordinates;
  42. }
  43. else if (feature.type === "MultiPolygon") {
  44. coordinates = [].concat.apply([], feature.coordinates);
  45. }
  46. else if (feature.type === "Polygon") {
  47. coordinates = feature.coordinates;
  48. }
  49. else {
  50. throw new Error("Input must be a LineString, MultiLineString, " +
  51. "Polygon, or MultiPolygon Feature or Geometry");
  52. }
  53. coordinates.forEach(function (line1) {
  54. coordinates.forEach(function (line2) {
  55. for (var i = 0; i < line1.length - 1; i++) {
  56. // start iteration at i, intersections for k < i have already
  57. // been checked in previous outer loop iterations
  58. for (var k = i; k < line2.length - 1; k++) {
  59. if (line1 === line2) {
  60. // segments are adjacent and always share a vertex, not a kink
  61. if (Math.abs(i - k) === 1) {
  62. continue;
  63. }
  64. // first and last segment in a closed lineString or ring always share a vertex, not a kink
  65. if (
  66. // segments are first and last segment of lineString
  67. i === 0 &&
  68. k === line1.length - 2 &&
  69. // lineString is closed
  70. line1[i][0] === line1[line1.length - 1][0] &&
  71. line1[i][1] === line1[line1.length - 1][1]) {
  72. continue;
  73. }
  74. }
  75. var intersection = lineIntersects(line1[i][0], line1[i][1], line1[i + 1][0], line1[i + 1][1], line2[k][0], line2[k][1], line2[k + 1][0], line2[k + 1][1]);
  76. if (intersection) {
  77. results.features.push(point([intersection[0], intersection[1]]));
  78. }
  79. }
  80. }
  81. });
  82. });
  83. return results;
  84. }
  85. // modified from http://jsfiddle.net/justin_c_rounds/Gd2S2/light/
  86. function lineIntersects(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
  87. // if the lines intersect, the result contains the x and y of the
  88. // intersection (treating the lines as infinite) and booleans for whether
  89. // line segment 1 or line segment 2 contain the point
  90. var denominator;
  91. var a;
  92. var b;
  93. var numerator1;
  94. var numerator2;
  95. var result = {
  96. x: null,
  97. y: null,
  98. onLine1: false,
  99. onLine2: false,
  100. };
  101. denominator =
  102. (line2EndY - line2StartY) * (line1EndX - line1StartX) -
  103. (line2EndX - line2StartX) * (line1EndY - line1StartY);
  104. if (denominator === 0) {
  105. if (result.x !== null && result.y !== null) {
  106. return result;
  107. }
  108. else {
  109. return false;
  110. }
  111. }
  112. a = line1StartY - line2StartY;
  113. b = line1StartX - line2StartX;
  114. numerator1 = (line2EndX - line2StartX) * a - (line2EndY - line2StartY) * b;
  115. numerator2 = (line1EndX - line1StartX) * a - (line1EndY - line1StartY) * b;
  116. a = numerator1 / denominator;
  117. b = numerator2 / denominator;
  118. // if we cast these lines infinitely in both directions, they intersect here:
  119. result.x = line1StartX + a * (line1EndX - line1StartX);
  120. result.y = line1StartY + a * (line1EndY - line1StartY);
  121. // if line1 is a segment and line2 is infinite, they intersect if:
  122. if (a >= 0 && a <= 1) {
  123. result.onLine1 = true;
  124. }
  125. // if line2 is a segment and line1 is infinite, they intersect if:
  126. if (b >= 0 && b <= 1) {
  127. result.onLine2 = true;
  128. }
  129. // if line1 and line2 are segments, they intersect if both of the above are true
  130. if (result.onLine1 && result.onLine2) {
  131. return [result.x, result.y];
  132. }
  133. else {
  134. return false;
  135. }
  136. }