Open-S2 / gis-tools / #4

Committed 14 Jan 2025 09:41AM UTC coverage: 93.032% (-0.3%) from 93.297%

Build # #4

Build Type

push

Committed by Mr Martian

Commit Message

rewrite geometry to vector; finished interpolators; dataStructures use BigInt; cluster and index simplified and support grids now; tests updated

Run Details

631 of 916 new or added lines in 37 files covered. (68.89%)

10 existing lines in 2 files now uncovered.

59812 of 64292 relevant lines covered (93.03%)

95.43 hits per line

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

98.84

/src/dataStructures/pointIndex.ts

import { Vector } from '../dataStore';
import { fromS2Points } from '../geometry/s1/chordAngle';
import { compareIDs, fromS2Point, range, toWM } from '../geometry';
import { fromS1ChordAngle, getIntersectingCells } from '../geometry/s2/cap';

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

import type { S1ChordAngle } from '../geometry/s1/chordAngle';
import type {
  Face,
  FeatureIterator,
  MValue,
  Properties,
  S2CellId,
  VectorFeatures,
  VectorPoint,
} from '..';
import type { VectorStore, VectorStoreConstructor } from '../dataStore';

/** The kind of input required to store a point for proper indexing */
export interface PointShape<M extends MValue = Properties> {
  cell: S2CellId;
  point: VectorPoint<M>;
}

/**
 * # 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-ts';
 * import { FileVector } from 'gis-tools-ts/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<M extends MValue = Properties> {
  #store: VectorStore<PointShape<M>>;
  #unsorted: boolean = false;

  /** @param store - the store to index. May be an in memory or disk */
  constructor(store: VectorStoreConstructor<PointShape<M>> = 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<M>>): void {
    this.#store = store;
  }

  /**
   * Insert a cell with the point and its corresponding data to the index
   * @param cell - the cell id to be indexed
   * @param point - the point to be indexed
   */
  insertID(cell: S2CellId, point: VectorPoint<M>): void {
    this.#store.push({ cell, point });
    this.#unsorted = true;
  }

  /**
   * Insert a point3D and its corresponding data to the index
   * @param point - the point to be indexed
   */
  insert(point: VectorPoint<M>): void {
    this.insertID(fromS2Point(point), point);
  }

  /**
   * Add all points from a reader. It will try to use the M-value first, but if it doesn't exist
   * it will use the feature properties data
   * @param reader - a reader containing the input data
   */
  async insertReader(reader: FeatureIterator<Record<string, unknown>, M, M>): Promise<void> {
    for await (const feature of reader) this.insertFeature(feature);
  }

  /**
   * Add a feature to the index
   * @param feature - vector feature (either S2 or WM)
   */
  insertFeature(feature: VectorFeatures<Record<string, unknown>, M, M>): void {
    if (feature.geometry.type !== 'Point' && feature.geometry.type !== 'MultiPoint') return;
    const {
      geometry: { coordinates, type },
    } = feature.type === 'S2Feature' ? toWM(feature) : feature;
    if (type === 'Point') {
      if (coordinates.m === undefined) coordinates.m = feature.properties;
      this.insertLonLat(coordinates);
    } else if (type === 'MultiPoint') {
      for (const point of coordinates) {
        if (point.m === undefined) point.m = feature.properties;
        this.insertLonLat(point);
      }
    }
  }

  /**
   * Add a lon-lat pair to the cluster
   * @param ll - lon-lat vector point in degrees
   */
  insertLonLat(ll: VectorPoint<M>): void {
    this.insert(fromLonLat(ll));
  }

  /**
   * 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: M): void {
    this.insert(fromST(face, s, t, data));
  }

  /**
   * iterate through the points
   * @yields a PointShape<T>
   */
  async *[Symbol.asyncIterator](): AsyncGenerator<PointShape<M>> {
    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: S2CellId): Promise<number> {
    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 (compareIDs(midCell, id) === -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: S2CellId,
    high: S2CellId,
    maxResults = Infinity,
  ): Promise<PointShape<M>[]> {
    await this.sort();
    const res: PointShape<M>[] = [];
    let loIdx = await this.lowerBound(low);

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

Open-S2 / gis-tools / #4

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