Open-S2 / s2-tools / #16

Committed 09 Jan 2025 05:22AM UTC coverage: 93.159% (-0.3%) from 93.433%

Build # #16

Build Type

push

Committed by Mr Martian

Commit Message

fix readme badges; fix test bug

Run Details

58949 of 63278 relevant lines covered (93.16%)

95.84 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.48

/src/dataStructures/pointIndex.ts

import { Vector } from '../dataStore';
import { fromS2Points } from '../geometry/s1/chordAngle';
import { range } from '../geometry';
import { compare, fromS2Point, toCell } from '../dataStructures/uint64';
import { fromS1ChordAngle, getIntersectingCells } from '../geometry/s2/cap';

import { fromLonLat, fromST } from '../geometry/s2/point';

import type { S1ChordAngle } from '../geometry/s1/chordAngle';
import type { Face, Point3D, Properties } from '..';
import type { Uint64, Uint64Cell } from '../dataStructures/uint64';
import type { VectorStore, VectorStoreConstructor } from '../dataStore';

/** The kind of input required to store a point for proper indexing */
export interface PointShape<T extends Properties = Properties> {
  cell: Uint64Cell;
  point: Point3D;
  data: T;
}

/**
 * # Point Index
 *
 * ## Description
 * An index of cells with radius queries
 * Assumes the data is compatible with {@link Properties}
 *
 * ## Usage
 * ```ts
 * import { PointIndex } from 'gis-tools';
 * import { FileVector } from 'gis-tools/file';
 *
 * const pointIndex = new PointIndex();
 * // or used a file based store
 * const pointIndex = new PointIndex(FileVector);
 *
 * // insert a lon-lat
 * pointIndex.insertLonLat(lon, lat, data);
 * // insert an STPoint
 * pointIndex.insertFaceST(face, s, t, data);
 *
 * // after adding data build the index. NOTE: You don't have to call this, it will be called
 * // automatically when making a query
 * await pointIndex.sort();
 *
 * // you can search a range
 * const points = await pointIndex.searchRange(low, high);
 * // or a radius
 * const points = await pointIndex.searchRadius(center, radius);
 * ```
 */
export class PointIndex<T extends Properties = Properties> {
  #store: VectorStore<PointShape<T>>;
  #unsorted: boolean = false;

  /** @param store - the store to index. May be an in memory or disk */
  constructor(store: VectorStoreConstructor<PointShape<T>> = Vector) {
    this.#store = new store();
  }

  /**
   * Set the index store to a defined one. Useful for file based stores where we want to reuse data
   * @param store - the index store
   */
  setStore(store: VectorStore<PointShape<T>>): void {
    this.#store = store;
  }

  /**
   * Insert a point3D and its corresponding data to the index
   * @param point - the point to be indexed
   * @param data - the data associated with the point
   */
  insert(point: Point3D, data: T): void {
    this.#store.push({ cell: fromS2Point(point), point, data });
    this.#unsorted = true;
  }

  /**
   * Add a lon-lat pair to the cluster
   * @param lon - longitude in degrees
   * @param lat - latitude in degrees
   * @param data - the data associated with the point
   */
  insertLonLat(lon: number, lat: number, data: T): void {
    this.insert(fromLonLat(lon, lat), data);
  }

  /**
   * Insert an STPoint to the index
   * @param face - the face of the cell
   * @param s - the s coordinate
   * @param t - the t coordinate
   * @param data - the data associated with the point
   */
  insertFaceST(face: Face, s: number, t: number, data: T): void {
    this.insert(fromST(face, s, t), data);
  }

  /**
   * iterate through the points
   * @yields a PointShape<T>
   */
  async *[Symbol.asyncIterator](): AsyncGenerator<PointShape<T>> {
    await this.sort();
    yield* this.#store;
  }

  /** Sort the index in place if unsorted */
  async sort(): Promise<void> {
    if (!this.#unsorted) return;
    await this.#store.sort();
    this.#unsorted = false;
  }

  /**
   * Find the starting index of a search
   * @param id - input id to seek the starting index of the search
   * @returns the starting index
   */
  async lowerBound(id: Uint64): Promise<number> {
    const cellID = toCell(id);
    await this.sort();
    // lower bound search
    let lo: number = 0;
    let hi: number = this.#store.length;
    let mid: number;

    while (lo < hi) {
      mid = Math.floor(lo + (hi - lo) / 2);
      const { cell: midCell } = await this.#store.get(mid);
      if (compare(midCell, cellID) === -1) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    return lo;
  }

  /**
   * Search for points given a range of low and high ids
   * @param low - the lower bound
   * @param high - the upper bound
   * @param maxResults - the maximum number of results to return
   * @returns the points in the range
   */
  async searchRange(low: Uint64, high: Uint64, maxResults = Infinity): Promise<PointShape<T>[]> {
    await this.sort();
    const res: PointShape<T>[] = [];
    let loIdx = await this.lowerBound(low);
    const hiID = toCell(high);

    while (true) {
      if (loIdx >= this.#store.length) break;
      const currLo = await this.#store.get(loIdx);
      if (compare(currLo.cell, hiID) > 0) break;
      res.push(currLo);
      if (res.length >= maxResults) break;
      loIdx++;
    }

    return res;
  }

  /**
   * @param target - the point to search
   * @param radius - the search radius
   * @param maxResults - the maximum number of results
   * @returns the points within the radius
   */
  async searchRadius(
    target: Point3D,
    radius: S1ChordAngle,
    maxResults = Infinity,
  ): Promise<PointShape<T>[]> {
    await this.sort();
    const res: PointShape<T>[] = [];
    if (radius < 0) return res;
    const cap = fromS1ChordAngle<undefined>(target, radius, undefined);
    for (const cell of getIntersectingCells(cap)) {
      // iterate each covering s2cell min-max range on store. check distance from found
      // store Cells to target and if within radius add to results
      const [min, max] = range(cell);
      for (const point of await this.searchRange(min, max)) {
        if (fromS2Points(target, point.point) < radius) res.push(point);
        if (res.length >= maxResults) break;
      }
    }

    return res;
  }
}

1	import { Vector } from '../dataStore';
2	import { fromS2Points } from '../geometry/s1/chordAngle';
3	import { range } from '../geometry';
4	import { compare, fromS2Point, toCell } from '../dataStructures/uint64';
5	import { fromS1ChordAngle, getIntersectingCells } from '../geometry/s2/cap';
6
7	import { fromLonLat, fromST } from '../geometry/s2/point';
8
9	import type { S1ChordAngle } from '../geometry/s1/chordAngle';
10	import type { Face, Point3D, Properties } from '..';
11	import type { Uint64, Uint64Cell } from '../dataStructures/uint64';
12	import type { VectorStore, VectorStoreConstructor } from '../dataStore';
13
14	/** The kind of input required to store a point for proper indexing */
15	export interface PointShape<T extends Properties = Properties> {
16	cell: Uint64Cell;
17	point: Point3D;
18	data: T;
19	}
20
21	/**
22	* # Point Index
23	*
24	* ## Description
25	* An index of cells with radius queries
26	* Assumes the data is compatible with {@link Properties}
27	*
28	* ## Usage
29	* ```ts
30	* import { PointIndex } from 'gis-tools';
31	* import { FileVector } from 'gis-tools/file';
32	*
33	* const pointIndex = new PointIndex();
34	* // or used a file based store
35	* const pointIndex = new PointIndex(FileVector);
36	*
37	* // insert a lon-lat
38	* pointIndex.insertLonLat(lon, lat, data);
39	* // insert an STPoint
40	* pointIndex.insertFaceST(face, s, t, data);
41	*
42	* // after adding data build the index. NOTE: You don't have to call this, it will be called
43	* // automatically when making a query
44	* await pointIndex.sort();
45	*
46	* // you can search a range
47	* const points = await pointIndex.searchRange(low, high);
48	* // or a radius
49	* const points = await pointIndex.searchRadius(center, radius);
50	* ```
51	*/
52	export class PointIndex<T extends Properties = Properties> {
53	#store: VectorStore<PointShape<T>>;
54	#unsorted: boolean = false;	2✔
55
56	/** @param store - the store to index. May be an in memory or disk */
57	constructor(store: VectorStoreConstructor<PointShape<T>> = Vector) {	98✔
58	this.#store = new store();	124✔
59	}
60
61	/**
62	* Set the index store to a defined one. Useful for file based stores where we want to reuse data
63	* @param store - the index store
64	*/
65	setStore(store: VectorStore<PointShape<T>>): void {	×
66	this.#store = store;	58✔
67	}
68
69	/**
70	* Insert a point3D and its corresponding data to the index
71	* @param point - the point to be indexed
72	* @param data - the data associated with the point
73	*/
74	insert(point: Point3D, data: T): void {	76✔
75	this.#store.push({ cell: fromS2Point(point), point, data });	256✔
76	this.#unsorted = true;	116✔
77	}
78
79	/**
80	* Add a lon-lat pair to the cluster
81	* @param lon - longitude in degrees
82	* @param lat - latitude in degrees
83	* @param data - the data associated with the point
84	*/
85	insertLonLat(lon: number, lat: number, data: T): void {	100✔
86	this.insert(fromLonLat(lon, lat), data);	188✔
87	}
88
89	/**
90	* Insert an STPoint to the index
91	* @param face - the face of the cell
92	* @param s - the s coordinate
93	* @param t - the t coordinate
94	* @param data - the data associated with the point
95	*/
96	insertFaceST(face: Face, s: number, t: number, data: T): void {	108✔
97	this.insert(fromST(face, s, t), data);	196✔
98	}
99
100	/**
101	* iterate through the points
102	* @yields a PointShape<T>
103	*/
104	async *[Symbol.asyncIterator](): AsyncGenerator<PointShape<T>> {	60✔
105	await this.sort();	88✔
106	yield* this.#store;	116✔
107	}
108
109	/** Sort the index in place if unsorted */
110	async sort(): Promise<void> {	28✔
111	if (!this.#unsorted) return;	144✔
112	await this.#store.sort();	116✔
113	this.#unsorted = false;	132✔
114	}
115
116	/**
117	* Find the starting index of a search
118	* @param id - input id to seek the starting index of the search
119	* @returns the starting index
120	*/
121	async lowerBound(id: Uint64): Promise<number> {	48✔
122	const cellID = toCell(id);	120✔
123	await this.sort();	88✔
124	// lower bound search
125	let lo: number = 0;	60✔
126	let hi: number = this.#store.length;	128✔
127	let mid: number;	48✔
128
129	while (lo < hi) {	82✔
130	mid = Math.floor(lo + (hi - lo) / 2);	172✔
131	const { cell: midCell } = await this.#store.get(mid);	236✔
132	if (compare(midCell, cellID) === -1) {	174✔
133	lo = mid + 1;	104✔
134	} else {	34✔
135	hi = mid;	106✔
136	}
137	}	6✔
138
139	return lo;	74✔
140	}
141
142	/**
143	* Search for points given a range of low and high ids
144	* @param low - the lower bound
145	* @param high - the upper bound
146	* @param maxResults - the maximum number of results to return
147	* @returns the points in the range
148	*/
149	async searchRange(low: Uint64, high: Uint64, maxResults = Infinity): Promise<PointShape<T>[]> {	158✔
150	await this.sort();	88✔
151	const res: PointShape<T>[] = [];	76✔
152	let loIdx = await this.lowerBound(low);	172✔
153	const hiID = toCell(high);	120✔
154
155	while (true) {	70✔
156	if (loIdx >= this.#store.length) break;	204✔
157	const currLo = await this.#store.get(loIdx);	200✔
158	if (compare(currLo.cell, hiID) > 0) break;	216✔
159	res.push(currLo);	92✔
160	if (res.length >= maxResults) break;	192✔
161	loIdx++;	68✔
162	}	6✔
163
164	return res;	78✔
165	}
166
167	/**
168	* @param target - the point to search
169	* @param radius - the search radius
170	* @param maxResults - the maximum number of results
171	* @returns the points within the radius
172	*/
173	async searchRadius(	30✔
174	target: Point3D,	32✔
175	radius: S1ChordAngle,	32✔
176	maxResults = Infinity,	78✔
177	): Promise<PointShape<T>[]> {	8✔
178	await this.sort();	88✔
179	const res: PointShape<T>[] = [];	76✔
180	if (radius < 0) return res;	120✔
181	const cap = fromS1ChordAngle<undefined>(target, radius, undefined);	240✔
182	for (const cell of getIntersectingCells(cap)) {	202✔
183	// iterate each covering s2cell min-max range on store. check distance from found
184	// store Cells to target and if within radius add to results
185	const [min, max] = range(cell);	148✔
186	for (const point of await this.searchRange(min, max)) {	242✔
187	if (fromS2Points(target, point.point) < radius) res.push(point);	320✔
188	if (res.length >= maxResults) break;	228✔
189	}	18✔
190	}	6✔
191
192	return res;	66✔
193	}
194	}	2✔

Open-S2 / s2-tools / #16

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous