// https://github.com/tidwall/tg // // Copyright 2023 Joshua J Baker. All rights reserved. // Use of this source code is governed by a license // that can be found in the LICENSE file. #ifndef TG_H #define TG_H #include #include #include /// The base point type used for all geometries. /// @see PointFuncs struct tg_point { double x; double y; }; /// The base segment type used in tg_line and tg_ring for joining two vertices. /// @see SegmentFuncs struct tg_segment { struct tg_point a; struct tg_point b; }; /// A rectangle defined by a minimum and maximum coordinates. /// Returned by the tg_geom_rect(), tg_ring_rect(), and other \*_rect() /// functions for getting a geometry's minumum bounding rectangle. /// Also used internally for geometry indexing. /// @see RectFuncs struct tg_rect { struct tg_point min; struct tg_point max; }; struct tg_line; ///< Find the description in the tg.c file. struct tg_ring; ///< Find the description in the tg.c file. struct tg_poly; ///< Find the description in the tg.c file. struct tg_geom; ///< Find the description in the tg.c file. /// Geometry types. /// /// All tg_geom are one of the following underlying types. /// /// @see tg_geom_typeof() /// @see tg_geom_type_string() /// @see GeometryAccessors enum tg_geom_type { TG_POINT = 1, ///< Point TG_LINESTRING = 2, ///< LineString TG_POLYGON = 3, ///< Polygon TG_MULTIPOINT = 4, ///< MultiPoint, collection of points TG_MULTILINESTRING = 5, ///< MultiLineString, collection of linestrings TG_MULTIPOLYGON = 6, ///< MultiPolygon, collection of polygons TG_GEOMETRYCOLLECTION = 7, ///< GeometryCollection, collection of geometries }; /// Geometry indexing options. /// /// Used for polygons, rings, and lines to make the point-in-polygon and /// geometry intersection operations fast. /// /// An index can also be used for efficiently traversing, searching, and /// performing nearest-neighbor (kNN) queries on the segment using /// tg_ring_index_*() and tg_ring_nearest() functions. enum tg_index { TG_DEFAULT, ///< default is TG_NATURAL or tg_env_set_default_index(). TG_NONE, ///< no indexing available, or disabled. TG_NATURAL, ///< indexing with natural ring order, for rings/lines TG_YSTRIPES, ///< indexing using segment striping, rings only }; /// @defgroup GeometryConstructors Geometry constructors /// Functions for creating and freeing geometries. /// @{ struct tg_geom *tg_geom_new_point(struct tg_point point); struct tg_geom *tg_geom_new_linestring(const struct tg_line *line); struct tg_geom *tg_geom_new_polygon(const struct tg_poly *poly); struct tg_geom *tg_geom_new_multipoint(const struct tg_point *points, int npoints); struct tg_geom *tg_geom_new_multilinestring(const struct tg_line *const lines[], int nlines); struct tg_geom *tg_geom_new_multipolygon(const struct tg_poly *const polys[], int npolys); struct tg_geom *tg_geom_new_geometrycollection(const struct tg_geom *const geoms[], int ngeoms); struct tg_geom *tg_geom_new_error(const char *errmsg); struct tg_geom *tg_geom_clone(const struct tg_geom *geom); struct tg_geom *tg_geom_copy(const struct tg_geom *geom); void tg_geom_free(struct tg_geom *geom); /// @} /// @defgroup GeometryAccessors Geometry accessors /// Functions for accessing various information about geometries, such as /// getting the geometry type or extracting underlying components or /// coordinates. /// @{ enum tg_geom_type tg_geom_typeof(const struct tg_geom *geom); const char *tg_geom_type_string(enum tg_geom_type type); struct tg_rect tg_geom_rect(const struct tg_geom *geom); bool tg_geom_is_feature(const struct tg_geom *geom); bool tg_geom_is_featurecollection(const struct tg_geom *geom); struct tg_point tg_geom_point(const struct tg_geom *geom); const struct tg_line *tg_geom_line(const struct tg_geom *geom); const struct tg_poly *tg_geom_poly(const struct tg_geom *geom); int tg_geom_num_points(const struct tg_geom *geom); struct tg_point tg_geom_point_at(const struct tg_geom *geom, int index); int tg_geom_num_lines(const struct tg_geom *geom); const struct tg_line *tg_geom_line_at(const struct tg_geom *geom, int index); int tg_geom_num_polys(const struct tg_geom *geom); const struct tg_poly *tg_geom_poly_at(const struct tg_geom *geom, int index); int tg_geom_num_geometries(const struct tg_geom *geom); const struct tg_geom *tg_geom_geometry_at(const struct tg_geom *geom, int index); const char *tg_geom_extra_json(const struct tg_geom *geom); bool tg_geom_is_empty(const struct tg_geom *geom); int tg_geom_dims(const struct tg_geom *geom); bool tg_geom_has_z(const struct tg_geom *geom); bool tg_geom_has_m(const struct tg_geom *geom); double tg_geom_z(const struct tg_geom *geom); double tg_geom_m(const struct tg_geom *geom); const double *tg_geom_extra_coords(const struct tg_geom *geom); int tg_geom_num_extra_coords(const struct tg_geom *geom); size_t tg_geom_memsize(const struct tg_geom *geom); void tg_geom_search(const struct tg_geom *geom, struct tg_rect rect, bool (*iter)(const struct tg_geom *geom, int index, void *udata), void *udata); /// @} /// @defgroup GeometryPredicates Geometry predicates /// Functions for testing the spatial relations of two geometries. /// @{ bool tg_geom_equals(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_intersects(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_disjoint(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_contains(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_within(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_covers(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_coveredby(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_touches(const struct tg_geom *a, const struct tg_geom *b); bool tg_geom_intersects_rect(const struct tg_geom *a, struct tg_rect b); bool tg_geom_intersects_xy(const struct tg_geom *a, double x, double y); /// @} /// @defgroup GeometryParsing Geometry parsing /// Functions for parsing geometries from external data representations. /// It's recommended to use tg_geom_error() after parsing to check for errors. /// @{ struct tg_geom *tg_parse_geojson(const char *geojson); struct tg_geom *tg_parse_geojsonn(const char *geojson, size_t len); struct tg_geom *tg_parse_geojson_ix(const char *geojson, enum tg_index ix); struct tg_geom *tg_parse_geojsonn_ix(const char *geojson, size_t len, enum tg_index ix); struct tg_geom *tg_parse_wkt(const char *wkt); struct tg_geom *tg_parse_wktn(const char *wkt, size_t len); struct tg_geom *tg_parse_wkt_ix(const char *wkt, enum tg_index ix); struct tg_geom *tg_parse_wktn_ix(const char *wkt, size_t len, enum tg_index ix); struct tg_geom *tg_parse_wkb(const uint8_t *wkb, size_t len); struct tg_geom *tg_parse_wkb_ix(const uint8_t *wkb, size_t len, enum tg_index ix); struct tg_geom *tg_parse_hex(const char *hex); struct tg_geom *tg_parse_hexn(const char *hex, size_t len); struct tg_geom *tg_parse_hex_ix(const char *hex, enum tg_index ix); struct tg_geom *tg_parse_hexn_ix(const char *hex, size_t len, enum tg_index ix); struct tg_geom *tg_parse(const void *data, size_t len); struct tg_geom *tg_parse_ix(const void *data, size_t len, enum tg_index ix); const char *tg_geom_error(const struct tg_geom *geom); /// @} /// @defgroup GeometryWriting Geometry writing /// Functions for writing geometries as external data representations. /// @{ size_t tg_geom_geojson(const struct tg_geom *geom, char *dst, size_t n); size_t tg_geom_wkt(const struct tg_geom *geom, char *dst, size_t n); size_t tg_geom_wkb(const struct tg_geom *geom, uint8_t *dst, size_t n); size_t tg_geom_hex(const struct tg_geom *geom, char *dst, size_t n); /// @} /// @defgroup GeometryConstructorsEx Geometry with alternative dimensions /// Functions for working with geometries that have more than two dimensions or /// are empty. The extra dimensional coordinates contained within these /// geometries are only carried along and serve no other purpose than to be /// available for when it's desired to export to an output representation such /// as GeoJSON, WKT, or WKB. /// @{ struct tg_geom *tg_geom_new_point_z(struct tg_point point, double z); struct tg_geom *tg_geom_new_point_m(struct tg_point point, double m); struct tg_geom *tg_geom_new_point_zm(struct tg_point point, double z, double m); struct tg_geom *tg_geom_new_point_empty(void); struct tg_geom *tg_geom_new_linestring_z(const struct tg_line *line, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_linestring_m(const struct tg_line *line, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_linestring_zm(const struct tg_line *line, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_linestring_empty(void); struct tg_geom *tg_geom_new_polygon_z(const struct tg_poly *poly, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_polygon_m(const struct tg_poly *poly, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_polygon_zm(const struct tg_poly *poly, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_polygon_empty(void); struct tg_geom *tg_geom_new_multipoint_z(const struct tg_point *points, int npoints, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multipoint_m(const struct tg_point *points, int npoints, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multipoint_zm(const struct tg_point *points, int npoints, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multipoint_empty(void); struct tg_geom *tg_geom_new_multilinestring_z(const struct tg_line *const lines[], int nlines, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multilinestring_m(const struct tg_line *const lines[], int nlines, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multilinestring_zm(const struct tg_line *const lines[], int nlines, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multilinestring_empty(void); struct tg_geom *tg_geom_new_multipolygon_z(const struct tg_poly *const polys[], int npolys, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multipolygon_m(const struct tg_poly *const polys[], int npolys, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multipolygon_zm(const struct tg_poly *const polys[], int npolys, const double *extra_coords, int ncoords); struct tg_geom *tg_geom_new_multipolygon_empty(void); struct tg_geom *tg_geom_new_geometrycollection_empty(void); /// @} /// @defgroup PointFuncs Point functions /// Functions for working directly with the tg_point type. /// @{ struct tg_rect tg_point_rect(struct tg_point point); bool tg_point_intersects_rect(struct tg_point a, struct tg_rect b); /// @} /// @defgroup SegmentFuncs Segment functions /// Functions for working directly with the tg_segment type. /// @{ struct tg_rect tg_segment_rect(struct tg_segment s); bool tg_segment_intersects_segment(struct tg_segment a, struct tg_segment b); /// @} /// @defgroup RectFuncs Rectangle functions /// Functions for working directly with the tg_rect type. /// @{ struct tg_rect tg_rect_expand(struct tg_rect rect, struct tg_rect other); struct tg_rect tg_rect_expand_point(struct tg_rect rect, struct tg_point point); struct tg_point tg_rect_center(struct tg_rect rect); bool tg_rect_intersects_rect(struct tg_rect a, struct tg_rect b); bool tg_rect_intersects_point(struct tg_rect a, struct tg_point b); /// @} /// @defgroup RingFuncs Ring functions /// Functions for working directly with the tg_ring type. /// /// There are no direct spatial predicates for tg_ring. /// If you want to perform operations like "intersects" or "covers" then you /// must upcast the ring to a tg_geom, like such: /// /// ``` /// tg_geom_intersects((struct tg_geom*)ring, geom); /// ``` /// @{ struct tg_ring *tg_ring_new(const struct tg_point *points, int npoints); struct tg_ring *tg_ring_new_ix(const struct tg_point *points, int npoints, enum tg_index ix); void tg_ring_free(struct tg_ring *ring); struct tg_ring *tg_ring_clone(const struct tg_ring *ring); struct tg_ring *tg_ring_copy(const struct tg_ring *ring); size_t tg_ring_memsize(const struct tg_ring *ring); struct tg_rect tg_ring_rect(const struct tg_ring *ring); int tg_ring_num_points(const struct tg_ring *ring); struct tg_point tg_ring_point_at(const struct tg_ring *ring, int index); const struct tg_point *tg_ring_points(const struct tg_ring *ring); int tg_ring_num_segments(const struct tg_ring *ring); struct tg_segment tg_ring_segment_at(const struct tg_ring *ring, int index); bool tg_ring_convex(const struct tg_ring *ring); bool tg_ring_clockwise(const struct tg_ring *ring); int tg_ring_index_spread(const struct tg_ring *ring); int tg_ring_index_num_levels(const struct tg_ring *ring); int tg_ring_index_level_num_rects(const struct tg_ring *ring, int levelidx); struct tg_rect tg_ring_index_level_rect(const struct tg_ring *ring, int levelidx, int rectidx); bool tg_ring_nearest_segment(const struct tg_ring *ring, double (*rect_dist)(struct tg_rect rect, int *more, void *udata), double (*seg_dist)(struct tg_segment seg, int *more, void *udata), bool (*iter)(struct tg_segment seg, double dist, int index, void *udata), void *udata); void tg_ring_line_search(const struct tg_ring *a, const struct tg_line *b, bool (*iter)(struct tg_segment aseg, int aidx, struct tg_segment bseg, int bidx, void *udata), void *udata); void tg_ring_ring_search(const struct tg_ring *a, const struct tg_ring *b, bool (*iter)(struct tg_segment aseg, int aidx, struct tg_segment bseg, int bidx, void *udata), void *udata); double tg_ring_area(const struct tg_ring *ring); double tg_ring_perimeter(const struct tg_ring *ring); /// @} /// @defgroup LineFuncs Line functions /// Functions for working directly with the tg_line type. /// /// There are no direct spatial predicates for tg_line. /// If you want to perform operations like "intersects" or "covers" then you /// must upcast the line to a tg_geom, like such: /// /// ``` /// tg_geom_intersects((struct tg_geom*)line, geom); /// ``` /// @{ struct tg_line *tg_line_new(const struct tg_point *points, int npoints); struct tg_line *tg_line_new_ix(const struct tg_point *points, int npoints, enum tg_index ix); void tg_line_free(struct tg_line *line); struct tg_line *tg_line_clone(const struct tg_line *line); struct tg_line *tg_line_copy(const struct tg_line *line); size_t tg_line_memsize(const struct tg_line *line); struct tg_rect tg_line_rect(const struct tg_line *line); int tg_line_num_points(const struct tg_line *line); const struct tg_point *tg_line_points(const struct tg_line *line); struct tg_point tg_line_point_at(const struct tg_line *line, int index); int tg_line_num_segments(const struct tg_line *line); struct tg_segment tg_line_segment_at(const struct tg_line *line, int index); bool tg_line_clockwise(const struct tg_line *line); int tg_line_index_spread(const struct tg_line *line); int tg_line_index_num_levels(const struct tg_line *line); int tg_line_index_level_num_rects(const struct tg_line *line, int levelidx); struct tg_rect tg_line_index_level_rect(const struct tg_line *line, int levelidx, int rectidx); bool tg_line_nearest_segment(const struct tg_line *line, double (*rect_dist)(struct tg_rect rect, int *more, void *udata), double (*seg_dist)(struct tg_segment seg, int *more, void *udata), bool (*iter)(struct tg_segment seg, double dist, int index, void *udata), void *udata); void tg_line_line_search(const struct tg_line *a, const struct tg_line *b, bool (*iter)(struct tg_segment aseg, int aidx, struct tg_segment bseg, int bidx, void *udata), void *udata); double tg_line_length(const struct tg_line *line); /// @} /// @defgroup PolyFuncs Polygon functions /// Functions for working directly with the tg_poly type. /// /// There are no direct spatial predicates for tg_poly. /// If you want to perform operations like "intersects" or "covers" then you /// must upcast the poly to a tg_geom, like such: /// /// ``` /// tg_geom_intersects((struct tg_geom*)poly, geom); /// ``` /// @{ struct tg_poly *tg_poly_new(const struct tg_ring *exterior, const struct tg_ring *const holes[], int nholes); void tg_poly_free(struct tg_poly *poly); struct tg_poly *tg_poly_clone(const struct tg_poly *poly); struct tg_poly *tg_poly_copy(const struct tg_poly *poly); size_t tg_poly_memsize(const struct tg_poly *poly); const struct tg_ring *tg_poly_exterior(const struct tg_poly *poly); int tg_poly_num_holes(const struct tg_poly *poly); const struct tg_ring *tg_poly_hole_at(const struct tg_poly *poly, int index); struct tg_rect tg_poly_rect(const struct tg_poly *poly); bool tg_poly_clockwise(const struct tg_poly *poly); /// @} /// @defgroup GlobalFuncs Global environment /// Functions for optionally setting the behavior of the TG environment. /// These, if desired, should be called only once at program start up and prior /// to calling any other tg_*() functions. /// @{ void tg_env_set_allocator(void *(*malloc)(size_t), void *(*realloc)(void*, size_t), void (*free)(void*)); void tg_env_set_index(enum tg_index ix); void tg_env_set_index_spread(int spread); /// @} #endif // TG_H