HTM tree indexes and queries. More...

#include "geometry.h"

Include dependency graph for tree.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	htm_tree_entry
	An entry (a row ID and a position) in an HTM tree. More...
struct	htm_tree
	An HTM tree containing a list of points sorted on HTM ID (tree entries), and optionally an index over the points that allows for fast spatial searches/counts. More...
Functions
struct htm_tree_entry	__attribute__ ((aligned(16)))
enum htm_errcode	htm_tree_init (struct htm_tree tree, const char const treefile, const char *const datafile)
	Initializes an HTM tree from the given tree and data files, returning HTM_OK on success.
void	htm_tree_destroy (struct htm_tree *tree)
	Releases the resources for the given HTM tree.
enum htm_errcode	htm_tree_lock (struct htm_tree *tree, size_t datathresh)
	Locks the HTM tree index in memory.
int64_t	htm_tree_s2circle_scan (const struct htm_tree tree, const struct htm_v3 center, double radius, enum htm_errcode *err)
	Returns the number of points in `tree` that are inside the spherical circle with the given center and radius.
int64_t	htm_tree_s2ellipse_scan (const struct htm_tree tree, const struct htm_s2ellipse ellipse, enum htm_errcode *err)
	Returns the number of points in `tree` that are inside the given spherical ellipse.
int64_t	htm_tree_s2cpoly_scan (const struct htm_tree tree, const struct htm_s2cpoly poly, enum htm_errcode *err)
	Returns the number of points in `tree` that are inside the given spherical convex polygon.
int64_t	htm_tree_s2circle_count (const struct htm_tree tree, const struct htm_v3 center, double radius, enum htm_errcode *err)
	Returns the number of points in `tree` that are inside the spherical circle with the given center and radius.
int64_t	htm_tree_s2ellipse_count (const struct htm_tree tree, const struct htm_s2ellipse ellipse, enum htm_errcode *err)
	Returns the number of points in `tree` that are inside the given spherical ellipse.
int64_t	htm_tree_s2cpoly_count (const struct htm_tree tree, const struct htm_s2cpoly poly, enum htm_errcode *err)
	Returns the number of points in `tree` that are inside the given spherical convex polygon.
struct htm_range	htm_tree_s2circle_range (const struct htm_tree tree, const struct htm_v3 center, double radius, enum htm_errcode *err)
	Returns a lower and upper bound on the number of points in `tree` that are inside the spherical circle with the given center and radius.
struct htm_range	htm_tree_s2ellipse_range (const struct htm_tree tree, const struct htm_s2ellipse ellipse, enum htm_errcode *err)
	Returns a lower and upper bound on the number of points in `tree` that are inside the given spherical ellipse.
struct htm_range	htm_tree_s2cpoly_range (const struct htm_tree tree, const struct htm_s2cpoly poly, enum htm_errcode *err)
	Returns a lower and upper bound on the number of points in `tree` that are inside the given spherical convex polygon.
Variables
struct htm_v3	v
	Unit vector position.
int64_t	rowid
	Row ID.
uint64_t	leafthresh
	Min # of points in an internal node.
uint64_t	count
	Total # of points in tree.
const unsigned char *	root [8]
	Pointers to HTM root nodes.
struct htm_tree_entry *	entries
	Data file memory map.
const void *	index
	Tree file memory map.
size_t	indexsz
	Size of tree file memory-map (bytes).
size_t	datasz
	Size of data file memory-map (bytes).
int	indexfd
	File descriptor for tree file.
int	datafd
	File descriptor for data file.

Detailed Description

HTM tree indexes and queries.

Authors:: Serge Monkewitz

Copyright:: IPAC/Caltech

Definition in file tree.h.

Function Documentation

int64_t htm_tree_s2circle_count	(	const struct htm_tree *	tree,
		const struct htm_v3 *	center,
		double	radius,
		enum htm_errcode *	err
	)

Returns the number of points in tree that are inside the spherical circle with the given center and radius.

If an error occurs, the return value is negative, and *err is set to an error code describing the reason for the failure.

Definition at line 1582 of file htm.c.

References htm_tree::count, count, htm_tree::entries, HTM_CONTAINS, HTM_EINV, HTM_ENULLPTR, HTM_INSIDE, HTM_INTERSECT, HTM_OK, HTM_RAD_PER_DEG, htm_tree_s2circle_scan(), htm_v3_dist2(), htm_varint_decode(), htm_varint_nfollow(), index, htm_tree::indexfd, htm_tree::leafthresh, htm_tree::root, root, and htm_tree_entry::v.

struct htm_range htm_tree_s2circle_range	(	const struct htm_tree *	tree,
		const struct htm_v3 *	center,
		double	radius,
		enum htm_errcode *	err
	)		`[read]`

Returns a lower and upper bound on the number of points in tree that are inside the spherical circle with the given center and radius.

If an error occurs, the returned range will contain an upper bound below the lower bound, and *err is set to an error code describing the reason for the failure.

Definition at line 1943 of file htm.c.

References HTM_CONTAINS, HTM_EINV, HTM_ENULLPTR, HTM_INSIDE, HTM_INTERSECT, HTM_OK, HTM_RAD_PER_DEG, htm_tree_s2circle_scan(), htm_varint_decode(), htm_varint_nfollow(), htm_range::max, htm_range::min, and root.

int64_t htm_tree_s2circle_scan	(	const struct htm_tree *	tree,
		const struct htm_v3 *	center,
		double	radius,
		enum htm_errcode *	err
	)

Returns the number of points in tree that are inside the spherical circle with the given center and radius.

The implementation scans over all the points in the tree rather than taking advantage of the index. Therefore, this function is primarily useful for testing - application code should use htm_tree_s2circle_count() instead.

If an error occurs, the return value is negative, and *err is set to an error code describing the reason for the failure.

Definition at line 202 of file tree.c.

References htm_tree::count, count, htm_tree::entries, HTM_ENULLPTR, HTM_RAD_PER_DEG, htm_v3_dist2(), and htm_tree_entry::v.

Referenced by htm_tree_s2circle_count(), and htm_tree_s2circle_range().

int64_t htm_tree_s2cpoly_count	(	const struct htm_tree *	tree,
		const struct htm_s2cpoly *	poly,
		enum htm_errcode *	err
	)

Returns the number of points in tree that are inside the given spherical convex polygon.

If an error occurs, the return value is negative, and *err is set to an error code describing the reason for the failure.

Definition at line 1813 of file htm.c.

References count, htm_tree::entries, HTM_CONTAINS, HTM_EINV, HTM_ENOMEM, HTM_ENULLPTR, HTM_INSIDE, HTM_INTERSECT, HTM_OK, htm_s2cpoly_cv3(), htm_tree_s2cpoly_scan(), htm_varint_decode(), htm_varint_nfollow(), index, htm_tree::indexfd, htm_tree::leafthresh, htm_s2cpoly::n, htm_tree::root, root, and htm_tree_entry::v.

struct htm_range htm_tree_s2cpoly_range	(	const struct htm_tree *	tree,
		const struct htm_s2cpoly *	poly,
		enum htm_errcode *	err
	)		`[read]`

Returns a lower and upper bound on the number of points in tree that are inside the given spherical convex polygon.

If an error occurs, the returned range will contain an upper bound below the lower bound, and *err is set to an error code describing the reason for the failure.

Definition at line 2164 of file htm.c.

References HTM_CONTAINS, HTM_EINV, HTM_ENOMEM, HTM_ENULLPTR, HTM_INSIDE, HTM_INTERSECT, HTM_OK, htm_tree_s2cpoly_scan(), htm_varint_decode(), htm_varint_nfollow(), htm_range::max, htm_range::min, htm_s2cpoly::n, and root.

int64_t htm_tree_s2cpoly_scan	(	const struct htm_tree *	tree,
		const struct htm_s2cpoly *	poly,
		enum htm_errcode *	err
	)

Returns the number of points in tree that are inside the given spherical convex polygon.

The implementation scans over all the points in the tree rather than taking advantage of the index. Therefore, this function is primarily useful for testing - application code should use htm_tree_s2cpoly_count() instead.

If an error occurs, the return value is negative, and *err is set to an error code describing the reason for the failure.

Definition at line 257 of file tree.c.

References htm_tree::count, count, htm_tree::entries, HTM_ENULLPTR, htm_s2cpoly_cv3(), and htm_tree_entry::v.

Referenced by htm_tree_s2cpoly_count(), and htm_tree_s2cpoly_range().

int64_t htm_tree_s2ellipse_count	(	const struct htm_tree *	tree,
		const struct htm_s2ellipse *	ellipse,
		enum htm_errcode *	err
	)

Returns the number of points in tree that are inside the given spherical ellipse.

If an error occurs, the return value is negative, and *err is set to an error code describing the reason for the failure.

Definition at line 1703 of file htm.c.

References count, htm_tree::entries, HTM_CONTAINS, HTM_EINV, HTM_ENULLPTR, HTM_INSIDE, HTM_INTERSECT, HTM_OK, htm_s2ellipse_cv3(), htm_tree_s2ellipse_scan(), htm_varint_decode(), htm_varint_nfollow(), index, htm_tree::indexfd, htm_tree::leafthresh, htm_tree::root, root, and htm_tree_entry::v.

struct htm_range htm_tree_s2ellipse_range	(	const struct htm_tree *	tree,
		const struct htm_s2ellipse *	ellipse,
		enum htm_errcode *	err
	)		`[read]`

Returns a lower and upper bound on the number of points in tree that are inside the given spherical ellipse.

If an error occurs, the returned range will contain an upper bound below the lower bound, and *err is set to an error code describing the reason for the failure.

Definition at line 2060 of file htm.c.

References HTM_CONTAINS, HTM_EINV, HTM_ENULLPTR, HTM_INSIDE, HTM_INTERSECT, HTM_OK, htm_tree_s2ellipse_scan(), htm_varint_decode(), htm_varint_nfollow(), htm_range::max, htm_range::min, and root.

int64_t htm_tree_s2ellipse_scan	(	const struct htm_tree *	tree,
		const struct htm_s2ellipse *	ellipse,
		enum htm_errcode *	err
	)

Returns the number of points in tree that are inside the given spherical ellipse.

The implementation scans over all the points in the tree rather than taking advantage of the index. Therefore, this function is primarily useful for testing - application code should use htm_tree_s2ellipse_count() instead.

If an error occurs, the return value is negative, and *err is set to an error code describing the reason for the failure.

Definition at line 234 of file tree.c.

References htm_tree::count, count, htm_tree::entries, HTM_ENULLPTR, htm_s2ellipse_cv3(), and htm_tree_entry::v.

Referenced by htm_tree_s2ellipse_count(), and htm_tree_s2ellipse_range().