Open-S2 / gis-tools / #16

Committed 08 Feb 2025 04:21PM UTC coverage: 92.693% (-0.8%) from 93.517%

Build # #16

Build Type

push

Committed by Mr Martian

Commit Message

prep documentation for LASzipped

Run Details

62057 of 66949 relevant lines covered (92.69%)

95.97 hits per line

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

99.05

/src/dataStructures/pointIndex.ts

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

import type { S1ChordAngle } from '../geometry/s1/chordAngle';
import type {
  Face,
  FeatureIterator,
  JSONCollection,
  MValue,
  Projection,
  Properties,
  RGBA,
  S2CellId,
  VectorPoint,
  VectorPointM,
} 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: VectorPointM<M>;
}

/**
 * # Point Index
 *
 * ## Description
 * An index of cells with radius queries
 * Assumes the data is compatible with {@link https://open-s2.github.io/s2json/types/Properties.html}
 *
 * ## 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 | RGBA> {
  #store: VectorStore<PointShape<M>>;
  #unsorted: boolean = false;

  /**
   * @param store - the store to index. May be an in memory or disk
   * @param projection - the projection of the data, defaults to S2
   */
  constructor(
    store: VectorStoreConstructor<PointShape<M>> = Vector,
    private projection: Projection = 'S2',
  ) {
    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: VectorPointM<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: VectorPointM<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<unknown, M, M>): Promise<void> {
    for await (const feature of reader) this.insertFeature(feature);
  }

  /**
   * Add a vector feature. It will try to use the M-value first, but if it doesn't exist
   * it will use the feature properties data
   * @param data - any source of data like a feature collection or features themselves
   */
  insertFeature(data: JSONCollection<unknown, M, M>): void {
    const features = convert(this.projection, data, undefined, undefined, undefined, true);
    for (const { face = 0, geometry, properties } of features) {
      const { type, coordinates } = geometry;
      if (type === 'Point') {
        const { x: s, y: t, m } = coordinates;
        this.#insertFaceST(face, s, t, m ?? properties);
      } else if (type === 'MultiPoint') {
        for (const point of coordinates) {
          const { x: s, y: t, m } = point;
          this.#insertFaceST(face, s, t, m ?? properties);
        }
      }
    }
  }

  /**
   * Add a lon-lat pair to the cluster
   * @param ll - lon-lat vector point in degrees
   */
  insertLonLat(ll: VectorPoint<M>): void {
    this.insertFeature({
      type: 'VectorFeature',
      properties: ll.m ?? ({} as M),
      geometry: { type: 'Point', coordinates: ll, is3D: false },
    });
  }

  /**
   * 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.insertFeature({
      type: 'S2Feature',
      face,
      properties: data,
      geometry: { type: 'Point', coordinates: { x: s, y: t, m: data }, is3D: false },
    });
  }

  /**
   * 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) as VectorPointM<M>);
  }

  /**
   * 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. If high is not provided, the low-high range will be created from the low
   * @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>[] = [];
    if (high === undefined) {
      const [lo, hi] = range(low);
      low = lo;
      high = hi;
    }
    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;
  }

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

Open-S2 / gis-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