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

70.87

/src/dataStructures/pointCluster.ts

import { fromS2Points } from '../geometry/s1/chordAngle';
import {
  PointIndex,
  PointShape,
  Tile,
  defaultGetInterpolateCurrentValue,
  getInterpolation,
  getRGBAInterpolation,
} from '..';
import {
  addMut,
  divMutScalar,
  fromLonLat,
  fromST,
  mulScalar,
  normalize,
  toST,
} from '../geometry/s2/point';
import {
  convert,
  fromFacePosLevel,
  getVertices,
  level,
  parent,
  range,
  toS2Point,
  toWM,
} from '../geometry';

import type { S1ChordAngle } from '../geometry/s1/chordAngle';
import type {
  Face,
  JSONCollection,
  MValue,
  Projection,
  Properties,
  S2CellId,
  VectorPoint,
} from '../geometry';
import type {
  FeatureIterator,
  GetInterpolateValue,
  InterpolationFunction,
  InterpolationMethod,
  RGBA,
  RGBAInterpolationFunction,
  VectorFeatures,
} from '..';

import type { VectorStore, VectorStoreConstructor } from '../dataStore/vector';

/** The kind of input required to store a point for proper indexing */
export type ClusterStore<M extends MValue = Properties> = VectorStoreConstructor<
  PointShape<Cluster<M>>
>;

/** The type of search to use */
export type ClusterSearch = 'radial' | 'cell';

/** Options for point clustering */
export interface ClusterOptions<M extends MValue = Properties> {
  /** type of store to use. Defaults to an in memory store */
  store?: ClusterStore<M>;
  /** projection to use */
  projection?: Projection;
  /** Name of the layer to build when requesting a tile */
  layerName?: string;
  /** min zoom to generate clusters on */
  minzoom?: number;
  /** max zoom level to cluster the points on */
  maxzoom?: number;
  /** cluster radius in pixels relative to a 512x512 pixel tile */
  radius?: number;
  /** Specify the type of clustering [default: 'radial'] */
  search?: ClusterSearch;
  /** Used by cell search to specify the type of interpolation to use [default: 'lanczos'] */
  interpolation?: InterpolationMethod;
  /** Used by cell search to specify the interpolation function to use [default: 'z' value of the point] */
  getInterpolationValue?: 'rgba' | GetInterpolateValue<M>;
  /** Used by the cell search to specify the tile buffer size in pixels. [default: 0] */
  bufferSize?: number;
  /** Grid size, assumed pixel ratio. [default: 512] */
  gridSize?: number;
}

/** An export of the data as a grid */
export interface TileGrid {
  name: string;
  size: number;
  data: number[];
}

/** A cluster is a storage device to maintain groups of information in a cluster */
export interface Cluster<M extends MValue = Properties> extends Properties {
  data: M;
  visited: boolean;
  value: number | RGBA;
}

/**
 * Create a cluster with the correct value
 * @param data - the m-value of the point
 * @param value - the interpolated value as a number or RGBA of the cluster
 * @returns - a new cluster with the correct value and m-value
 */
function toCluster<M extends MValue = Properties>(data: M, value: number | RGBA): Cluster<M> {
  return { data, visited: false, value };
}

/** Compare two data items, return true to merge data */
export type Comparitor<M extends MValue = Properties> = (a: M, b: M) => boolean;

/**
 * # Point Cluster
 *
 * ## Description
 * A cluster store to index points at each zoom level
 *
 * ## Usage
 * ```ts
 * import { PointCluster } from 'gis-tools-ts';
 * const pointCluster = new PointCluster();
 *
 * // add a lon-lat
 * pointCluster.insertLonLat(lon, lat, data);
 * // add an STPoint
 * pointCluster.insertFaceST(face, s, t, data);
 *
 * // after adding data build the clusters
 * await pointCluster.buildClusters();
 *
 * // get the clusters for a tile
 * const tile = await pointCluster.getTile(id);
 * // or get the raw cluster data
 * const clusters = await pointCluster.getCellData(id);
 * ```
 */
export class PointCluster<M extends MValue = Properties> {
  projection: Projection;
  layerName: string;
  minzoom: number;
  maxzoom: number;
  radius: number;
  bufferSize: number;
  search: ClusterSearch;
  interpolation: InterpolationFunction<M> | RGBAInterpolationFunction;
  getValue: GetInterpolateValue<M>;
  gridSize: number; // a default is a 512x512 pixel tile
  indexes = new Map<number, PointIndex<Cluster<M>>>();

  /**
   * @param data - if provided, the data to index
   * @param options - cluster options on how to build the cluster
   * @param maxzoomStore - the store to use for the maxzoom index
   */
  constructor(
    data?: JSONCollection<Record<string, unknown>, M, M>,
    options?: ClusterOptions<M>,
    maxzoomStore?: VectorStore<PointShape<Cluster<M>>>,
  ) {
    this.projection = options?.projection ?? 'S2';
    this.layerName = options?.layerName ?? 'default';
    this.minzoom = Math.max(options?.minzoom ?? 0, 0);
    this.maxzoom = Math.min(options?.maxzoom ?? 16, 29);
    this.radius = options?.radius ?? 40;
    this.bufferSize = options?.bufferSize ?? 0;
    this.gridSize = options?.gridSize ?? 512;
    this.search = options?.search ?? 'radial';
    const isRGBA = options?.getInterpolationValue === 'rgba';
    const interpolation = options?.interpolation ?? 'lanczos';
    this.interpolation = isRGBA
      ? getRGBAInterpolation(interpolation)
      : getInterpolation<M>(interpolation);
    this.getValue =
      options?.getInterpolationValue === 'rgba' || this.search === 'radial'
        ? () => 1
        : (options?.getInterpolationValue ?? defaultGetInterpolateCurrentValue);
    // one extra zoom incase its a cell search system (bottom zoom isn't clustered to a cell)
    for (let zoom = this.minzoom; zoom <= this.maxzoom + 1; zoom++) {
      this.indexes.set(zoom, new PointIndex<Cluster<M>>(options?.store));
    }
    if (maxzoomStore !== undefined) {
      const maxzoomIndex = this.indexes.get(this.maxzoom);
      maxzoomIndex?.setStore(maxzoomStore);
    }
    // convert features if provided
    if (data !== undefined) {
      const features = convert(this.projection, data, false, undefined, this.maxzoom, true);
      for (const feature of features) {
        const face = feature.face ?? 0;
        const { type, coordinates } = feature.geometry;
        if (type === 'Point') {
          const { x: s, y: t } = coordinates;
          this.insertFaceST(face, s, t, feature.properties);
        }
      }
    }
  }

  /**
   * Add a point to the maxzoom index. The point is a Point3D
   * @param point - the point to add
   */
  insert(point: VectorPoint<M>): void {
    const { x, y, z, m } = point;
    const maxzoomIndex = this.indexes.get(this.maxzoom);
    const value = this.getValue(point);
    maxzoomIndex?.insert({ x, y, z, m: toCluster<M>(m!, value) });
  }

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

  /**
   * Build the clusters when done adding points
   * @param cmp_ - custom compare function
   */
  async buildClusters(cmp_?: Comparitor<M>): Promise<void> {
    const { minzoom, maxzoom, search } = this;
    const cmp: Comparitor<M> = cmp_ ?? ((_a: M, _b: M) => true);
    let zoom = search === 'radial' ? maxzoom - 1 : maxzoom;
    for (; zoom >= minzoom; zoom--) {
      const curIndex = this.indexes.get(zoom);
      const queryIndex = this.indexes.get(zoom + 1);
      if (curIndex === undefined || queryIndex === undefined) throw new Error('Index not found');
      if (search === 'radial') await this.#clusterRadius(zoom, queryIndex, curIndex, cmp);
      else await this.#clusterCells(zoom, queryIndex, curIndex);
    }
    // ensure all point indexes are sorted
    for (const index of this.indexes.values()) await index.sort();
  }

  /**
   * Radial clustering
   * @param zoom - the zoom level
   * @param queryIndex - the index to query
   * @param currIndex - the index to insert into
   * @param cmp - the compare function
   */
  async #clusterRadius(
    zoom: number,
    queryIndex: PointIndex<Cluster<M>>,
    currIndex: PointIndex<Cluster<M>>,
    cmp: Comparitor<M>,
  ): Promise<void> {
    const radius = this.#getLevelRadius(zoom);
    for await (const clusterPoint of queryIndex) {
      const { point } = clusterPoint;
      const clusterData = point.m!;
      if (clusterData.visited) continue;
      clusterData.visited = true;
      // setup a new weighted cluster point
      const newClusterPoint = mulScalar(point, clusterData.value as number);
      let newNumPoints = clusterData.value as number;
      // joining all points found within radius
      const points = await queryIndex.searchRadius(point, radius);
      for (const { point: foundPoint } of points) {
        const foundData = foundPoint.m!;
        // only add points that match or have not been visited already
        if (!cmp(clusterData.data, foundData.data) || foundData.visited) continue;
        foundData.visited = true;
        // weighted add to newClusterPoint position
        addMut(newClusterPoint, mulScalar(foundPoint, foundData.value as number));
        newNumPoints += foundData.value as number;
      }
      // finish position average
      divMutScalar(newClusterPoint, newNumPoints);
      normalize(newClusterPoint);
      // store the new cluster point
      const { x, y, z } = newClusterPoint;
      currIndex.insert({ x, y, z, m: toCluster(clusterData.data, newNumPoints) });
    }
  }

  /**
   * Cell clustering
   * @param zoom - the zoom level
   * @param queryIndex - the index to query
   * @param currIndex - the index to insert into
   */
  async #clusterCells(
    zoom: number,
    queryIndex: PointIndex<Cluster<M>>,
    currIndex: PointIndex<Cluster<M>>,
  ): Promise<void> {
    const { interpolation, getValue, maxzoom } = this;
    for await (const clusterPoint of queryIndex) {
      const {
        cell,
        point: { m: clusterData },
      } = clusterPoint;
      const parentID = parent(cell, zoom);
      const parentPoint = toS2Point(parentID);
      // get all cells in parentID who haven't been visited yet. maxzoom does a radial search
      const cellPoints = (
        maxzoom === zoom
          ? await queryIndex.searchRadius(parentPoint, this.#getLevelRadius(zoom))
          : await queryIndex.searchRange(parentID, parentID)
      ).filter(({ point }) => point.m!.visited);
      // use interpolation
      if (cellPoints.length > 0) {
        for (const { point } of cellPoints) point.m!.visited = true;
        const cellPointsData = cellPoints.map(({ point }) => {
          const { x, y, z } = point;
          return { x, y, z, m: point.m!.m };
        });
        // @ts-expect-error - we know M is correct
        const interpValue = interpolation(parentPoint, cellPointsData, getValue);
        const { x, y, z } = parentPoint;
        currIndex.insert({ x, y, z, m: toCluster(clusterData!.data, interpValue) });
      }
    }
  }

  /**
   * @param id - the cell id
   * @returns - the data within the range of the tile id
   */
  async getCellData(id: S2CellId): Promise<undefined | PointShape<Cluster<M>>[]> {
    const { minzoom, maxzoom, indexes } = this;
    const zoom = level(id);
    if (zoom < minzoom) return;
    const [min, max] = range(id);
    const levelIndex = indexes.get(Math.min(zoom, maxzoom));

    return await levelIndex?.searchRange(min, max);
  }

  /**
   * @param id - the id of the vector tile
   * @returns - the vector tile
   */
  async getTile(
    id: S2CellId,
  ): Promise<undefined | Tile<Record<string, unknown>, { value: number | RGBA }, M>> {
    const data = await this.getCellData(id);
    if (data === undefined) return;
    const tile = new Tile<Record<string, unknown>, { value: number | RGBA }, M>(id);
    for (const { point } of data) {
      const [face, s, t] = toST(point);
      const { value, data } = point.m!;
      tile.addFeature(
        {
          type: 'VectorFeature',
          face,
          geometry: { is3D: false, type: 'Point', coordinates: { x: s, y: t, m: { value } } },
          properties: data,
        },
        this.layerName,
      );
    }

    // transform the geometry to be relative to the tile
    tile.transform(0, this.maxzoom);

    return tile;
  }

  /**
   * Get the point data as a grid of a tile
   * @param id - the cell id
   * @returns - a tile grid
   */
  async getTileGrid(id: S2CellId): Promise<undefined | TileGrid> {
    const { layerName, gridSize } = this;
    const cellData = await this.getCellData(id);
    if (cellData === undefined) return;

    // TODO: Organize all the cell data into a grid of gridSize. Then flatten if RGBA. Ship off.

    return {
      name: layerName,
      size: gridSize,
      // TODO: Build data
      data: [],
    };
  }

  /**
   * Get a S1ChordAngle relative to a tile zoom level
   * @param zoom - the zoom level to build a radius
   * @returns - the appropriate radius for the given zoom
   */
  #getLevelRadius(zoom: number): S1ChordAngle {
    const multiplier = this.radius / this.gridSize;
    const cell = fromFacePosLevel(0, 0n, zoom);
    const [lo, hi] = getVertices(cell);
    const angle = fromS2Points(lo, hi);
    return angle * multiplier;
  }
}

1	import { fromS2Points } from '../geometry/s1/chordAngle';	228✔
2	import {	468✔
3	PointIndex,
4	PointShape,
5	Tile,
6	defaultGetInterpolateCurrentValue,
7	getInterpolation,
8	getRGBAInterpolation,
9	} from '..';
10	import {	456✔
11	addMut,
12	divMutScalar,
13	fromLonLat,
14	fromST,
15	mulScalar,
16	normalize,
17	toST,
18	} from '../geometry/s2/point';
19	import {	458✔
20	convert,
21	fromFacePosLevel,
22	getVertices,
23	level,
24	parent,
25	range,
26	toS2Point,
27	toWM,
28	} from '../geometry';
29
30	import type { S1ChordAngle } from '../geometry/s1/chordAngle';
31	import type {
32	Face,
33	JSONCollection,
34	MValue,
35	Projection,
36	Properties,
37	S2CellId,
38	VectorPoint,
39	} from '../geometry';
40	import type {
41	FeatureIterator,
42	GetInterpolateValue,
43	InterpolationFunction,
44	InterpolationMethod,
45	RGBA,
46	RGBAInterpolationFunction,
47	VectorFeatures,
48	} from '..';
49
50	import type { VectorStore, VectorStoreConstructor } from '../dataStore/vector';
51
52	/** The kind of input required to store a point for proper indexing */
53	export type ClusterStore<M extends MValue = Properties> = VectorStoreConstructor<
54	PointShape<Cluster<M>>
55	>;
56
57	/** The type of search to use */
58	export type ClusterSearch = 'radial' \| 'cell';
59
60	/** Options for point clustering */
61	export interface ClusterOptions<M extends MValue = Properties> {
62	/** type of store to use. Defaults to an in memory store */
63	store?: ClusterStore<M>;
64	/** projection to use */
65	projection?: Projection;
66	/** Name of the layer to build when requesting a tile */
67	layerName?: string;
68	/** min zoom to generate clusters on */
69	minzoom?: number;
70	/** max zoom level to cluster the points on */
71	maxzoom?: number;
72	/** cluster radius in pixels relative to a 512x512 pixel tile */
73	radius?: number;
74	/** Specify the type of clustering [default: 'radial'] */
75	search?: ClusterSearch;
76	/** Used by cell search to specify the type of interpolation to use [default: 'lanczos'] */
77	interpolation?: InterpolationMethod;
78	/** Used by cell search to specify the interpolation function to use [default: 'z' value of the point] */
79	getInterpolationValue?: 'rgba' \| GetInterpolateValue<M>;
80	/** Used by the cell search to specify the tile buffer size in pixels. [default: 0] */
81	bufferSize?: number;
82	/** Grid size, assumed pixel ratio. [default: 512] */
83	gridSize?: number;
84	}
85
86	/** An export of the data as a grid */
87	export interface TileGrid {
88	name: string;
89	size: number;
90	data: number[];
91	}
92
93	/** A cluster is a storage device to maintain groups of information in a cluster */
94	export interface Cluster<M extends MValue = Properties> extends Properties {
95	data: M;
96	visited: boolean;
97	value: number \| RGBA;
98	}
99
100	/**
101	* Create a cluster with the correct value
102	* @param data - the m-value of the point
103	* @param value - the interpolated value as a number or RGBA of the cluster
104	* @returns - a new cluster with the correct value and m-value
105	*/
106	function toCluster<M extends MValue = Properties>(data: M, value: number \| RGBA): Cluster<M> {	98✔
107	return { data, visited: false, value };	162✔
108	}
109
110	/** Compare two data items, return true to merge data */
111	export type Comparitor<M extends MValue = Properties> = (a: M, b: M) => boolean;
112
113	/**
114	* # Point Cluster
115	*
116	* ## Description
117	* A cluster store to index points at each zoom level
118	*
119	* ## Usage
120	* ```ts
121	* import { PointCluster } from 'gis-tools-ts';
122	* const pointCluster = new PointCluster();
123	*
124	* // add a lon-lat
125	* pointCluster.insertLonLat(lon, lat, data);
126	* // add an STPoint
127	* pointCluster.insertFaceST(face, s, t, data);
128	*
129	* // after adding data build the clusters
130	* await pointCluster.buildClusters();
131	*
132	* // get the clusters for a tile
133	* const tile = await pointCluster.getTile(id);
134	* // or get the raw cluster data
135	* const clusters = await pointCluster.getCellData(id);
136	* ```
137	*/
138	export class PointCluster<M extends MValue = Properties> {
139	projection: Projection;
140	layerName: string;
141	minzoom: number;
142	maxzoom: number;
143	radius: number;
144	bufferSize: number;
145	search: ClusterSearch;
146	interpolation: InterpolationFunction<M> \| RGBAInterpolationFunction;
147	getValue: GetInterpolateValue<M>;
148	gridSize: number; // a default is a 512x512 pixel tile
149	indexes = new Map<number, PointIndex<Cluster<M>>>();	2✔
150
151	/**
152	* @param data - if provided, the data to index
153	* @param options - cluster options on how to build the cluster
154	* @param maxzoomStore - the store to use for the maxzoom index
155	*/
156	constructor(	26✔
157	data?: JSONCollection<Record<string, unknown>, M, M>,	24✔
158	options?: ClusterOptions<M>,	36✔
159	maxzoomStore?: VectorStore<PointShape<Cluster<M>>>,	56✔
160	) {	8✔
161	this.projection = options?.projection ?? 'S2';	200✔
162	this.layerName = options?.layerName ?? 'default';	212✔
163	this.minzoom = Math.max(options?.minzoom ?? 0, 0);	216✔
164	this.maxzoom = Math.min(options?.maxzoom ?? 16, 29);	224✔
165	this.radius = options?.radius ?? 40;	160✔
166	this.bufferSize = options?.bufferSize ?? 0;	188✔
167	this.gridSize = options?.gridSize ?? 512;	180✔
168	this.search = options?.search ?? 'radial';	184✔
169	const isRGBA = options?.getInterpolationValue === 'rgba';	244✔
170	const interpolation = options?.interpolation ?? 'lanczos';	248✔
171	this.interpolation = isRGBA	130✔
172	? getRGBAInterpolation(interpolation)	80✔
173	: getInterpolation<M>(interpolation);	130✔
174	this.getValue =	76✔
175	options?.getInterpolationValue === 'rgba' \|\| this.search === 'radial'	288✔
176	? () => 1	36✔
177	: (options?.getInterpolationValue ?? defaultGetInterpolateCurrentValue);	140✔
178	// one extra zoom incase its a cell search system (bottom zoom isn't clustered to a cell)
179	for (let zoom = this.minzoom; zoom <= this.maxzoom + 1; zoom++) {	270✔
180	this.indexes.set(zoom, new PointIndex<Cluster<M>>(options?.store));	256✔
181	}	6✔
182	if (maxzoomStore !== undefined) {	142✔
183	const maxzoomIndex = this.indexes.get(this.maxzoom);	116✔
184	maxzoomIndex?.setStore(maxzoomStore);	92✔
185	}	6✔
186	// convert features if provided
187	if (data !== undefined) {	114✔
188	const features = convert(this.projection, data, false, undefined, this.maxzoom, true);	368✔
189	for (const feature of features) {	154✔
190	const face = feature.face ?? 0;	156✔
191	const { type, coordinates } = feature.geometry;	220✔
192	if (type === 'Point') {	122✔
193	const { x: s, y: t } = coordinates;	180✔
194	this.insertFaceST(face, s, t, feature.properties);	268✔
195	}	26✔
196	}	18✔
197	}	18✔
198	}
199
200	/**
201	* Add a point to the maxzoom index. The point is a Point3D
202	* @param point - the point to add
203	*/
204	insert(point: VectorPoint<M>): void {	52✔
205	const { x, y, z, m } = point;	132✔
206	const maxzoomIndex = this.indexes.get(this.maxzoom);	224✔
207	const value = this.getValue(point);	156✔
208	maxzoomIndex?.insert({ x, y, z, m: toCluster<M>(m!, value) });	270✔
209	}
210
211	/**
212	* Add all points from a reader. It will try to use the M-value first, but if it doesn't exist
213	* it will use the feature properties data
214	* @param reader - a reader containing the input data
215	*/
216	async insertReader(reader: FeatureIterator<Record<string, unknown>, M, M>): Promise<void> {	68✔
217	for await (const feature of reader) this.insertFeature(feature);	302✔
218	}
219
220	/**
221	* Add a vector feature. It will try to use the M-value first, but if it doesn't exist
222	* it will use the feature properties data
223	* @param feature - vector feature (either S2 or WM)
224	*/
225	insertFeature(feature: VectorFeatures<Record<string, unknown>, M, M>): void {	74✔
226	if (feature.geometry.type !== 'Point' && feature.geometry.type !== 'MultiPoint') return;	372✔
227	const {	64✔
228	geometry: { coordinates, type },	156✔
229	} = feature.type === 'S2Feature' ? toWM(feature) : feature;	192✔
230	if (type === 'Point') {	106✔
231	if (coordinates.m === undefined) coordinates.m = feature.properties;	320✔
232	this.insertLonLat(coordinates);	160✔
233	} else if (type === 'MultiPoint') {	72✔
234	for (const point of coordinates) {	80✔
235	if (point.m === undefined) point.m = feature.properties;	146✔
236	this.insertLonLat(point);	76✔
237	}	10✔
238	}	20✔
239	}
240
241	/**
242	* Add a lon-lat pair to the cluster
243	* @param ll - lon-lat vector point in degrees
244	*/
245	insertLonLat(ll: VectorPoint<M>): void {	52✔
246	this.insert(fromLonLat(ll));	140✔
247	}
248
249	/**
250	* Insert an STPoint to the index
251	* @param face - the face of the cell
252	* @param s - the s coordinate
253	* @param t - the t coordinate
254	* @param data - the data associated with the point
255	*/
256	insertFaceST(face: Face, s: number, t: number, data: M): void {	108✔
257	this.insert(fromST(face, s, t, data));	190✔
258	}
259
260	/**
261	* Build the clusters when done adding points
262	* @param cmp_ - custom compare function
263	*/
264	async buildClusters(cmp_?: Comparitor<M>): Promise<void> {	62✔
265	const { minzoom, maxzoom, search } = this;	184✔
266	const cmp: Comparitor<M> = cmp_ ?? ((_a: M, _b: M) => true);	168✔
267	let zoom = search === 'radial' ? maxzoom - 1 : maxzoom;	212✔
268	for (; zoom >= minzoom; zoom--) {	142✔
269	const curIndex = this.indexes.get(zoom);	184✔
270	const queryIndex = this.indexes.get(zoom + 1);	208✔
271	if (curIndex === undefined \|\| queryIndex === undefined) throw new Error('Index not found');	344✔
272	if (search === 'radial') await this.#clusterRadius(zoom, queryIndex, curIndex, cmp);	402✔
273	else await this.#clusterCells(zoom, queryIndex, curIndex);	136✔
274	}	6✔
275	// ensure all point indexes are sorted
276	for (const index of this.indexes.values()) await index.sort();	304✔
277	}
278
279	/**
280	* Radial clustering
281	* @param zoom - the zoom level
282	* @param queryIndex - the index to query
283	* @param currIndex - the index to insert into
284	* @param cmp - the compare function
285	*/
286	async #clusterRadius(	32✔
287	zoom: number,	24✔
288	queryIndex: PointIndex<Cluster<M>>,	48✔
289	currIndex: PointIndex<Cluster<M>>,	44✔
290	cmp: Comparitor<M>,	18✔
291	): Promise<void> {	8✔
292	const radius = this.#getLevelRadius(zoom);	184✔
293	for await (const clusterPoint of queryIndex) {	198✔
294	const { point } = clusterPoint;	148✔
295	const clusterData = point.m!;	136✔
296	if (clusterData.visited) continue;	184✔
297	clusterData.visited = true;	132✔
298	// setup a new weighted cluster point
299	const newClusterPoint = mulScalar(point, clusterData.value as number);	264✔
300	let newNumPoints = clusterData.value as number;	172✔
301	// joining all points found within radius
302	const points = await queryIndex.searchRadius(point, radius);	264✔
303	for (const { point: foundPoint } of points) {	202✔
304	const foundData = foundPoint.m!;	156✔
305	// only add points that match or have not been visited already
306	if (!cmp(clusterData.data, foundData.data) \|\| foundData.visited) continue;	360✔
307	foundData.visited = true;	132✔
308	// weighted add to newClusterPoint position
309	addMut(newClusterPoint, mulScalar(foundPoint, foundData.value as number));	288✔
310	newNumPoints += foundData.value as number;	180✔
311	}	6✔
312	// finish position average
313	divMutScalar(newClusterPoint, newNumPoints);	200✔
314	normalize(newClusterPoint);	132✔
315	// store the new cluster point
316	const { x, y, z } = newClusterPoint;	168✔
317	currIndex.insert({ x, y, z, m: toCluster(clusterData.data, newNumPoints) });	340✔
NEW 318	}	×
NEW 319	}	×
NEW 320		×
NEW 321	/**	×
NEW 322	* Cell clustering	×
NEW 323	* @param zoom - the zoom level	×
NEW 324	* @param queryIndex - the index to query	×
NEW 325	* @param currIndex - the index to insert into	×
NEW 326	*/	×
NEW 327	async #clusterCells(	×
NEW 328	zoom: number,	×
NEW 329	queryIndex: PointIndex<Cluster<M>>,	×
NEW 330	currIndex: PointIndex<Cluster<M>>,	×
NEW 331	): Promise<void> {	×
NEW 332	const { interpolation, getValue, maxzoom } = this;	×
NEW 333	for await (const clusterPoint of queryIndex) {	×
NEW 334	const {	×
NEW 335	cell,	×
NEW 336	point: { m: clusterData },	×
NEW 337	} = clusterPoint;	×
NEW 338	const parentID = parent(cell, zoom);	×
NEW 339	const parentPoint = toS2Point(parentID);	×
NEW 340	// get all cells in parentID who haven't been visited yet. maxzoom does a radial search	×
NEW 341	const cellPoints = (	×
NEW 342	maxzoom === zoom	×
NEW 343	? await queryIndex.searchRadius(parentPoint, this.#getLevelRadius(zoom))	×
NEW 344	: await queryIndex.searchRange(parentID, parentID)	×
NEW 345	).filter(({ point }) => point.m!.visited);	×
NEW 346	// use interpolation	×
NEW 347	if (cellPoints.length > 0) {	×
NEW 348	for (const { point } of cellPoints) point.m!.visited = true;	×
NEW 349	const cellPointsData = cellPoints.map(({ point }) => {	×
NEW 350	const { x, y, z } = point;	×
NEW 351	return { x, y, z, m: point.m!.m };	×
NEW 352	});	×
NEW 353	// @ts-expect-error - we know M is correct	×
NEW 354	const interpValue = interpolation(parentPoint, cellPointsData, getValue);	×
NEW 355	const { x, y, z } = parentPoint;	×
NEW 356	currIndex.insert({ x, y, z, m: toCluster(clusterData!.data, interpValue) });	×
NEW 357	}	×
358	}	24✔
359	}
360
361	/**
362	* @param id - the cell id
363	* @returns - the data within the range of the tile id
364	*/
365	async getCellData(id: S2CellId): Promise<undefined \| PointShape<Cluster<M>>[]> {	50✔
366	const { minzoom, maxzoom, indexes } = this;	188✔
367	const zoom = level(id);	108✔
368	if (zoom < minzoom) return;	128✔
369	const [min, max] = range(id);	132✔
370	const levelIndex = indexes.get(Math.min(zoom, maxzoom));	240✔
371
372	return await levelIndex?.searchRange(min, max);	222✔
373	}
374
375	/**
376	* @param id - the id of the vector tile
377	* @returns - the vector tile
378	*/
379	async getTile(	20✔
380	id: S2CellId,	14✔
381	): Promise<undefined \| Tile<Record<string, unknown>, { value: number \| RGBA }, M>> {	8✔
382	const data = await this.getCellData(id);	176✔
383	if (data === undefined) return;	144✔
384	const tile = new Tile<Record<string, unknown>, { value: number \| RGBA }, M>(id);	120✔
385	for (const { point } of data) {	138✔
386	const [face, s, t] = toST(point);	156✔
387	const { value, data } = point.m!;	152✔
388	tile.addFeature(	84✔
389	{	36✔
390	type: 'VectorFeature',	120✔
391	face,	52✔
392	geometry: { is3D: false, type: 'Point', coordinates: { x: s, y: t, m: { value } } },	368✔
393	properties: data,	88✔
394	},	12✔
395	this.layerName,	56✔
396	);	24✔
397	}	6✔
398
399	// transform the geometry to be relative to the tile
400	tile.transform(0, this.maxzoom);	144✔
401
UNCOV 402	return tile;	×
UNCOV 403	}	×
UNCOV 404		×
NEW 405	/**	×
NEW 406	* Get the point data as a grid of a tile	×
NEW 407	* @param id - the cell id	×
NEW 408	* @returns - a tile grid	×
NEW 409	*/	×
NEW 410	async getTileGrid(id: S2CellId): Promise<undefined \| TileGrid> {	×
NEW 411	const { layerName, gridSize } = this;	×
NEW 412	const cellData = await this.getCellData(id);	×
NEW 413	if (cellData === undefined) return;	×
NEW 414		×
NEW 415	// TODO: Organize all the cell data into a grid of gridSize. Then flatten if RGBA. Ship off.	×
NEW 416		×
NEW 417	return {	×
NEW 418	name: layerName,	×
NEW 419	size: gridSize,	×
NEW 420	// TODO: Build data	×
NEW 421	data: [],	×
422	};	16✔
423	}
424
425	/**
426	* Get a S1ChordAngle relative to a tile zoom level
427	* @param zoom - the zoom level to build a radius
428	* @returns - the appropriate radius for the given zoom
429	*/
430	#getLevelRadius(zoom: number): S1ChordAngle {	66✔
431	const multiplier = this.radius / this.gridSize;	204✔
432	const cell = fromFacePosLevel(0, 0n, zoom);	188✔
433	const [lo, hi] = getVertices(cell);	156✔
434	const angle = fromS2Points(lo, hi);	156✔
435	return angle * multiplier;	124✔
436	}
437	}	4✔

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