type Point = { $type: "PlainPoint"; x: number; y: number; }; const removeRedundantPoints = (points: Point[]) => { const redundantIndexes: number[] = []; for (let i = 0; i < points.length - 2; i++) { const [idxLeft, idxMiddle, idxRight] = [i, i + 1, i + 2]; if (isBetween(points[idxLeft], points[idxMiddle], points[idxRight])) { redundantIndexes.push(idxMiddle); } } console.log( `${redundantIndexes.length} of ${points.length} redundant (${points.length - redundantIndexes.length} significant)`, ); const significantPoints = points.filter( (_, i) => !redundantIndexes.includes(i), ); return significantPoints; }; const isBetween = (left: Point, middle: Point, right: Point) => { // Smaller number => stricter constraint of what is considered "between" const threshold = 0.000006; const directDistance = distance(left, right); const jointDistance = distance(left, middle) + distance(middle, right); return jointDistance - directDistance < threshold; }; const distance = (a: Point, b: Point) => Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2)); // Example: const testPoints = [ { $type: "PlainPoint", x: 2.3518900238, y: 48.856656958, }, { $type: "PlainPoint", x: 2.3519332771, y: 48.856685416, }, { $type: "PlainPoint", x: 2.3516305042, y: 48.856742332, }, { $type: "PlainPoint", x: 2.351587251, y: 48.856713874, }, { $type: "PlainPoint", x: 2.3515439977, y: 48.856600041, }, { $type: "PlainPoint", x: 2.3512412249, y: 48.856628499, }, { $type: "PlainPoint", x: 2.3511979717, y: 48.856656958, }, { $type: "PlainPoint", x: 2.3511547184, y: 48.856656958, }, { $type: "PlainPoint", x: 2.3511114651, y: 48.856685416, }, { $type: "PlainPoint", x: 2.3510682119, y: 48.856685416, }, { $type: "PlainPoint", x: 2.3510682119, y: 48.856685416, }, { $type: "PlainPoint", x: 2.3508951988, y: 48.856742332, }, { $type: "PlainPoint", x: 2.3497273608, y: 48.856998456, }, { $type: "PlainPoint", x: 2.3496408543, y: 48.85677079, }, { $type: "PlainPoint", x: 2.3495110945, y: 48.856514666, }, { $type: "PlainPoint", x: 2.3507654391, y: 48.856030872, }, { $type: "PlainPoint", x: 2.3510682119, y: 48.856742332, }, { $type: "PlainPoint", x: 2.3511114651, y: 48.856827707, }, { $type: "PlainPoint", x: 2.3510682119, y: 48.856827707, }, { $type: "PlainPoint", x: 2.3496841076, y: 48.85722612, }, { $type: "PlainPoint", x: 2.349251575, y: 48.857311493, }, { $type: "PlainPoint", x: 2.3489488022, y: 48.856713874, }, { $type: "PlainPoint", x: 2.3488622957, y: 48.856628499, }, { $type: "PlainPoint", x: 2.3487325359, y: 48.856429291, }, { $type: "PlainPoint", x: 2.3486460294, y: 48.856230082, }, { $type: "PlainPoint", x: 2.3485595228, y: 48.85605933, }, { $type: "PlainPoint", x: 2.3483432565, y: 48.855717826, }, { $type: "PlainPoint", x: 2.3483432565, y: 48.855689367, }, { $type: "PlainPoint", x: 2.3483000033, y: 48.855660908, }, { $type: "PlainPoint", x: 2.348083737, y: 48.855262483, }, { $type: "PlainPoint", x: 2.3478242174, y: 48.854778676, }, { $type: "PlainPoint", x: 2.3473916848, y: 48.854067188, }, { $type: "PlainPoint", x: 2.3472619251, y: 48.853896429, }, { $type: "PlainPoint", x: 2.3471321653, y: 48.85358337, }, { $type: "PlainPoint", x: 2.3470456588, y: 48.85344107, }, { $type: "PlainPoint", x: 2.3470024055, y: 48.85341261, }, { $type: "PlainPoint", x: 2.3469591522, y: 48.853298769, }, { $type: "PlainPoint", x: 2.3468293925, y: 48.853128008, }, { $type: "PlainPoint", x: 2.3468293925, y: 48.853071087, }, { $type: "PlainPoint", x: 2.3466563794, y: 48.852786483, }, { $type: "PlainPoint", x: 2.3463103533, y: 48.852160349, }, { $type: "PlainPoint", x: 2.3458778208, y: 48.851420362, }, { $type: "PlainPoint", x: 2.3455317947, y: 48.850794211, }, { $type: "PlainPoint", x: 2.3452290219, y: 48.850253437, }, { $type: "PlainPoint", x: 2.3452290219, y: 48.850196513, }, { $type: "PlainPoint", x: 2.3448829958, y: 48.849570347, }, { $type: "PlainPoint", x: 2.3447099828, y: 48.849342648, }, { $type: "PlainPoint", x: 2.3444072099, y: 48.848688008, }, { $type: "PlainPoint", x: 2.3443207034, y: 48.848545693, }, { $type: "PlainPoint", x: 2.3436286513, y: 48.847350238, }, { $type: "PlainPoint", x: 2.3433691317, y: 48.846780964, }, { $type: "PlainPoint", x: 2.3431528654, y: 48.846439396, }, { $type: "PlainPoint", x: 2.3429798524, y: 48.84612629, }, { $type: "PlainPoint", x: 2.3426338263, y: 48.845557002, }, { $type: "PlainPoint", x: 2.3424608133, y: 48.845158496, }, { $type: "PlainPoint", x: 2.3423310535, y: 48.844930777, }, { $type: "PlainPoint", x: 2.3420282807, y: 48.84433301, }, { $type: "PlainPoint", x: 2.3415524948, y: 48.843365181, }, { $type: "PlainPoint", x: 2.3413794818, y: 48.84302359, }, { $type: "PlainPoint", x: 2.3413794818, y: 48.842938192, }, { $type: "PlainPoint", x: 2.3413362285, y: 48.842738929, }, { $type: "PlainPoint", x: 2.3412929753, y: 48.842112669, }, { $type: "PlainPoint", x: 2.341249722, y: 48.841714136, }, { $type: "PlainPoint", x: 2.3412064687, y: 48.841429467, }, { $type: "PlainPoint", x: 2.3412064687, y: 48.841344067, }, { $type: "PlainPoint", x: 2.3412064687, y: 48.841287133, }, { $type: "PlainPoint", x: 2.3411632155, y: 48.841201731, }, { $type: "PlainPoint", x: 2.3411632155, y: 48.841173264, }, { $type: "PlainPoint", x: 2.3409902024, y: 48.840860126, }, { $type: "PlainPoint", x: 2.3408171894, y: 48.84060392, }, { $type: "PlainPoint", x: 2.3407306829, y: 48.840433115, }, { $type: "PlainPoint", x: 2.340081884, y: 48.839465211, }, { $type: "PlainPoint", x: 2.3399521242, y: 48.839294402, }, { $type: "PlainPoint", x: 2.3396926047, y: 48.838895847, }, { $type: "PlainPoint", x: 2.3396493514, y: 48.838781973, }, { $type: "PlainPoint", x: 2.3396060982, y: 48.838696568, }, { $type: "PlainPoint", x: 2.3395195916, y: 48.838582694, }, { $type: "PlainPoint", x: 2.3392600721, y: 48.838212601, }, { $type: "PlainPoint", x: 2.3382652471, y: 48.836703735, }, { $type: "PlainPoint", x: 2.3380489808, y: 48.836333628, }, { $type: "PlainPoint", x: 2.3378327145, y: 48.835991989, }, { $type: "PlainPoint", x: 2.337746208, y: 48.835878109, }, { $type: "PlainPoint", x: 2.3377029547, y: 48.835792699, }, { $type: "PlainPoint", x: 2.3372704221, y: 48.835109411, }, { $type: "PlainPoint", x: 2.3369243961, y: 48.83462541, }, { $type: "PlainPoint", x: 2.3365351167, y: 48.834596939, }, { $type: "PlainPoint", x: 2.3361890907, y: 48.834596939, }, { $type: "PlainPoint", x: 2.3359295711, y: 48.834568468, }, { $type: "PlainPoint", x: 2.3356267983, y: 48.834568468, }, { $type: "PlainPoint", x: 2.3350212527, y: 48.834539997, }, { $type: "PlainPoint", x: 2.3348049864, y: 48.834511527, }, { $type: "PlainPoint", x: 2.3345454668, y: 48.834511527, }, { $type: "PlainPoint", x: 2.3341561875, y: 48.834511527, }, { $type: "PlainPoint", x: 2.3333343755, y: 48.834454585, }, { $type: "PlainPoint", x: 2.3330316027, y: 48.834426114, }, { $type: "PlainPoint", x: 2.3326855767, y: 48.834426114, }, { $type: "PlainPoint", x: 2.3323828038, y: 48.834397643, }, { $type: "PlainPoint", x: 2.3322530441, y: 48.834283759, }, { $type: "PlainPoint", x: 2.3320367778, y: 48.833999049, }, { $type: "PlainPoint", x: 2.3318205115, y: 48.833742808, }, { $type: "PlainPoint", x: 2.3316474984, y: 48.833486565, }, { $type: "PlainPoint", x: 2.3315177387, y: 48.833344208, }, { $type: "PlainPoint", x: 2.3314744854, y: 48.833287265, }, { $type: "PlainPoint", x: 2.3313447256, y: 48.833116435, }, { $type: "PlainPoint", x: 2.3310419528, y: 48.832803246, }, { $type: "PlainPoint", x: 2.3308689398, y: 48.832603943, }, { $type: "PlainPoint", x: 2.3307824332, y: 48.832461583, }, { $type: "PlainPoint", x: 2.3306094202, y: 48.832262278, }, { $type: "PlainPoint", x: 2.3305661669, y: 48.832176862, }, { $type: "PlainPoint", x: 2.3304796604, y: 48.832062973, }, { $type: "PlainPoint", x: 2.3302633941, y: 48.831806722, }, { $type: "PlainPoint", x: 2.3299606213, y: 48.83143658, }, { $type: "PlainPoint", x: 2.3299606213, y: 48.831379634, }, { $type: "PlainPoint", x: 2.3298308615, y: 48.831208798, }, { $type: "PlainPoint", x: 2.3294415822, y: 48.830781705, }, { $type: "PlainPoint", x: 2.3290955561, y: 48.830383082, }, { $type: "PlainPoint", x: 2.3288360366, y: 48.830069876, }, { $type: "PlainPoint", x: 2.3284467572, y: 48.829557352, }, { $type: "PlainPoint", x: 2.3280574779, y: 48.829158719, }, { $type: "PlainPoint", x: 2.3277979583, y: 48.82887398, }, { $type: "PlainPoint", x: 2.3277114518, y: 48.828788557, }, { $type: "PlainPoint", x: 2.3275384388, y: 48.828560764, }, { $type: "PlainPoint", x: 2.3274519323, y: 48.828475341, }, { $type: "PlainPoint", x: 2.3273654258, y: 48.828418392, }, { $type: "PlainPoint", x: 2.3268896399, y: 48.82801975, }, { $type: "PlainPoint", x: 2.3268463866, y: 48.82801975, }, { $type: "PlainPoint", x: 2.3267166269, y: 48.82801975, }, { $type: "PlainPoint", x: 2.3266301203, y: 48.827905852, }, { $type: "PlainPoint", x: 2.3266733736, y: 48.827820428, }, { $type: "PlainPoint", x: 2.3267598801, y: 48.827791953, }, { $type: "PlainPoint", x: 2.3266301203, y: 48.827564156, }, { $type: "PlainPoint", x: 2.3265003606, y: 48.827222457, }, { $type: "PlainPoint", x: 2.3264138541, y: 48.826909231, }, { $type: "PlainPoint", x: 2.3263706008, y: 48.826652953, }, { $type: "PlainPoint", x: 2.3263706008, y: 48.826482101, }, { $type: "PlainPoint", x: 2.3261110812, y: 48.825542404, }, { $type: "PlainPoint", x: 2.3259813215, y: 48.82505831, }, { $type: "PlainPoint", x: 2.3258515617, y: 48.824659641, }, { $type: "PlainPoint", x: 2.3258515617, y: 48.824602688, }, { $type: "PlainPoint", x: 2.3258083084, y: 48.824545735, }, { $type: "PlainPoint", x: 2.3258083084, y: 48.824431829, }, { $type: "PlainPoint", x: 2.3256785486, y: 48.823947725, }, { $type: "PlainPoint", x: 2.3256785486, y: 48.823833817, }, { $type: "PlainPoint", x: 2.3254190291, y: 48.823264275, }, { $type: "PlainPoint", x: 2.3253757758, y: 48.823121889, }, { $type: "PlainPoint", x: 2.3253325226, y: 48.822922547, }, { $type: "PlainPoint", x: 2.3252892693, y: 48.822751682, }, { $type: "PlainPoint", x: 2.3251162563, y: 48.822125172, }, { $type: "PlainPoint", x: 2.325073003, y: 48.821954305, }, { $type: "PlainPoint", x: 2.3250297498, y: 48.821811915, }, { $type: "PlainPoint", x: 2.3249432432, y: 48.821698002, }, { $type: "PlainPoint", x: 2.32489999, y: 48.821584089, }, { $type: "PlainPoint", x: 2.3248134835, y: 48.821498655, }, { $type: "PlainPoint", x: 2.3247702302, y: 48.821384742, }, { $type: "PlainPoint", x: 2.3247269769, y: 48.821327785, }, { $type: "PlainPoint", x: 2.3244674574, y: 48.820957565, }, { $type: "PlainPoint", x: 2.3244242041, y: 48.820929086, }, { $type: "PlainPoint", x: 2.3241646846, y: 48.820558864, }, { $type: "PlainPoint", x: 2.3241214313, y: 48.820473427, }, { $type: "PlainPoint", x: 2.324078178, y: 48.820359512, }, { $type: "PlainPoint", x: 2.3240349248, y: 48.820274075, }, { $type: "PlainPoint", x: 2.3239916715, y: 48.820160159, }, { $type: "PlainPoint", x: 2.3242079378, y: 48.820103201, }, { $type: "PlainPoint", x: 2.3255055356, y: 48.819846889, }, { $type: "PlainPoint", x: 2.3255920421, y: 48.81981841, }, { $type: "PlainPoint", x: 2.3257650552, y: 48.81981841, }, { $type: "PlainPoint", x: 2.3258948149, y: 48.819789931, }, { $type: "PlainPoint", x: 2.3261110812, y: 48.819732972, }, { $type: "PlainPoint", x: 2.3263273475, y: 48.819676013, }, { $type: "PlainPoint", x: 2.3268463866, y: 48.819619055, }, { $type: "PlainPoint", x: 2.3290955561, y: 48.819163384, }, { $type: "PlainPoint", x: 2.3297876083, y: 48.819020986, }, { $type: "PlainPoint", x: 2.3327288299, y: 48.818308989, }, { $type: "PlainPoint", x: 2.3338966679, y: 48.817625463, }, { $type: "PlainPoint", x: 2.334069681, y: 48.817540021, }, { $type: "PlainPoint", x: 2.3343292005, y: 48.817312177, }, { $type: "PlainPoint", x: 2.3350645059, y: 48.816941927, }, { $type: "PlainPoint", x: 2.3363188504, y: 48.816657118, }, { $type: "PlainPoint", x: 2.336405357, y: 48.816600156, }, { $type: "PlainPoint", x: 2.3366648765, y: 48.816258382, }, { $type: "PlainPoint", x: 2.3366648765, y: 48.815945088, }, { $type: "PlainPoint", x: 2.3364918635, y: 48.815489383, }, { $type: "PlainPoint", x: 2.3360160776, y: 48.814093762, }, { $type: "PlainPoint", x: 2.3359728244, y: 48.814008315, }, { $type: "PlainPoint", x: 2.3359728244, y: 48.813552593, }, { $type: "PlainPoint", x: 2.3360160776, y: 48.813381696, }, { $type: "PlainPoint", x: 2.3363188504, y: 48.812527202, }, { $type: "PlainPoint", x: 2.3370541558, y: 48.811672695, }, { $type: "PlainPoint", x: 2.3371839156, y: 48.811530275, }, { $type: "PlainPoint", x: 2.3373569287, y: 48.811330887, }, { $type: "PlainPoint", x: 2.3374001819, y: 48.811273919, }, { $type: "PlainPoint", x: 2.3374866884, y: 48.811159983, }, { $type: "PlainPoint", x: 2.3380922341, y: 48.810504844, }, { $type: "PlainPoint", x: 2.3383950069, y: 48.810163029, }, { $type: "PlainPoint", x: 2.3392600721, y: 48.80925151, }, { $type: "PlainPoint", x: 2.3397791112, y: 48.808653317, }, { $type: "PlainPoint", x: 2.340081884, y: 48.808311489, }, { $type: "PlainPoint", x: 2.3402981503, y: 48.808083603, }, { $type: "PlainPoint", x: 2.3408604427, y: 48.807342965, }, { $type: "PlainPoint", x: 2.3409036959, y: 48.807285992, }, { $type: "PlainPoint", x: 2.3410334557, y: 48.80714356, }, { $type: "PlainPoint", x: 2.3411632155, y: 48.806858695, }, { $type: "PlainPoint", x: 2.3414659883, y: 48.806288961, }, { $type: "PlainPoint", x: 2.3415092416, y: 48.806175013, }, { $type: "PlainPoint", x: 2.3417687611, y: 48.805120984, }, { $type: "PlainPoint", x: 2.3418120144, y: 48.802243659, }, { $type: "PlainPoint", x: 2.3418120144, y: 48.801018608, }, { $type: "PlainPoint", x: 2.3418552676, y: 48.800790689, }, { $type: "PlainPoint", x: 2.3418552676, y: 48.800733709, }, { $type: "PlainPoint", x: 2.3418985209, y: 48.800448807, }, { $type: "PlainPoint", x: 2.3419417742, y: 48.800363337, }, { $type: "PlainPoint", x: 2.3421147872, y: 48.799907491, }, { $type: "PlainPoint", x: 2.3422012937, y: 48.799679566, }, { $type: "PlainPoint", x: 2.342244547, y: 48.799622585, }, { $type: "PlainPoint", x: 2.3428068393, y: 48.798767857, }, { $type: "PlainPoint", x: 2.3431961187, y: 48.798283505, }, { $type: "PlainPoint", x: 2.343412385, y: 48.798027081, }, { $type: "PlainPoint", x: 2.3437151578, y: 48.797685181, }, { $type: "PlainPoint", x: 2.3438016643, y: 48.797542722, }, { $type: "PlainPoint", x: 2.3443639567, y: 48.796687959, }, { $type: "PlainPoint", x: 2.3447964893, y: 48.795633731, }, { $type: "PlainPoint", x: 2.3448829958, y: 48.794408519, }, { $type: "PlainPoint", x: 2.3445369697, y: 48.792613388, }, { $type: "PlainPoint", x: 2.3444504632, y: 48.79238543, }, { $type: "PlainPoint", x: 2.3441044371, y: 48.79056173, }, { $type: "PlainPoint", x: 2.3442341969, y: 48.789336394, }, { $type: "PlainPoint", x: 2.3443639567, y: 48.788937442, }, { $type: "PlainPoint", x: 2.3452722751, y: 48.786942629, }, { $type: "PlainPoint", x: 2.3460940871, y: 48.785204229, }, { $type: "PlainPoint", x: 2.3460940871, y: 48.785147231, }, { $type: "PlainPoint", x: 2.3463968599, y: 48.784235258, }, { $type: "PlainPoint", x: 2.3464401131, y: 48.784035761, }, { $type: "PlainPoint", x: 2.3466563794, y: 48.782753266, }, { $type: "PlainPoint", x: 2.3466563794, y: 48.781071722, }, { $type: "PlainPoint", x: 2.3463536066, y: 48.778649061, }, { $type: "PlainPoint", x: 2.3462671001, y: 48.778107508, }, { $type: "PlainPoint", x: 2.3462671001, y: 48.777907988, }, { $type: "PlainPoint", x: 2.345921074, y: 48.775314147, }, { $type: "PlainPoint", x: 2.3458778208, y: 48.77508611, }, { $type: "PlainPoint", x: 2.3457048077, y: 48.773632354, }, { $type: "PlainPoint", x: 2.3455317947, y: 48.772093036, }, { $type: "PlainPoint", x: 2.3454885414, y: 48.771836479, }, { $type: "PlainPoint", x: 2.3454885414, y: 48.771779466, }, { $type: "PlainPoint", x: 2.3454452882, y: 48.771750959, }, ]; console.log(removeRedundantPoints(testPoints as Point[]))