liblwgeom.h

Go to the documentation of this file.

/**********************************************************************
 *
 * PostGIS - Spatial Types for PostgreSQL
 * http://postgis.net
 *
 * PostGIS is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * PostGIS is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with PostGIS.  If not, see <http://www.gnu.org/licenses/>.
 *
 **********************************************************************
 *
 * Copyright 2011 Sandro Santilli <strk@kbt.io>
 * Copyright 2011 Paul Ramsey <pramsey@cleverelephant.ca>
 * Copyright 2007-2008 Mark Cave-Ayland
 * Copyright 2001-2006 Refractions Research Inc.
 *
 **********************************************************************/


#ifndef _LIBLWGEOM_H
#define _LIBLWGEOM_H 1

#include <stdarg.h>
#include <stdio.h>
#include <stdint.h>
#define ACCEPT_USE_OF_DEPRECATED_PROJ_API_H 1
#include "proj_api.h"

#if defined(PJ_VERSION) && PJ_VERSION >= 490
/* Enable new geodesic functions */
#define PROJ_GEODESIC 1
#else
/* Use the old (pre-2.2) geodesic functions */
#define PROJ_GEODESIC 0
#endif

#define LIBLWGEOM_VERSION "2.4.9dev"
#define LIBLWGEOM_VERSION_MAJOR "2"
#define LIBLWGEOM_VERSION_MINOR "4"
#define LIBLWGEOM_GEOS_VERSION "37"

const char* lwgeom_version(void);

#define LW_TRUE 1
#define LW_FALSE 0
#define LW_UNKNOWN 2
#define LW_FAILURE 0
#define LW_SUCCESS 1

#define POINTTYPE                1
#define LINETYPE                 2
#define POLYGONTYPE              3
#define MULTIPOINTTYPE           4
#define MULTILINETYPE            5
#define MULTIPOLYGONTYPE         6
#define COLLECTIONTYPE           7
#define CIRCSTRINGTYPE           8
#define COMPOUNDTYPE             9
#define CURVEPOLYTYPE           10
#define MULTICURVETYPE          11
#define MULTISURFACETYPE        12
#define POLYHEDRALSURFACETYPE   13
#define TRIANGLETYPE            14
#define TINTYPE                 15

#define NUMTYPES                16

#define WKBZOFFSET  0x80000000
#define WKBMOFFSET  0x40000000
#define WKBSRIDFLAG 0x20000000
#define WKBBBOXFLAG 0x10000000

typedef enum LWORD_T {
  LWORD_X = 0,
  LWORD_Y = 1,
  LWORD_Z = 2,
  LWORD_M = 3
} LWORD;

/**********************************************************************
** Spherical radius.
** Moritz, H. (1980). Geodetic Reference System 1980, by resolution of
** the XVII General Assembly of the IUGG in Canberra.
** http://en.wikipedia.org/wiki/Earth_radius
** http://en.wikipedia.org/wiki/World_Geodetic_System
*/

#define WGS84_MAJOR_AXIS 6378137.0
#define WGS84_INVERSE_FLATTENING 298.257223563
#define WGS84_MINOR_AXIS (WGS84_MAJOR_AXIS - WGS84_MAJOR_AXIS / WGS84_INVERSE_FLATTENING)
#define WGS84_RADIUS ((2.0 * WGS84_MAJOR_AXIS + WGS84_MINOR_AXIS ) / 3.0)


#define FLAGS_GET_Z(flags) ((flags) & 0x01)
#define FLAGS_GET_M(flags) (((flags) & 0x02)>>1)
#define FLAGS_GET_BBOX(flags) (((flags) & 0x04)>>2)
#define FLAGS_GET_GEODETIC(flags) (((flags) & 0x08)>>3)
#define FLAGS_GET_READONLY(flags) (((flags) & 0x10)>>4)
#define FLAGS_GET_SOLID(flags) (((flags) & 0x20)>>5)
#define FLAGS_SET_Z(flags, value) ((flags) = (value) ? ((flags) | 0x01) : ((flags) & 0xFE))
#define FLAGS_SET_M(flags, value) ((flags) = (value) ? ((flags) | 0x02) : ((flags) & 0xFD))
#define FLAGS_SET_BBOX(flags, value) ((flags) = (value) ? ((flags) | 0x04) : ((flags) & 0xFB))
#define FLAGS_SET_GEODETIC(flags, value) ((flags) = (value) ? ((flags) | 0x08) : ((flags) & 0xF7))
#define FLAGS_SET_READONLY(flags, value) ((flags) = (value) ? ((flags) | 0x10) : ((flags) & 0xEF))
#define FLAGS_SET_SOLID(flags, value) ((flags) = (value) ? ((flags) | 0x20) : ((flags) & 0xDF))
#define FLAGS_NDIMS(flags) (2 + FLAGS_GET_Z(flags) + FLAGS_GET_M(flags))
#define FLAGS_GET_ZM(flags) (FLAGS_GET_M(flags) + FLAGS_GET_Z(flags) * 2)
#define FLAGS_NDIMS_BOX(flags) (FLAGS_GET_GEODETIC(flags) ? 3 : FLAGS_NDIMS(flags))

#define TYPMOD_GET_SRID(typmod) ((((typmod) & 0x0FFFFF00) - ((typmod) & 0x10000000)) >> 8)
#define TYPMOD_SET_SRID(typmod, srid) ((typmod) = (((typmod) & 0xE00000FF) | ((srid & 0x001FFFFF)<<8)))
#define TYPMOD_GET_TYPE(typmod) ((typmod & 0x000000FC)>>2)
#define TYPMOD_SET_TYPE(typmod, type) ((typmod) = (typmod & 0xFFFFFF03) | ((type & 0x0000003F)<<2))
#define TYPMOD_GET_Z(typmod) ((typmod & 0x00000002)>>1)
#define TYPMOD_SET_Z(typmod) ((typmod) = typmod | 0x00000002)
#define TYPMOD_GET_M(typmod) (typmod & 0x00000001)
#define TYPMOD_SET_M(typmod) ((typmod) = typmod | 0x00000001)
#define TYPMOD_GET_NDIMS(typmod) (2+TYPMOD_GET_Z(typmod)+TYPMOD_GET_M(typmod))

#define SRID_MAXIMUM 999999

#define SRID_USER_MAXIMUM 998999

#define SRID_UNKNOWN 0
#define SRID_IS_UNKNOWN(x) ((int)x<=0)

/*
** EPSG WGS84 geographics, OGC standard default SRS, better be in
** the SPATIAL_REF_SYS table!
*/
#define SRID_DEFAULT 4326

#ifndef __GNUC__
# define __attribute__(x)
#endif

extern int clamp_srid(int srid);

/* Raise an lwerror if srids do not match */
void error_if_srid_mismatch(int srid1, int srid2);

typedef void* (*lwallocator)(size_t size);
typedef void* (*lwreallocator)(void *mem, size_t size);
typedef void (*lwfreeor)(void* mem);
typedef void (*lwreporter)(const char* fmt, va_list ap)
  __attribute__ (( format(printf, 1, 0) ));
typedef void (*lwdebuglogger)(int level, const char* fmt, va_list ap)
  __attribute__ (( format(printf, 2,0) ));

extern void lwgeom_set_handlers(lwallocator allocator,
        lwreallocator reallocator, lwfreeor freeor, lwreporter errorreporter,
        lwreporter noticereporter);

extern void lwgeom_set_debuglogger(lwdebuglogger debuglogger);

extern void lwgeom_request_interrupt(void);

extern void lwgeom_cancel_interrupt(void);

typedef void (lwinterrupt_callback)();
extern lwinterrupt_callback *lwgeom_register_interrupt_callback(lwinterrupt_callback *);

/******************************************************************/

typedef struct {
        double afac, bfac, cfac, dfac, efac, ffac, gfac, hfac, ifac, xoff, yoff, zoff;
} AFFINE;

/******************************************************************/

typedef struct
{
        double xmin, ymin, zmin;
        double xmax, ymax, zmax;
        int32_t srid;
}
BOX3D;

/******************************************************************
* GBOX structure.
* We include the flags (information about dimensinality),
* so we don't have to constantly pass them
* into functions that use the GBOX.
*/
typedef struct
{
        uint8_t flags;
        double xmin;
        double xmax;
        double ymin;
        double ymax;
        double zmin;
        double zmax;
        double mmin;
        double mmax;
} GBOX;


/******************************************************************
* SPHEROID
*
*  Standard definition of an ellipsoid (what wkt calls a spheroid)
*    f = (a-b)/a
*    e_sq = (a*a - b*b)/(a*a)
*    b = a - fa
*/
typedef struct
{
        double  a;      /* semimajor axis */
        double  b;      /* semiminor axis b = (a - fa) */
        double  f;      /* flattening f = (a-b)/a */
        double  e;      /* eccentricity (first) */
        double  e_sq;   /* eccentricity squared (first) e_sq = (a*a-b*b)/(a*a) */
        double  radius;  /* spherical average radius = (2*a+b)/3 */
        char    name[20];  /* name of ellipse */
}
SPHEROID;

/******************************************************************
* POINT2D, POINT3D, POINT3DM, POINT4D
*/
typedef struct
{
        double x, y;
}
POINT2D;

typedef struct
{
        double x, y, z;
}
POINT3DZ;

typedef struct
{
        double x, y, z;
}
POINT3D;

typedef struct
{
        double x, y, m;
}
POINT3DM;

typedef struct
{
        double x, y, z, m;
}
POINT4D;

/******************************************************************
*  POINTARRAY
*  Point array abstracts a lot of the complexity of points and point lists.
*  It handles 2d/3d translation
*    (2d points converted to 3d will have z=0 or NaN)
*  DO NOT MIX 2D and 3D POINTS! EVERYTHING* is either one or the other
*/
typedef struct
{
        /* Array of POINT 2D, 3D or 4D, possibly missaligned. */
        uint8_t *serialized_pointlist;

        /* Use FLAGS_* macros to handle */
        uint8_t  flags;

        int npoints;   /* how many points we are currently storing */
        int maxpoints; /* how many points we have space for in serialized_pointlist */
}
POINTARRAY;

/******************************************************************
* GSERIALIZED
*/
typedef struct
{
        uint32_t size; /* For PgSQL use only, use VAR* macros to manipulate. */
        uint8_t srid[3]; /* 24 bits of SRID */
        uint8_t flags; /* HasZ, HasM, HasBBox, IsGeodetic, IsReadOnly */
        uint8_t data[1]; /* See gserialized.txt */
} GSERIALIZED;


/******************************************************************
* LWGEOM (any geometry type)
*
* Abstract type, note that 'type', 'bbox' and 'srid' are available in
* all geometry variants.
*/
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        void *data;
}
LWGEOM;

/* POINTYPE */
typedef struct
{
        uint8_t type; /* POINTTYPE */
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        POINTARRAY *point;  /* hide 2d/3d (this will be an array of 1 point) */
}
LWPOINT; /* "light-weight point" */

/* LINETYPE */
typedef struct
{
        uint8_t type; /* LINETYPE */
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        POINTARRAY *points; /* array of POINT3D */
}
LWLINE; /* "light-weight line" */

/* TRIANGLE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        POINTARRAY *points;
}
LWTRIANGLE;

/* CIRCSTRINGTYPE */
typedef struct
{
        uint8_t type; /* CIRCSTRINGTYPE */
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        POINTARRAY *points; /* array of POINT(3D/3DM) */
}
LWCIRCSTRING; /* "light-weight circularstring" */

/* POLYGONTYPE */
typedef struct
{
        uint8_t type; /* POLYGONTYPE */
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int nrings;   /* how many rings we are currently storing */
        int maxrings; /* how many rings we have space for in **rings */
        POINTARRAY **rings; /* list of rings (list of points) */
}
LWPOLY; /* "light-weight polygon" */

/* MULTIPOINTTYPE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWPOINT **geoms;
}
LWMPOINT;

/* MULTILINETYPE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWLINE **geoms;
}
LWMLINE;

/* MULTIPOLYGONTYPE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWPOLY **geoms;
}
LWMPOLY;

/* COLLECTIONTYPE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWGEOM **geoms;
}
LWCOLLECTION;

/* COMPOUNDTYPE */
typedef struct
{
        uint8_t type; /* COMPOUNDTYPE */
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWGEOM **geoms;
}
LWCOMPOUND; /* "light-weight compound line" */

/* CURVEPOLYTYPE */
typedef struct
{
        uint8_t type; /* CURVEPOLYTYPE */
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int nrings;    /* how many rings we are currently storing */
        int maxrings;  /* how many rings we have space for in **rings */
        LWGEOM **rings; /* list of rings (list of points) */
}
LWCURVEPOLY; /* "light-weight polygon" */

/* MULTICURVE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWGEOM **geoms;
}
LWMCURVE;

/* MULTISURFACETYPE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWGEOM **geoms;
}
LWMSURFACE;

/* POLYHEDRALSURFACETYPE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWPOLY **geoms;
}
LWPSURFACE;

/* TINTYPE */
typedef struct
{
        uint8_t type;
        uint8_t flags;
        GBOX *bbox;
        int32_t srid;
        int ngeoms;   /* how many geometries we are currently storing */
        int maxgeoms; /* how many geometries we have space for in **geoms */
        LWTRIANGLE **geoms;
}
LWTIN;

/* Casts LWGEOM->LW* (return NULL if cast is illegal) */
extern LWMPOLY *lwgeom_as_lwmpoly(const LWGEOM *lwgeom);
extern LWMLINE *lwgeom_as_lwmline(const LWGEOM *lwgeom);
extern LWMPOINT *lwgeom_as_lwmpoint(const LWGEOM *lwgeom);
extern LWCOLLECTION *lwgeom_as_lwcollection(const LWGEOM *lwgeom);
extern LWPOLY *lwgeom_as_lwpoly(const LWGEOM *lwgeom);
extern LWLINE *lwgeom_as_lwline(const LWGEOM *lwgeom);
extern LWPOINT *lwgeom_as_lwpoint(const LWGEOM *lwgeom);
extern LWCIRCSTRING *lwgeom_as_lwcircstring(const LWGEOM *lwgeom);
extern LWCURVEPOLY *lwgeom_as_lwcurvepoly(const LWGEOM *lwgeom);
extern LWCOMPOUND *lwgeom_as_lwcompound(const LWGEOM *lwgeom);
extern LWPSURFACE *lwgeom_as_lwpsurface(const LWGEOM *lwgeom);
extern LWTRIANGLE *lwgeom_as_lwtriangle(const LWGEOM *lwgeom);
extern LWTIN *lwgeom_as_lwtin(const LWGEOM *lwgeom);
extern LWGEOM *lwgeom_as_multi(const LWGEOM *lwgeom);
extern LWGEOM *lwgeom_as_curve(const LWGEOM *lwgeom);

/* Casts LW*->LWGEOM (always cast) */
extern LWGEOM *lwtin_as_lwgeom(const LWTIN *obj);
extern LWGEOM *lwtriangle_as_lwgeom(const LWTRIANGLE *obj);
extern LWGEOM *lwpsurface_as_lwgeom(const LWPSURFACE *obj);
extern LWGEOM *lwmpoly_as_lwgeom(const LWMPOLY *obj);
extern LWGEOM *lwmline_as_lwgeom(const LWMLINE *obj);
extern LWGEOM *lwmpoint_as_lwgeom(const LWMPOINT *obj);
extern LWGEOM *lwcollection_as_lwgeom(const LWCOLLECTION *obj);
extern LWGEOM *lwcircstring_as_lwgeom(const LWCIRCSTRING *obj);
extern LWGEOM *lwcompound_as_lwgeom(const LWCOMPOUND *obj);
extern LWGEOM *lwcurvepoly_as_lwgeom(const LWCURVEPOLY *obj);
extern LWGEOM *lwpoly_as_lwgeom(const LWPOLY *obj);
extern LWGEOM *lwline_as_lwgeom(const LWLINE *obj);
extern LWGEOM *lwpoint_as_lwgeom(const LWPOINT *obj);


extern LWCOLLECTION* lwcollection_add_lwgeom(LWCOLLECTION *col, const LWGEOM *geom);
extern LWMPOINT* lwmpoint_add_lwpoint(LWMPOINT *mobj, const LWPOINT *obj);
extern LWMLINE* lwmline_add_lwline(LWMLINE *mobj, const LWLINE *obj);
extern LWMPOLY* lwmpoly_add_lwpoly(LWMPOLY *mobj, const LWPOLY *obj);
extern LWPSURFACE* lwpsurface_add_lwpoly(LWPSURFACE *mobj, const LWPOLY *obj);
extern LWTIN* lwtin_add_lwtriangle(LWTIN *mobj, const LWTRIANGLE *obj);



/***********************************************************************
** Utility functions for flag byte and srid_flag integer.
*/

extern uint8_t gflags(int hasz, int hasm, int geodetic);

extern uint32_t gserialized_get_type(const GSERIALIZED *g);

extern uint32_t gserialized_max_header_size(void);

extern uint32_t gserialized_header_size(const GSERIALIZED *gser);

extern int32_t gserialized_get_srid(const GSERIALIZED *g);

extern void gserialized_set_srid(GSERIALIZED *g, int32_t srid);

extern int gserialized_is_empty(const GSERIALIZED *g);

extern int gserialized_has_bbox(const GSERIALIZED *gser);

extern int gserialized_has_z(const GSERIALIZED *gser);

extern int gserialized_has_m(const GSERIALIZED *gser);

extern int gserialized_is_geodetic(const GSERIALIZED *gser);

extern int gserialized_get_zm(const GSERIALIZED *gser);

extern int gserialized_ndims(const GSERIALIZED *gser);

extern int gserialized_cmp(const GSERIALIZED *g1, const GSERIALIZED *g2);

extern void lwgeom_drop_bbox(LWGEOM *lwgeom);
extern void lwgeom_drop_srid(LWGEOM *lwgeom);

extern void lwgeom_add_bbox(LWGEOM *lwgeom);
extern void lwgeom_add_bbox_deep(LWGEOM *lwgeom, GBOX *gbox);

extern const GBOX *lwgeom_get_bbox(const LWGEOM *lwgeom);

extern int lwgeom_is_collection(const LWGEOM *lwgeom);

/******************************************************************/
/* Functions that work on type numbers */

extern int lwtype_is_collection(uint8_t type);

extern int lwtype_get_collectiontype(uint8_t type);

extern const char *lwtype_name(uint8_t type);


/******************************************************************/

/*
 * copies a point from the point array into the parameter point
 * will set point's z=0 (or NaN) if pa is 2d
 * will set point's m=0 (or NaN) if pa is 3d or 2d
 * NOTE: point is a real POINT3D *not* a pointer
 */
extern POINT4D getPoint4d(const POINTARRAY *pa, int n);

/*
 * copies a point from the point array into the parameter point
 * will set point's z=0 (or NaN) if pa is 2d
 * will set point's m=0 (or NaN) if pa is 3d or 2d
 * NOTE: this will modify the point4d pointed to by 'point'.
 */
extern int getPoint4d_p(const POINTARRAY *pa, int n, POINT4D *point);

/*
 * copies a point from the point array into the parameter point
 * will set point's z=0 (or NaN) if pa is 2d
 * NOTE: point is a real POINT3D *not* a pointer
 */
extern POINT3DZ getPoint3dz(const POINTARRAY *pa, int n);
extern POINT3DM getPoint3dm(const POINTARRAY *pa, int n);

/*
 * copies a point from the point array into the parameter point
 * will set point's z=0 (or NaN) if pa is 2d
 * NOTE: this will modify the point3d pointed to by 'point'.
 */
extern int getPoint3dz_p(const POINTARRAY *pa, int n, POINT3DZ *point);
extern int getPoint3dm_p(const POINTARRAY *pa, int n, POINT3DM *point);


/*
 * copies a point from the point array into the parameter point
 * z value (if present is not returned)
 * NOTE: point is a real POINT3D *not* a pointer
 */
extern POINT2D getPoint2d(const POINTARRAY *pa, int n);

/*
 * copies a point from the point array into the parameter point
 * z value (if present is not returned)
 * NOTE: this will modify the point2d pointed to by 'point'.
 */
extern int getPoint2d_p(const POINTARRAY *pa, int n, POINT2D *point);

extern const POINT2D* getPoint2d_cp(const POINTARRAY *pa, int n);

extern const POINT3DZ* getPoint3dz_cp(const POINTARRAY *pa, int n);

extern const POINT4D* getPoint4d_cp(const POINTARRAY *pa, int n);

/*
 * set point N to the given value
 * NOTE that the pointarray can be of any
 * dimension, the appropriate ordinate values
 * will be extracted from it
 *
 * N must be a valid point index
 */
extern void ptarray_set_point4d(POINTARRAY *pa, int n, const POINT4D *p4d);

/*
 * get a pointer to nth point of a POINTARRAY
 * You'll need to cast it to appropriate dimensioned point.
 * Note that if you cast to a higher dimensional point you'll
 * possibly corrupt the POINTARRAY.
 *
 * WARNING: Don't cast this to a POINT !
 * it would not be reliable due to memory alignment constraints
 */
extern uint8_t *getPoint_internal(const POINTARRAY *pa, int n);

/*
 * size of point represeneted in the POINTARRAY
 * 16 for 2d, 24 for 3d, 32 for 4d
 */
extern int ptarray_point_size(const POINTARRAY *pa);


extern POINTARRAY* ptarray_construct(char hasz, char hasm, uint32_t npoints);

extern POINTARRAY* ptarray_construct_copy_data(char hasz, char hasm, uint32_t npoints, const uint8_t *ptlist);

extern POINTARRAY* ptarray_construct_reference_data(char hasz, char hasm, uint32_t npoints, uint8_t *ptlist);

extern POINTARRAY* ptarray_construct_empty(char hasz, char hasm, uint32_t maxpoints);

extern int ptarray_append_point(POINTARRAY *pa, const POINT4D *pt, int allow_duplicates);

extern int ptarray_append_ptarray(POINTARRAY *pa1, POINTARRAY *pa2, double gap_tolerance);

extern int ptarray_insert_point(POINTARRAY *pa, const POINT4D *p, int where);

extern int ptarray_remove_point(POINTARRAY *pa, int where);

extern POINTARRAY *ptarray_addPoint(const POINTARRAY *pa, uint8_t *p, size_t pdims, uint32_t where);

extern POINTARRAY *ptarray_removePoint(POINTARRAY *pa, uint32_t where);

extern POINTARRAY *ptarray_merge(POINTARRAY *pa1, POINTARRAY *pa2);

extern int ptarray_is_closed(const POINTARRAY *pa);
extern int ptarray_is_closed_2d(const POINTARRAY *pa);
extern int ptarray_is_closed_3d(const POINTARRAY *pa);
extern int ptarray_is_closed_z(const POINTARRAY *pa);
extern void ptarray_longitude_shift(POINTARRAY *pa);
extern int ptarray_isccw(const POINTARRAY *pa);
extern void ptarray_reverse(POINTARRAY *pa);
extern POINTARRAY* ptarray_flip_coordinates(POINTARRAY *pa);

extern POINTARRAY *ptarray_substring(POINTARRAY *pa, double d1, double d2,
                                                          double tolerance);


extern LWGEOM* lwgeom_force_2d(const LWGEOM *geom);
extern LWGEOM* lwgeom_force_3dz(const LWGEOM *geom);
extern LWGEOM* lwgeom_force_3dm(const LWGEOM *geom);
extern LWGEOM* lwgeom_force_4d(const LWGEOM *geom);

extern LWGEOM* lwgeom_simplify(const LWGEOM *igeom, double dist, int preserve_collapsed);
extern LWGEOM* lwgeom_set_effective_area(const LWGEOM *igeom, int set_area, double area);

/*
 * Force to use SFS 1.1 geometry type
 * (rather than SFS 1.2 and/or SQL/MM)
 */
extern LWGEOM* lwgeom_force_sfs(LWGEOM *geom, int version);


/*--------------------------------------------------------
 * all the base types (point/line/polygon) will have a
 * basic constructor, basic de-serializer, basic serializer,
 * bounding box finder and (TODO) serialized form size finder.
 *--------------------------------------------------------*/

/*
 * convenience functions to hide the POINTARRAY
 */
extern int lwpoint_getPoint2d_p(const LWPOINT *point, POINT2D *out);
extern int lwpoint_getPoint3dz_p(const LWPOINT *point, POINT3DZ *out);
extern int lwpoint_getPoint3dm_p(const LWPOINT *point, POINT3DM *out);
extern int lwpoint_getPoint4d_p(const LWPOINT *point, POINT4D *out);

/******************************************************************
 * LWLINE functions
 ******************************************************************/

extern int lwline_add_lwpoint(LWLINE *line, LWPOINT *point, int where);

/******************************************************************
 * LWPOLY functions
 ******************************************************************/

extern int lwpoly_add_ring(LWPOLY *poly, POINTARRAY *pa);

extern int lwcurvepoly_add_ring(LWCURVEPOLY *poly, LWGEOM *ring);

extern int lwcompound_add_lwgeom(LWCOMPOUND *comp, LWGEOM *geom);

extern LWCOMPOUND* lwcompound_construct_from_lwline(const LWLINE *lwpoly);

extern LWCURVEPOLY* lwcurvepoly_construct_from_lwpoly(LWPOLY *lwpoly);


/******************************************************************
 * LWGEOM functions
 ******************************************************************/

extern int lwcollection_ngeoms(const LWCOLLECTION *col);

/* Given a generic geometry/collection, return the "simplest" form.
 * The elements of the homogenized collection are references to the
 * input geometry; a deep clone is not performed.
 * TODO: consider returning a geometry that does not reference the
 * input
 * */
extern LWGEOM *lwgeom_homogenize(const LWGEOM *geom);


/******************************************************************
 * LWMULTIx and LWCOLLECTION functions
 ******************************************************************/

LWGEOM *lwcollection_getsubgeom(LWCOLLECTION *col, int gnum);

/* WARNING: the output will contain references to geometries in the input, */
/* so the result must be carefully released, not freed. */
LWCOLLECTION* lwcollection_extract(LWCOLLECTION *col, int type);


/******************************************************************
 * SERIALIZED FORM functions
 ******************************************************************/

extern void lwgeom_set_srid(LWGEOM *geom, int srid);

/*------------------------------------------------------
 * other stuff
 *
 * handle the double-to-float conversion.  The results of this
 * will usually be a slightly bigger box because of the difference
 * between float8 and float4 representations.
 */

extern BOX3D* box3d_from_gbox(const GBOX *gbox);
extern GBOX* box3d_to_gbox(const BOX3D *b3d);

void expand_box3d(BOX3D *box, double d);


/****************************************************************
 * MEMORY MANAGEMENT
 ****************************************************************/

/*
* The *_free family of functions frees *all* memory associated
* with the pointer. When the recursion gets to the level of the
* POINTARRAY, the POINTARRAY is only freed if it is not flagged
* as "read only". LWGEOMs constructed on top of GSERIALIZED
* from PgSQL use read only point arrays.
*/

extern void ptarray_free(POINTARRAY *pa);
extern void lwpoint_free(LWPOINT *pt);
extern void lwline_free(LWLINE *line);
extern void lwpoly_free(LWPOLY *poly);
extern void lwtriangle_free(LWTRIANGLE *triangle);
extern void lwmpoint_free(LWMPOINT *mpt);
extern void lwmline_free(LWMLINE *mline);
extern void lwmpoly_free(LWMPOLY *mpoly);
extern void lwpsurface_free(LWPSURFACE *psurf);
extern void lwtin_free(LWTIN *tin);
extern void lwcollection_free(LWCOLLECTION *col);
extern void lwcircstring_free(LWCIRCSTRING *curve);
extern void lwgeom_free(LWGEOM *geom);

/*
* The *_release family of functions frees the LWGEOM structures
* surrounding the POINTARRAYs but leaves the POINTARRAYs
* intact. Useful when re-shaping geometries between types,
* or splicing geometries together.
*/

extern void lwpoint_release(LWPOINT *lwpoint);
extern void lwline_release(LWLINE *lwline);
extern void lwpoly_release(LWPOLY *lwpoly);
extern void lwtriangle_release(LWTRIANGLE *lwtriangle);
extern void lwcircstring_release(LWCIRCSTRING *lwcirc);
extern void lwmpoint_release(LWMPOINT *lwpoint);
extern void lwmline_release(LWMLINE *lwline);
extern void lwmpoly_release(LWMPOLY *lwpoly);
extern void lwpsurface_release(LWPSURFACE *lwpsurface);
extern void lwtin_release(LWTIN *lwtin);
extern void lwcollection_release(LWCOLLECTION *lwcollection);
extern void lwgeom_release(LWGEOM *lwgeom);


/****************************************************************
* Utility
****************************************************************/

extern void printBOX3D(BOX3D *b);
extern void printPA(POINTARRAY *pa);
extern void printLWPOINT(LWPOINT *point);
extern void printLWLINE(LWLINE *line);
extern void printLWPOLY(LWPOLY *poly);
extern void printLWTRIANGLE(LWTRIANGLE *triangle);
extern void printLWPSURFACE(LWPSURFACE *psurf);
extern void printLWTIN(LWTIN *tin);

extern float  next_float_down(double d);
extern float  next_float_up(double d);

/* general utilities 2D */
extern double  distance2d_pt_pt(const POINT2D *p1, const POINT2D *p2);
extern double  distance2d_sqr_pt_pt(const POINT2D *p1, const POINT2D *p2);
extern double  distance2d_pt_seg(const POINT2D *p, const POINT2D *A, const POINT2D *B);
extern double  distance2d_sqr_pt_seg(const POINT2D *p, const POINT2D *A, const POINT2D *B);
extern LWGEOM* lwgeom_closest_line(const LWGEOM *lw1, const LWGEOM *lw2);
extern LWGEOM* lwgeom_furthest_line(const LWGEOM *lw1, const LWGEOM *lw2);
extern LWGEOM* lwgeom_closest_point(const LWGEOM *lw1, const LWGEOM *lw2);
extern LWGEOM* lwgeom_furthest_point(const LWGEOM *lw1, const LWGEOM *lw2);
extern double  lwgeom_mindistance2d(const LWGEOM *lw1, const LWGEOM *lw2);
extern double  lwgeom_mindistance2d_tolerance(const LWGEOM *lw1, const LWGEOM *lw2, double tolerance);
extern double  lwgeom_maxdistance2d(const LWGEOM *lw1, const LWGEOM *lw2);
extern double  lwgeom_maxdistance2d_tolerance(const LWGEOM *lw1, const LWGEOM *lw2, double tolerance);

/* 3D */
extern double distance3d_pt_pt(const POINT3D *p1, const POINT3D *p2);
extern double distance3d_pt_seg(const POINT3D *p, const POINT3D *A, const POINT3D *B);

extern LWGEOM* lwgeom_furthest_line_3d(LWGEOM *lw1, LWGEOM *lw2);
extern LWGEOM* lwgeom_closest_line_3d(const LWGEOM *lw1, const LWGEOM *lw2);
extern LWGEOM* lwgeom_closest_point_3d(const LWGEOM *lw1, const LWGEOM *lw2);


extern double lwgeom_mindistance3d(const LWGEOM *lw1, const LWGEOM *lw2);
extern double lwgeom_mindistance3d_tolerance(const LWGEOM *lw1, const LWGEOM *lw2, double tolerance);
extern double lwgeom_maxdistance3d(const LWGEOM *lw1, const LWGEOM *lw2);
extern double lwgeom_maxdistance3d_tolerance(const LWGEOM *lw1, const LWGEOM *lw2, double tolerance);

extern double lwgeom_area(const LWGEOM *geom);
extern double lwgeom_length(const LWGEOM *geom);
extern double lwgeom_length_2d(const LWGEOM *geom);
extern double lwgeom_perimeter(const LWGEOM *geom);
extern double lwgeom_perimeter_2d(const LWGEOM *geom);
extern void lwgeom_affine(LWGEOM *geom, const AFFINE *affine);
extern void lwgeom_scale(LWGEOM *geom, const POINT4D *factors);
extern int lwgeom_dimension(const LWGEOM *geom);

extern LWPOINT* lwline_get_lwpoint(const LWLINE *line, int where);
extern LWPOINT* lwcircstring_get_lwpoint(const LWCIRCSTRING *circ, int where);

extern LWPOINT* lwcompound_get_startpoint(const LWCOMPOUND *lwcmp);
extern LWPOINT* lwcompound_get_endpoint(const LWCOMPOUND *lwcmp);
extern LWPOINT* lwcompound_get_lwpoint(const LWCOMPOUND *lwcmp, int where);


extern double ptarray_length_2d(const POINTARRAY *pts);
extern double ptarray_length(const POINTARRAY *pts);
extern double ptarray_arc_length_2d(const POINTARRAY *pts);


extern int pt_in_ring_2d(const POINT2D *p, const POINTARRAY *ring);
extern int azimuth_pt_pt(const POINT2D *p1, const POINT2D *p2, double *ret);
extern int lwpoint_inside_circle(const LWPOINT *p, double cx, double cy, double rad);
extern void lwgeom_reverse(LWGEOM *lwgeom);
extern void lwline_reverse(LWLINE *line);
extern void lwpoly_reverse(LWPOLY *poly);
extern void lwtriangle_reverse(LWTRIANGLE *triangle);
extern char* lwgeom_summary(const LWGEOM *lwgeom, int offset);
extern char* lwpoint_to_latlon(const LWPOINT *p, const char *format);
extern int lwgeom_startpoint(const LWGEOM* lwgeom, POINT4D* pt);

extern void lwgeom_force_clockwise(LWGEOM *lwgeom);
extern void lwpoly_force_clockwise(LWPOLY *poly);
extern void lwtriangle_force_clockwise(LWTRIANGLE *triangle);

extern int lwgeom_is_clockwise(LWGEOM *lwgeom);
extern int lwpoly_is_clockwise(LWPOLY *poly);
extern int lwtriangle_is_clockwise(LWTRIANGLE *triangle);

extern void interpolate_point4d(POINT4D *A, POINT4D *B, POINT4D *I, double F);

void lwgeom_longitude_shift(LWGEOM *lwgeom);

LWGEOM *lwgeom_wrapx(const LWGEOM *lwgeom, double cutx, double amount);


extern int lwgeom_needs_bbox(const LWGEOM *geom);

extern int lwgeom_count_vertices(const LWGEOM *geom);

extern int lwgeom_count_rings(const LWGEOM *geom);

extern int lwgeom_has_srid(const LWGEOM *geom);

extern int lwgeom_is_empty(const LWGEOM *geom);

extern int lwgeom_is_closed(const LWGEOM *geom);

extern int lwgeom_dimensionality(LWGEOM *geom);

/* Is lwgeom1 geometrically equal to lwgeom2 ? */
char lwgeom_same(const LWGEOM *lwgeom1, const LWGEOM *lwgeom2);
char ptarray_same(const POINTARRAY *pa1, const POINTARRAY *pa2);
char lwpoint_same(const LWPOINT *p1, const LWPOINT *p2);
char lwline_same(const LWLINE *p1, const LWLINE *p2);
char lwpoly_same(const LWPOLY *p1, const LWPOLY *p2);
char lwtriangle_same(const LWTRIANGLE *p1, const LWTRIANGLE *p2);
char lwcollection_same(const LWCOLLECTION *p1, const LWCOLLECTION *p2);
char lwcircstring_same(const LWCIRCSTRING *p1, const LWCIRCSTRING *p2);


extern LWGEOM *lwgeom_clone(const LWGEOM *lwgeom);

extern LWGEOM *lwgeom_clone_deep(const LWGEOM *lwgeom);

/* TODO Move to Internal */
LWPOINT *lwpoint_clone(const LWPOINT *lwgeom);
POINTARRAY *ptarray_clone_deep(const POINTARRAY *ptarray);


/*
* Geometry constructors. These constructors to not copy the point arrays
* passed to them, they just take references, so do not free them out
* from underneath the geometries.
*/
extern LWPOINT* lwpoint_construct(int srid, GBOX *bbox, POINTARRAY *point);
extern LWMPOINT *lwmpoint_construct(int srid, const POINTARRAY *pa);
extern LWLINE* lwline_construct(int srid, GBOX *bbox, POINTARRAY *points);
extern LWCIRCSTRING* lwcircstring_construct(int srid, GBOX *bbox, POINTARRAY *points);
extern LWPOLY* lwpoly_construct(int srid, GBOX *bbox, uint32_t nrings, POINTARRAY **points);
extern LWCURVEPOLY* lwcurvepoly_construct(int srid, GBOX *bbox, uint32_t nrings, LWGEOM **geoms);
extern LWTRIANGLE* lwtriangle_construct(int srid, GBOX *bbox, POINTARRAY *points);
extern LWCOLLECTION* lwcollection_construct(uint8_t type, int srid, GBOX *bbox, uint32_t ngeoms, LWGEOM **geoms);
/*
* Empty geometry constructors.
*/
extern LWGEOM* lwgeom_construct_empty(uint8_t type, int srid, char hasz, char hasm);
extern LWPOINT* lwpoint_construct_empty(int srid, char hasz, char hasm);
extern LWLINE* lwline_construct_empty(int srid, char hasz, char hasm);
extern LWPOLY* lwpoly_construct_empty(int srid, char hasz, char hasm);
extern LWCURVEPOLY* lwcurvepoly_construct_empty(int srid, char hasz, char hasm);
extern LWCIRCSTRING* lwcircstring_construct_empty(int srid, char hasz, char hasm);
extern LWCOMPOUND* lwcompound_construct_empty(int srid, char hasz, char hasm);
extern LWTRIANGLE* lwtriangle_construct_empty(int srid, char hasz, char hasm);
extern LWMPOINT* lwmpoint_construct_empty(int srid, char hasz, char hasm);
extern LWMLINE* lwmline_construct_empty(int srid, char hasz, char hasm);
extern LWMPOLY* lwmpoly_construct_empty(int srid, char hasz, char hasm);
extern LWCOLLECTION* lwcollection_construct_empty(uint8_t type, int srid, char hasz, char hasm);


/* Other constructors */
extern LWPOINT *lwpoint_make2d(int srid, double x, double y);
extern LWPOINT *lwpoint_make3dz(int srid, double x, double y, double z);
extern LWPOINT *lwpoint_make3dm(int srid, double x, double y, double m);
extern LWPOINT *lwpoint_make4d(int srid, double x, double y, double z, double m);
extern LWPOINT *lwpoint_make(int srid, int hasz, int hasm, const POINT4D *p);
extern LWLINE *lwline_from_lwgeom_array(int srid, uint32_t ngeoms, LWGEOM **geoms);
extern LWLINE *lwline_from_ptarray(int srid, uint32_t npoints, LWPOINT **points); /* TODO: deprecate */
extern LWLINE *lwline_from_lwmpoint(int srid, const LWMPOINT *mpoint);
extern LWLINE *lwline_addpoint(LWLINE *line, LWPOINT *point, uint32_t where);
extern LWLINE *lwline_removepoint(LWLINE *line, uint32_t which);
extern void lwline_setPoint4d(LWLINE *line, uint32_t which, POINT4D *newpoint);
extern LWPOLY *lwpoly_from_lwlines(const LWLINE *shell, uint32_t nholes, const LWLINE **holes);
extern LWPOLY *lwpoly_construct_rectangle(char hasz, char hasm, POINT4D *p1, POINT4D *p2, POINT4D *p3, POINT4D *p4);
extern LWPOLY *lwpoly_construct_envelope(int srid, double x1, double y1, double x2, double y2);
extern LWPOLY *lwpoly_construct_circle(int srid, double x, double y, double radius, uint32_t segments_per_quarter, char exterior);
extern LWTRIANGLE *lwtriangle_from_lwline(const LWLINE *shell);
extern LWMPOINT *lwmpoint_from_lwgeom(const LWGEOM *g); /* Extract the coordinates of an LWGEOM into an LWMPOINT */

/* Some point accessors */
extern double lwpoint_get_x(const LWPOINT *point);
extern double lwpoint_get_y(const LWPOINT *point);
extern double lwpoint_get_z(const LWPOINT *point);
extern double lwpoint_get_m(const LWPOINT *point);

extern int32_t lwgeom_get_srid(const LWGEOM *geom);

extern uint32_t lwgeom_get_type(const LWGEOM *geom);

extern int lwgeom_has_z(const LWGEOM *geom);

extern int lwgeom_has_m(const LWGEOM *geom);

extern int lwgeom_ndims(const LWGEOM *geom);

/*
 * Given a point, returns the location of closest point on pointarray
 * as a fraction of total length (0: first point -- 1: last point).
 *
 * If not-null, the third argument will be set to the actual distance
 * of the point from the pointarray.
 */
extern double ptarray_locate_point(const POINTARRAY *pa, const POINT4D *pt, double *dist, POINT4D *p_located);

extern LWLINE *lwline_measured_from_lwline(const LWLINE *lwline, double m_start, double m_end);
extern LWMLINE* lwmline_measured_from_lwmline(const LWMLINE *lwmline, double m_start, double m_end);

extern LWGEOM* lwgeom_locate_along(const LWGEOM *lwin, double m, double offset);

extern LWCOLLECTION* lwgeom_locate_between(const LWGEOM *lwin, double from, double to, double offset);

extern double lwgeom_interpolate_point(const LWGEOM *lwin, const LWPOINT *lwpt);

extern double lwgeom_tcpa(const LWGEOM *g1, const LWGEOM *g2, double *mindist);

extern int lwgeom_cpa_within(const LWGEOM *g1, const LWGEOM *g2, double maxdist);

extern int lwgeom_is_trajectory(const LWGEOM *geom);
extern int lwline_is_trajectory(const LWLINE *geom);

/*
 * Ensure every segment is at most 'dist' long.
 * Returned LWGEOM might is unchanged if a POINT.
 */
extern LWGEOM *lwgeom_segmentize2d(LWGEOM *line, double dist);
extern POINTARRAY *ptarray_segmentize2d(const POINTARRAY *ipa, double dist);
extern LWLINE *lwline_segmentize2d(LWLINE *line, double dist);
extern LWPOLY *lwpoly_segmentize2d(LWPOLY *line, double dist);
extern LWCOLLECTION *lwcollection_segmentize2d(LWCOLLECTION *coll, double dist);

/*
 * Point density functions
 */
extern LWMPOINT *lwpoly_to_points(const LWPOLY *poly, int npoints);
extern LWMPOINT *lwmpoly_to_points(const LWMPOLY *mpoly, int npoints);
extern LWMPOINT *lwgeom_to_points(const LWGEOM *lwgeom, int npoints);

/*
 * Geometric median
 */
extern LWPOINT* lwgeom_median(const LWGEOM *g, double tol, uint32_t maxiter, char fail_if_not_converged);
extern LWPOINT* lwmpoint_median(const LWMPOINT *g, double tol, uint32_t maxiter, char fail_if_not_converged);

char *lwgeom_geohash(const LWGEOM *lwgeom, int precision);
unsigned int geohash_point_as_int(POINT2D *pt);


enum CG_LINE_CROSS_TYPE {
    LINE_NO_CROSS = 0,
    LINE_CROSS_LEFT = -1,
    LINE_CROSS_RIGHT = 1,
    LINE_MULTICROSS_END_LEFT = -2,
    LINE_MULTICROSS_END_RIGHT = 2,
    LINE_MULTICROSS_END_SAME_FIRST_LEFT = -3,
    LINE_MULTICROSS_END_SAME_FIRST_RIGHT = 3
};

int lwline_crossing_direction(const LWLINE *l1, const LWLINE *l2);

LWCOLLECTION* lwgeom_clip_to_ordinate_range(const LWGEOM *lwin, char ordinate, double from, double to, double offset);

#define LW_GML_IS_DIMS     (1<<0)

#define LW_GML_IS_DEGREE   (1<<1)

#define LW_GML_SHORTLINE   (1<<2)

#define LW_GML_EXTENT      (1<<4)


#define IS_DIMS(x) ((x) & LW_GML_IS_DIMS)
#define IS_DEGREE(x) ((x) & LW_GML_IS_DEGREE)

#define LW_X3D_FLIP_XY     (1<<0)
#define LW_X3D_USE_GEOCOORDS     (1<<1)
#define X3D_USE_GEOCOORDS(x) ((x) & LW_X3D_USE_GEOCOORDS)



extern char* lwgeom_to_gml2(const LWGEOM *geom, const char *srs, int precision, const char *prefix);
extern char* lwgeom_extent_to_gml2(const LWGEOM *geom, const char *srs, int precision, const char *prefix);
extern char* lwgeom_extent_to_gml3(const LWGEOM *geom, const char *srs, int precision, int opts, const char *prefix);
extern char* lwgeom_to_gml3(const LWGEOM *geom, const char *srs, int precision, int opts, const char *prefix, const char *id);
extern char* lwgeom_to_kml2(const LWGEOM *geom, int precision, const char *prefix);
extern char* lwgeom_to_geojson(const LWGEOM *geo, char *srs, int precision, int has_bbox);
extern char* lwgeom_to_svg(const LWGEOM *geom, int precision, int relative);
extern char* lwgeom_to_x3d3(const LWGEOM *geom, char *srs, int precision, int opts, const char *defid);
extern char* lwgeom_to_encoded_polyline(const LWGEOM *geom, int precision);

extern LWGEOM* lwgeom_from_geojson(const char *geojson, char **srs);

extern LWGEOM* lwgeom_from_encoded_polyline(const char *encodedpolyline, int precision);

extern void spheroid_init(SPHEROID *s, double a, double b);

extern double lwgeom_distance_spheroid(const LWGEOM *lwgeom1, const LWGEOM *lwgeom2, const SPHEROID *spheroid, double tolerance);

extern LWPOINT* lwgeom_project_spheroid(const LWPOINT *r, const SPHEROID *spheroid, double distance, double azimuth);

extern LWGEOM* lwgeom_segmentize_sphere(const LWGEOM *lwg_in, double max_seg_length);

extern double lwgeom_azumith_spheroid(const LWPOINT *r, const LWPOINT *s, const SPHEROID *spheroid);

extern double lwgeom_area_sphere(const LWGEOM *lwgeom, const SPHEROID *spheroid);

extern double lwgeom_area_spheroid(const LWGEOM *lwgeom, const SPHEROID *spheroid);

extern double lwgeom_length_spheroid(const LWGEOM *geom, const SPHEROID *s);

extern int lwgeom_covers_lwgeom_sphere(const LWGEOM *lwgeom1, const LWGEOM *lwgeom2);

typedef struct {
        POINT2D* center;
        double radius;
} LWBOUNDINGCIRCLE;

extern void lwboundingcircle_destroy(LWBOUNDINGCIRCLE* c);

/* Calculates the minimum circle that encloses all of the points in g, using a
 * two-dimensional implementation of the algorithm proposed in:
 *
 * Welzl, Emo (1991), "Smallest enclosing disks (balls and elipsoids)."
 * New Results and Trends in Computer Science (H. Maurer, Ed.), Lecture Notes
 * in Computer Science, 555 (1991) 359-370.
 *
 * Available online at the time of this writing at
 * https://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf
 *
 * Returns NULL if the circle could not be calculated.
 */
extern LWBOUNDINGCIRCLE* lwgeom_calculate_mbc(const LWGEOM* g);

extern LWGEOM* lwgeom_remove_repeated_points(const LWGEOM *in, double tolerance);

extern char lwtriangle_is_repeated_points(LWTRIANGLE *triangle);

extern void lwgeom_swap_ordinates(LWGEOM *in, LWORD o1, LWORD o2);

extern LWGEOM* lwgeom_flip_coordinates(LWGEOM *in);

struct LWPOINTITERATOR;
typedef struct LWPOINTITERATOR LWPOINTITERATOR;

extern LWPOINTITERATOR* lwpointiterator_create(const LWGEOM* g);

extern LWPOINTITERATOR* lwpointiterator_create_rw(LWGEOM* g);

extern void lwpointiterator_destroy(LWPOINTITERATOR* s);

extern int lwpointiterator_has_next(LWPOINTITERATOR* s);

extern int lwpointiterator_modify_next(LWPOINTITERATOR* s, const POINT4D* p);

extern int lwpointiterator_next(LWPOINTITERATOR* s, POINT4D* p);

extern int lwpointiterator_peek(LWPOINTITERATOR* s, POINT4D* p);


extern uint8_t parse_hex(char *str);

extern void deparse_hex(uint8_t str, char *result);



/***********************************************************************
** Functions for managing serialized forms and bounding boxes.
*/

extern GBOX* gserialized_calculate_gbox_geocentric(const GSERIALIZED *g);

int gserialized_calculate_gbox_geocentric_p(const GSERIALIZED *g, GBOX *g_box);

extern char* gserialized_to_string(const GSERIALIZED *g);

extern GSERIALIZED* gserialized_copy(const GSERIALIZED *g);

extern int lwgeom_check_geodetic(const LWGEOM *geom);

extern int lwgeom_nudge_geodetic(LWGEOM *geom);

extern int lwgeom_force_geodetic(LWGEOM *geom);

extern void lwgeom_set_geodetic(LWGEOM *geom, int value);

extern int lwgeom_calculate_gbox_geodetic(const LWGEOM *geom, GBOX *gbox);

extern int lwgeom_calculate_gbox_cartesian(const LWGEOM *lwgeom, GBOX *gbox);

extern int lwgeom_calculate_gbox(const LWGEOM *lwgeom, GBOX *gbox);

extern int getPoint2d_p_ro(const POINTARRAY *pa, int n, POINT2D **point);

extern int ptarray_calculate_gbox_geodetic(const POINTARRAY *pa, GBOX *gbox);

extern int ptarray_calculate_gbox_cartesian(const POINTARRAY *pa, GBOX *gbox );

int gbox_pt_outside(const GBOX *gbox, POINT2D *pt_outside);

extern GBOX* gbox_new(uint8_t flags);

extern void gbox_init(GBOX *gbox);

extern int gbox_merge(const GBOX *new_box, GBOX *merged_box);

extern int gbox_union(const GBOX *g1, const GBOX *g2, GBOX *gout);

extern void gbox_expand(GBOX *g, double d);

extern void gbox_expand_xyzm(GBOX *g, double dx, double dy, double dz, double dm);

extern int gbox_init_point3d(const POINT3D *p, GBOX *gbox);

extern int gbox_merge_point3d(const POINT3D *p, GBOX *gbox);

extern int gbox_contains_point3d(const GBOX *gbox, const POINT3D *pt);

extern char* gbox_to_string(const GBOX *gbox);

extern GBOX* gbox_copy(const GBOX *gbox);

extern GBOX* gbox_from_string(const char *str);

extern int gbox_overlaps(const GBOX *g1, const GBOX *g2);

extern int gbox_overlaps_2d(const GBOX *g1, const GBOX *g2);

extern int  gbox_contains_2d(const GBOX *g1, const GBOX *g2);

extern void gbox_duplicate(const GBOX *original, GBOX *duplicate);

extern size_t gbox_serialized_size(uint8_t flags);

extern int gbox_same(const GBOX *g1, const GBOX *g2);

extern int gbox_same_2d(const GBOX *g1, const GBOX *g2);

extern int gbox_same_2d_float(const GBOX *g1, const GBOX *g2);

extern void gbox_float_round(GBOX *gbox);

extern int gbox_is_valid(const GBOX *gbox);

extern uint64_t gbox_get_sortable_hash(const GBOX *g);

extern int geometry_type_from_string(const char *str, uint8_t *type, int *z, int *m);

extern size_t gserialized_from_lwgeom_size(const LWGEOM *geom);

extern GSERIALIZED* gserialized_from_lwgeom(LWGEOM *geom, size_t *size);

extern LWGEOM* lwgeom_from_gserialized(const GSERIALIZED *g);

extern int gserialized_get_gbox_p(const GSERIALIZED *g, GBOX *gbox);


#define LW_PARSER_CHECK_MINPOINTS  1
#define LW_PARSER_CHECK_ODD        2
#define LW_PARSER_CHECK_CLOSURE    4
#define LW_PARSER_CHECK_ZCLOSURE   8

#define LW_PARSER_CHECK_NONE   0
#define LW_PARSER_CHECK_ALL     (LW_PARSER_CHECK_MINPOINTS | LW_PARSER_CHECK_ODD | LW_PARSER_CHECK_CLOSURE)

typedef struct struct_lwgeom_parser_result
{
        const char *wkinput;        /* Copy of pointer to input WKT/WKB */
        uint8_t *serialized_lwgeom;   /* Pointer to serialized LWGEOM */
        int size;                   /* Size of serialized LWGEOM in bytes */
        LWGEOM *geom;               /* Pointer to LWGEOM struct */
        const char *message;        /* Error/warning message */
        int errcode;                /* Error/warning number */
        int errlocation;            /* Location of error */
        int parser_check_flags;     /* Bitmask of validity checks run during this parse */
}
LWGEOM_PARSER_RESULT;

/*
 * Parser error messages (these must match the message array in lwgparse.c)
 */
#define PARSER_ERROR_MOREPOINTS     1
#define PARSER_ERROR_ODDPOINTS      2
#define PARSER_ERROR_UNCLOSED       3
#define PARSER_ERROR_MIXDIMS        4
#define PARSER_ERROR_INVALIDGEOM    5
#define PARSER_ERROR_INVALIDWKBTYPE 6
#define PARSER_ERROR_INCONTINUOUS   7
#define PARSER_ERROR_TRIANGLEPOINTS 8
#define PARSER_ERROR_LESSPOINTS     9
#define PARSER_ERROR_OTHER          10



/*
 * Unparser result structure: returns the result of attempting to convert LWGEOM to (E)WKT/(E)WKB
 */
typedef struct struct_lwgeom_unparser_result
{
        uint8_t *serialized_lwgeom;     /* Copy of pointer to input serialized LWGEOM */
        char *wkoutput;                 /* Pointer to WKT or WKB output */
        int size;                       /* Size of serialized LWGEOM in bytes */
        const char *message;            /* Error/warning message */
        int errlocation;                /* Location of error */
}
LWGEOM_UNPARSER_RESULT;

/*
 * Unparser error messages (these must match the message array in lwgunparse.c)
 */
#define UNPARSER_ERROR_MOREPOINTS       1
#define UNPARSER_ERROR_ODDPOINTS        2
#define UNPARSER_ERROR_UNCLOSED         3


/*
** Variants available for WKB and WKT output types
*/

#define WKB_ISO 0x01
#define WKB_SFSQL 0x02
#define WKB_EXTENDED 0x04
#define WKB_NDR 0x08
#define WKB_XDR 0x10
#define WKB_HEX 0x20
#define WKB_NO_NPOINTS 0x40 /* Internal use only */
#define WKB_NO_SRID 0x80 /* Internal use only */

#define WKT_ISO 0x01
#define WKT_SFSQL 0x02
#define WKT_EXTENDED 0x04


/*
** Variants available for TWKB
*/
#define TWKB_BBOX 0x01 /* User wants bboxes */
#define TWKB_SIZE 0x02 /* User wants sizes */
#define TWKB_ID 0x04 /* User wants id */
#define TWKB_NO_TYPE 0x10 /* No type because it is a sub geoemtry */
#define TWKB_NO_ID 0x20 /* No ID because it is a subgeoemtry */
#define TWKB_DEFAULT_PRECISION 0 /* Aim for 1m (or ft) rounding by default */

/*
** New parsing and unparsing functions.
*/

extern char*   lwgeom_to_wkt(const LWGEOM *geom, uint8_t variant, int precision, size_t *size_out);

extern uint8_t*  lwgeom_to_wkb(const LWGEOM *geom, uint8_t variant, size_t *size_out);

extern char*   lwgeom_to_hexwkb(const LWGEOM *geom, uint8_t variant, size_t *size_out);

extern char *lwgeom_to_ewkt(const LWGEOM *lwgeom);

extern LWGEOM* lwgeom_from_wkb(const uint8_t *wkb, const size_t wkb_size, const char check);

extern LWGEOM* lwgeom_from_wkt(const char *wkt, const char check);

extern LWGEOM* lwgeom_from_hexwkb(const char *hexwkb, const char check);

extern uint8_t*  bytes_from_hexbytes(const char *hexbuf, size_t hexsize);

extern char*   hexbytes_from_bytes(uint8_t *bytes, size_t size);

/*
* WKT detailed parsing support
*/
extern int lwgeom_parse_wkt(LWGEOM_PARSER_RESULT *parser_result, char *wktstr, int parse_flags);
void lwgeom_parser_result_init(LWGEOM_PARSER_RESULT *parser_result);
void lwgeom_parser_result_free(LWGEOM_PARSER_RESULT *parser_result);


/* Memory management */
extern void *lwalloc(size_t size);
extern void *lwrealloc(void *mem, size_t size);
extern void lwfree(void *mem);

/* Utilities */
extern char *lwmessage_truncate(char *str, int startpos, int endpos, int maxlength, int truncdirection);

/*
* TWKB functions
*/

extern LWGEOM* lwgeom_from_twkb(uint8_t *twkb, size_t twkb_size, char check);

extern uint8_t* lwgeom_to_twkb(const LWGEOM *geom, uint8_t variant, int8_t precision_xy, int8_t precision_z, int8_t precision_m, size_t *twkb_size);

extern uint8_t* lwgeom_to_twkb_with_idlist(const LWGEOM *geom, int64_t *idlist, uint8_t variant, int8_t precision_xy, int8_t precision_z, int8_t precision_m, size_t *twkb_size);

/*******************************************************************************
 * SQLMM internal functions
 ******************************************************************************/

int lwgeom_has_arc(const LWGEOM *geom);
LWGEOM *lwgeom_stroke(const LWGEOM *geom, uint32_t perQuad);
LWGEOM *lwgeom_unstroke(const LWGEOM *geom);

typedef enum {
        LW_LINEARIZE_TOLERANCE_TYPE_SEGS_PER_QUAD = 0,
        LW_LINEARIZE_TOLERANCE_TYPE_MAX_DEVIATION = 1,
        LW_LINEARIZE_TOLERANCE_TYPE_MAX_ANGLE = 2
} LW_LINEARIZE_TOLERANCE_TYPE;

typedef enum {
        LW_LINEARIZE_FLAG_SYMMETRIC = 1 << 0,

        LW_LINEARIZE_FLAG_RETAIN_ANGLE = 1 << 1
} LW_LINEARIZE_FLAGS;

extern LWGEOM* lwcurve_linearize(const LWGEOM *geom, double tol, LW_LINEARIZE_TOLERANCE_TYPE type, int flags);

/*******************************************************************************
 * GEOS proxy functions on LWGEOM
 ******************************************************************************/

const char* lwgeom_geos_version(void);

LWGEOM* lwgeom_geos_noop(const LWGEOM *geom) ;

LWGEOM *lwgeom_normalize(const LWGEOM *geom);
LWGEOM *lwgeom_intersection(const LWGEOM *geom1, const LWGEOM *geom2);
LWGEOM *lwgeom_difference(const LWGEOM *geom1, const LWGEOM *geom2);
LWGEOM *lwgeom_symdifference(const LWGEOM* geom1, const LWGEOM* geom2);
LWGEOM *lwgeom_centroid(const LWGEOM* geom);
LWGEOM *lwgeom_union(const LWGEOM *geom1, const LWGEOM *geom2);
LWGEOM *lwgeom_linemerge(const LWGEOM *geom1);
LWGEOM *lwgeom_unaryunion(const LWGEOM *geom1);
LWGEOM *lwgeom_clip_by_rect(const LWGEOM *geom1, double x0, double y0, double x1, double y1);
LWCOLLECTION *lwgeom_subdivide(const LWGEOM *geom, int maxvertices);

LWGEOM* lwgeom_snap(const LWGEOM* geom1, const LWGEOM* geom2, double tolerance);

/*
 * Return the set of paths shared between two linear geometries,
 * and their direction (same or opposite).
 *
 * @param geom1 a lineal geometry
 * @param geom2 another lineal geometry
 *
 * Requires GEOS-3.3.0+
 */
LWGEOM* lwgeom_sharedpaths(const LWGEOM* geom1, const LWGEOM* geom2);

/*
 * An offset curve against the input line.
 *
 * @param lwline a lineal geometry
 * @param size offset distance. Offset left if negative and right if positive
 * @param quadsegs number of quadrature segments in curves (try 8)
 * @param joinStyle (1 = round, 2 = mitre, 3 = bevel)
 * @param mitreLimit (try 5.0)
 * @return derived geometry (linestring or multilinestring)
 *
 * Requires GEOS-3.2.0+
 */
LWGEOM* lwgeom_offsetcurve(const LWLINE *lwline, double size, int quadsegs, int joinStyle, double mitreLimit);

/*
 * Return true if the input geometry is "simple" as per OGC defn.
 *
 * @return 1 if simple, 0 if non-simple, -1 on exception (lwerror is called
 *         in that case)
 */
int lwgeom_is_simple(const LWGEOM *lwgeom);


/*******************************************************************************
 * PROJ4-dependent extra functions on LWGEOM
 ******************************************************************************/

projPJ lwproj_from_string(const char* txt);

int lwgeom_transform(LWGEOM *geom, projPJ inpj, projPJ outpj) ;
int ptarray_transform(POINTARRAY *geom, projPJ inpj, projPJ outpj) ;
int point4d_transform(POINT4D *pt, projPJ srcpj, projPJ dstpj) ;


/*******************************************************************************
 * GEOS-dependent extra functions on LWGEOM
 ******************************************************************************/

LWGEOM* lwgeom_buildarea(const LWGEOM *geom) ;


LWGEOM* lwgeom_make_valid(LWGEOM* geom);

/*
 * Split (multi)polygon by line; (multi)line by (multi)line,
 * (multi)point or (multi)polygon boundary.
 *
 * Collections are accepted as first argument.
 * Returns all obtained pieces as a collection.
 */
LWGEOM* lwgeom_split(const LWGEOM* lwgeom_in, const LWGEOM* blade_in);

/*
 * Fully node a set of linestrings, using the least nodes preserving
 * all the input ones.
 *
 * Requires GEOS-3.3.0 or higher
 */
LWGEOM* lwgeom_node(const LWGEOM* lwgeom_in);

LWGEOM* lwgeom_delaunay_triangulation(const LWGEOM *geom, double tolerance, int edgeOnly);

LWGEOM* lwgeom_voronoi_diagram(const LWGEOM* g, const GBOX* env, double tolerance, int output_edges);

int * lwgeom_cluster_2d_kmeans(const LWGEOM **geoms, int ngeoms, int k);


#endif /* !defined _LIBLWGEOM_H  */