skia / buildbot / 0fef7d6691c14788697b32c84241d2ad1a90d535 / . / perf / modules / plot-simple-sk / kd_test.ts

// Copyright 2019 Google LLC | |

// | |

// Licensed under the Apache License, Version 2.0 (the "License"); | |

// you may not use this file except in compliance with the License. | |

// You may obtain a copy of the License at | |

// | |

// https://www.apache.org/licenses/LICENSE-2.0 | |

// | |

// Unless required by applicable law or agreed to in writing, software | |

// distributed under the License is distributed on an "AS IS" BASIS, | |

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |

// See the License for the specific language governing permissions and | |

// limitations under the License. | |

import { assert } from 'chai'; | |

import { KDTree, KDPoint } from './kd'; | |

describe('KDTree search', () => { | |

const points: KDPoint[] = [ | |

{ x: 5, y: 5 }, | |

{ x: 2, y: 2 }, | |

{ x: 6, y: 6 }, | |

]; | |

const distance = (a: KDPoint, b: KDPoint) => (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); | |

const tree = new KDTree(points, distance, ['x', 'y']); | |

it('finds the closest point', () => { | |

// Nearby | |

const nearest = tree.nearest({ x: 2.1, y: 2.1 }); | |

assert.deepEqual(nearest, { x: 2, y: 2 }); | |

}); | |

it('finds the closest point even if the distance is zero', () => { | |

// Exact match. | |

const nearest = tree.nearest({ x: 5, y: 5 }); | |

assert.deepEqual(nearest, { x: 5, y: 5 }); | |

}); | |

it('finds the closest point even if it is on the other side of the hyperplane', () => { | |

// This tests checking down the alternate tree. | |

// I.e. the point we are searching for has an x value of 4.5, so it | |

// should search down the 2,2 side of the tree, but it will turn out | |

// that the hyperplane through 5,5 will be closer than 2,2 so we need to | |

// look for a closer match in the 6,6 area, which will actually be our | |

// closest point. | |

const nearest = tree.nearest({ x: 4.5, y: 7 }); | |

assert.deepEqual(nearest, { x: 6, y: 6 }); | |

}); | |

}); |