index.js (2685B)
1 // From https://www.geeksforgeeks.org/dsa/check-if-two-given-line-segments-intersect/ 2 3 /* eslint-disable camelcase */ 4 5 // function to find orientation of ordered triplet (p, q, r) 6 // 0 --> p, q and r are collinear 7 // 1 --> Clockwise 8 // 2 --> Counterclockwise 9 function orientation(p, q, r) { 10 const val = (q.lng - p.lng) * (r.lat - q.lat) - (q.lat - p.lat) * (r.lng - q.lng); 11 // collinear 12 if (val === 0) { 13 return 0; 14 } 15 // clock or counterclock wise 16 // 1 for clockwise, 2 for counterclockwise 17 return val > 0 ? 1 : 2; 18 } 19 20 // function to check if point q lies on line segment 'pr' 21 function onSegment(p, q, r) { 22 return ( 23 q.lat <= Math.max(p.lat, r.lat) && 24 q.lat >= Math.min(p.lat, r.lat) && 25 q.lng <= Math.max(p.lng, r.lng) && 26 q.lng >= Math.min(p.lng, r.lng) 27 ); 28 } 29 30 // function to check if two line segments intersect 31 function segmentsIntersect(seg1_1, seg1_2, seg2_1, seg2_2) { 32 // find the four orientations needed 33 // for general and special cases 34 const o1 = orientation(seg1_1, seg1_2, seg2_1); 35 const o2 = orientation(seg1_1, seg1_2, seg2_2); 36 const o3 = orientation(seg2_1, seg2_2, seg1_1); 37 const o4 = orientation(seg2_1, seg2_2, seg1_2); 38 // general case 39 if (o1 !== o2 && o3 !== o4) { 40 return true; 41 } 42 // special cases 43 // seg1_1, seg1_2 and seg2_1 are collinear and seg2_1 lies on segment seg1 44 if (o1 === 0 && onSegment(seg1_1, seg2_1, seg1_2)) { 45 return true; 46 } 47 // seg1_1, seg1_2 and seg2_2 are collinear and seg2_2 lies on segment seg1 48 if (o2 === 0 && onSegment(seg1_1, seg2_2, seg1_2)) { 49 return true; 50 } 51 // seg2_1, seg2_2 and seg1_1 are collinear and seg1_1 lies on segment seg2 52 if (o3 === 0 && onSegment(seg2_1, seg1_1, seg2_2)) { 53 return true; 54 } 55 // seg2_1, seg2_2 and seg1_2 are collinear and seg1_2 lies on segment seg2 56 if (o4 === 0 && onSegment(seg2_1, seg1_2, seg2_2)) { 57 return true; 58 } 59 return false; 60 } 61 62 function polylineHasSelfIntersections(latlngs) { 63 if (latlngs.length < 4) { 64 return false; 65 } 66 for (let i = 0; i <= latlngs.length - 3; i++) { 67 const seg1_1 = latlngs[i]; 68 const seg1_2 = latlngs[i + 1]; 69 70 for (let j = i + 2; j <= latlngs.length - 1; j++) { 71 if (i === 0 && j === latlngs.length - 1) { 72 continue; 73 } 74 const seg2_1 = latlngs[j]; 75 const seg2_2 = latlngs[(j + 1) % latlngs.length]; 76 77 if (segmentsIntersect(seg1_1, seg1_2, seg2_1, seg2_2)) { 78 return true; 79 } 80 } 81 } 82 return false; 83 } 84 85 export {polylineHasSelfIntersections};