Skip to content

Instantly share code, notes, and snippets.

@dir01

dir01/removeRedundantPoints.ts

Created April 9, 2019 09:29
Show Gist options
  • Save dir01/b80170d735b69bcf1eb71d4831cab62e to your computer and use it in GitHub Desktop.
Save dir01/b80170d735b69bcf1eb71d4831cab62e to your computer and use it in GitHub Desktop.
Download ZIP
Given an array of points, remove those, which are placed on a straight (and almost straight) line between two neighbor points
Raw
removeRedundantPoints.ts
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[]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment