PostGIS  2.5.7dev-r@@SVN_REVISION@@
lwgeom_topo.c File Reference
#include "../postgis_config.h"
#include "lwgeom_log.h"
#include "liblwgeom_internal.h"
#include "liblwgeom_topo_internal.h"
#include "lwgeom_geos.h"
#include <stdio.h>
#include <inttypes.h>
#include <errno.h>
#include <math.h>
Include dependency graph for lwgeom_topo.c:

Go to the source code of this file.

Data Structures

struct  edgeend_t
 
struct  scored_pointer_t
 
struct  LWT_ISO_EDGE_TABLE_T
 
struct  LWT_EDGERING_ELEM_T
 
struct  LWT_EDGERING_T
 
struct  LWT_EDGERING_ARRAY_T
 
struct  LWT_EDGERING_POINT_ITERATOR_T
 

Macros

#define LWTFMT_ELEMID   PRId64
 
#define CHECKCB(be, method)
 
#define CB0(be, method)
 
#define CB1(be, method, a1)
 
#define CBT0(to, method)
 
#define CBT1(to, method, a1)
 
#define CBT2(to, method, a1, a2)
 
#define CBT3(to, method, a1, a2, a3)
 
#define CBT4(to, method, a1, a2, a3, a4)
 
#define CBT5(to, method, a1, a2, a3, a4, a5)
 
#define CBT6(to, method, a1, a2, a3, a4, a5, a6)
 
#define _LWT_MINTOLERANCE(topo, geom)
 
#define LWT_EDGERING_INIT(a)
 
#define LWT_EDGERING_PUSH(a, r)
 
#define LWT_EDGERING_CLEAN(a)
 
#define LWT_EDGERING_ARRAY_INIT(a)
 
#define LWT_EDGERING_ARRAY_CLEAN(a)
 
#define LWT_EDGERING_ARRAY_PUSH(a, r)
 
#define LWT_HOLES_FACE_PLACEHOLDER   INT32_MIN
 

Typedefs

typedef struct edgeend_t edgeend
 
typedef struct scored_pointer_t scored_pointer
 
typedef struct LWT_ISO_EDGE_TABLE_T LWT_ISO_EDGE_TABLE
 
typedef struct LWT_EDGERING_ELEM_T LWT_EDGERING_ELEM
 
typedef struct LWT_EDGERING_T LWT_EDGERING
 
typedef struct LWT_EDGERING_ARRAY_T LWT_EDGERING_ARRAY
 
typedef struct LWT_EDGERING_POINT_ITERATOR_T LWT_EDGERING_POINT_ITERATOR
 

Functions

LWT_BE_IFACElwt_CreateBackendIface (const LWT_BE_DATA *data)
 Create a new backend interface. More...
 
void lwt_BackendIfaceRegisterCallbacks (LWT_BE_IFACE *iface, const LWT_BE_CALLBACKS *cb)
 Register backend callbacks into the opaque iface handler. More...
 
void lwt_FreeBackendIface (LWT_BE_IFACE *iface)
 Release memory associated with an LWT_BE_IFACE. More...
 
const char * lwt_be_lastErrorMessage (const LWT_BE_IFACE *be)
 
LWT_BE_TOPOLOGYlwt_be_loadTopologyByName (LWT_BE_IFACE *be, const char *name)
 
static int lwt_be_topoGetSRID (LWT_TOPOLOGY *topo)
 
static double lwt_be_topoGetPrecision (LWT_TOPOLOGY *topo)
 
static int lwt_be_topoHasZ (LWT_TOPOLOGY *topo)
 
int lwt_be_freeTopology (LWT_TOPOLOGY *topo)
 
LWT_ISO_NODElwt_be_getNodeById (LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields)
 
LWT_ISO_NODElwt_be_getNodeWithinDistance2D (LWT_TOPOLOGY *topo, LWPOINT *pt, double dist, int *numelems, int fields, int limit)
 
static LWT_ISO_NODElwt_be_getNodeWithinBox2D (const LWT_TOPOLOGY *topo, const GBOX *box, int *numelems, int fields, int limit)
 
static LWT_ISO_EDGElwt_be_getEdgeWithinBox2D (const LWT_TOPOLOGY *topo, const GBOX *box, int *numelems, int fields, int limit)
 
static LWT_ISO_FACElwt_be_getFaceWithinBox2D (const LWT_TOPOLOGY *topo, const GBOX *box, int *numelems, int fields, int limit)
 
int lwt_be_insertNodes (LWT_TOPOLOGY *topo, LWT_ISO_NODE *node, int numelems)
 
static int lwt_be_insertFaces (LWT_TOPOLOGY *topo, LWT_ISO_FACE *face, int numelems)
 
static int lwt_be_deleteFacesById (const LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int numelems)
 
static int lwt_be_deleteNodesById (const LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int numelems)
 
LWT_ELEMID lwt_be_getNextEdgeId (LWT_TOPOLOGY *topo)
 
LWT_ISO_EDGElwt_be_getEdgeById (LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields)
 
static LWT_ISO_FACElwt_be_getFaceById (LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields)
 
static LWT_ISO_EDGElwt_be_getEdgeByNode (LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields)
 
static LWT_ISO_EDGElwt_be_getEdgeByFace (LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields, const GBOX *box)
 
static LWT_ISO_NODElwt_be_getNodeByFace (LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields, const GBOX *box)
 
LWT_ISO_EDGElwt_be_getEdgeWithinDistance2D (LWT_TOPOLOGY *topo, LWPOINT *pt, double dist, int *numelems, int fields, int limit)
 
int lwt_be_insertEdges (LWT_TOPOLOGY *topo, LWT_ISO_EDGE *edge, int numelems)
 
int lwt_be_updateEdges (LWT_TOPOLOGY *topo, const LWT_ISO_EDGE *sel_edge, int sel_fields, const LWT_ISO_EDGE *upd_edge, int upd_fields, const LWT_ISO_EDGE *exc_edge, int exc_fields)
 
static int lwt_be_updateNodes (LWT_TOPOLOGY *topo, const LWT_ISO_NODE *sel_node, int sel_fields, const LWT_ISO_NODE *upd_node, int upd_fields, const LWT_ISO_NODE *exc_node, int exc_fields)
 
static int lwt_be_updateFacesById (LWT_TOPOLOGY *topo, const LWT_ISO_FACE *faces, int numfaces)
 
static int lwt_be_updateEdgesById (LWT_TOPOLOGY *topo, const LWT_ISO_EDGE *edges, int numedges, int upd_fields)
 
static int lwt_be_updateNodesById (LWT_TOPOLOGY *topo, const LWT_ISO_NODE *nodes, int numnodes, int upd_fields)
 
int lwt_be_deleteEdges (LWT_TOPOLOGY *topo, const LWT_ISO_EDGE *sel_edge, int sel_fields)
 
LWT_ELEMID lwt_be_getFaceContainingPoint (LWT_TOPOLOGY *topo, LWPOINT *pt)
 
int lwt_be_updateTopoGeomEdgeSplit (LWT_TOPOLOGY *topo, LWT_ELEMID split_edge, LWT_ELEMID new_edge1, LWT_ELEMID new_edge2)
 
static int lwt_be_updateTopoGeomFaceSplit (LWT_TOPOLOGY *topo, LWT_ELEMID split_face, LWT_ELEMID new_face1, LWT_ELEMID new_face2)
 
static int lwt_be_checkTopoGeomRemEdge (LWT_TOPOLOGY *topo, LWT_ELEMID edge_id, LWT_ELEMID face_left, LWT_ELEMID face_right)
 
static int lwt_be_checkTopoGeomRemNode (LWT_TOPOLOGY *topo, LWT_ELEMID node_id, LWT_ELEMID eid1, LWT_ELEMID eid2)
 
static int lwt_be_updateTopoGeomFaceHeal (LWT_TOPOLOGY *topo, LWT_ELEMID face1, LWT_ELEMID face2, LWT_ELEMID newface)
 
static int lwt_be_updateTopoGeomEdgeHeal (LWT_TOPOLOGY *topo, LWT_ELEMID edge1, LWT_ELEMID edge2, LWT_ELEMID newedge)
 
static LWT_ELEMIDlwt_be_getRingEdges (LWT_TOPOLOGY *topo, LWT_ELEMID edge, int *numedges, int limit)
 
int lwt_be_ExistsCoincidentNode (LWT_TOPOLOGY *topo, LWPOINT *pt)
 
int lwt_be_ExistsEdgeIntersectingPoint (LWT_TOPOLOGY *topo, LWPOINT *pt)
 
static LWGEOM_lwt_toposnap (LWGEOM *src, LWGEOM *tgt, double tol)
 
static void _lwt_release_faces (LWT_ISO_FACE *faces, int num_faces)
 
static void _lwt_release_edges (LWT_ISO_EDGE *edges, int num_edges)
 
static void _lwt_release_nodes (LWT_ISO_NODE *nodes, int num_nodes)
 
LWT_TOPOLOGYlwt_LoadTopology (LWT_BE_IFACE *iface, const char *name)
 Loads an existing topology by name from the database. More...
 
void lwt_FreeTopology (LWT_TOPOLOGY *topo)
 Release memory associated with an LWT_TOPOLOGY. More...
 
static LWT_ELEMID _lwt_AddIsoNode (LWT_TOPOLOGY *topo, LWT_ELEMID face, LWPOINT *pt, int skipISOChecks, int checkFace)
 
LWT_ELEMID lwt_AddIsoNode (LWT_TOPOLOGY *topo, LWT_ELEMID face, LWPOINT *pt, int skipISOChecks)
 Add an isolated node. More...
 
static int _lwt_CheckEdgeCrossing (LWT_TOPOLOGY *topo, LWT_ELEMID start_node, LWT_ELEMID end_node, const LWLINE *geom, LWT_ELEMID myself)
 
LWT_ELEMID lwt_AddIsoEdge (LWT_TOPOLOGY *topo, LWT_ELEMID startNode, LWT_ELEMID endNode, const LWLINE *geom)
 Add an isolated edge connecting two existing isolated nodes. More...
 
static LWCOLLECTION_lwt_EdgeSplit (LWT_TOPOLOGY *topo, LWT_ELEMID edge, LWPOINT *pt, int skipISOChecks, LWT_ISO_EDGE **oldedge)
 
LWT_ELEMID lwt_ModEdgeSplit (LWT_TOPOLOGY *topo, LWT_ELEMID edge, LWPOINT *pt, int skipISOChecks)
 Split an edge by a node, modifying the original edge and adding a new one. More...
 
LWT_ELEMID lwt_NewEdgesSplit (LWT_TOPOLOGY *topo, LWT_ELEMID edge, LWPOINT *pt, int skipISOChecks)
 Split an edge by a node, replacing it with two new edges. More...
 
static int _lwt_FirstDistinctVertex2D (const POINTARRAY *pa, POINT2D *ref, int from, int dir, POINT2D *op)
 
static int _lwt_InitEdgeEndByLine (edgeend *fee, edgeend *lee, LWLINE *edge, POINT2D *fp, POINT2D *lp)
 
static int _lwt_FindAdjacentEdges (LWT_TOPOLOGY *topo, LWT_ELEMID node, edgeend *data, edgeend *other, int myedge_id)
 
static int _lwt_GetInteriorEdgePoint (const LWLINE *edge, POINT2D *ip)
 
static LWPOLY_lwt_MakeRingShell (LWT_TOPOLOGY *topo, LWT_ELEMID *signed_edge_ids, int num_signed_edge_ids)
 
static LWT_ELEMID _lwt_AddFaceSplit (LWT_TOPOLOGY *topo, LWT_ELEMID sedge, LWT_ELEMID face, int mbr_only)
 
static LWT_ELEMID _lwt_AddEdge (LWT_TOPOLOGY *topo, LWT_ELEMID start_node, LWT_ELEMID end_node, LWLINE *geom, int skipChecks, int modFace)
 
LWT_ELEMID lwt_AddEdgeModFace (LWT_TOPOLOGY *topo, LWT_ELEMID start_node, LWT_ELEMID end_node, LWLINE *geom, int skipChecks)
 Add a new edge possibly splitting a face (modifying it) More...
 
LWT_ELEMID lwt_AddEdgeNewFaces (LWT_TOPOLOGY *topo, LWT_ELEMID start_node, LWT_ELEMID end_node, LWLINE *geom, int skipChecks)
 Add a new edge possibly splitting a face (replacing with two new faces) More...
 
static LWGEOM_lwt_FaceByEdges (LWT_TOPOLOGY *topo, LWT_ISO_EDGE *edges, int numfaceedges)
 
LWGEOMlwt_GetFaceGeometry (LWT_TOPOLOGY *topo, LWT_ELEMID faceid)
 Return the geometry of a face. More...
 
static int _lwt_FindNextRingEdge (const POINTARRAY *ring, int from, const LWT_ISO_EDGE *edges, int numedges)
 
static void _lwt_ReverseElemidArray (LWT_ELEMID *ary, int from, int to)
 
static void _lwt_RotateElemidArray (LWT_ELEMID *ary, int from, int to, int rotidx)
 
int lwt_GetFaceEdges (LWT_TOPOLOGY *topo, LWT_ELEMID face_id, LWT_ELEMID **out)
 Return the list of directed edges bounding a face. More...
 
int lwt_ChangeEdgeGeom (LWT_TOPOLOGY *topo, LWT_ELEMID edge_id, LWLINE *geom)
 Changes the shape of an edge without affecting the topology structure. More...
 
static LWT_ISO_NODE_lwt_GetIsoNode (LWT_TOPOLOGY *topo, LWT_ELEMID nid)
 
int lwt_MoveIsoNode (LWT_TOPOLOGY *topo, LWT_ELEMID nid, LWPOINT *pt)
 Move an isolated node. More...
 
int lwt_RemoveIsoNode (LWT_TOPOLOGY *topo, LWT_ELEMID nid)
 Remove an isolated node. More...
 
int lwt_RemIsoEdge (LWT_TOPOLOGY *topo, LWT_ELEMID id)
 Remove an isolated edge. More...
 
static int _lwt_UpdateEdgeFaceRef (LWT_TOPOLOGY *topo, LWT_ELEMID of, LWT_ELEMID nf)
 
static int _lwt_UpdateNodeFaceRef (LWT_TOPOLOGY *topo, LWT_ELEMID of, LWT_ELEMID nf)
 
static LWT_ELEMID _lwt_RemEdge (LWT_TOPOLOGY *topo, LWT_ELEMID edge_id, int modFace)
 
LWT_ELEMID lwt_RemEdgeModFace (LWT_TOPOLOGY *topo, LWT_ELEMID edge_id)
 Remove an edge, possibly merging two faces (replacing one with the other) More...
 
LWT_ELEMID lwt_RemEdgeNewFace (LWT_TOPOLOGY *topo, LWT_ELEMID edge_id)
 Remove an edge, possibly merging two faces (replacing both with a new one) More...
 
static LWT_ELEMID _lwt_HealEdges (LWT_TOPOLOGY *topo, LWT_ELEMID eid1, LWT_ELEMID eid2, int modEdge)
 
LWT_ELEMID lwt_ModEdgeHeal (LWT_TOPOLOGY *topo, LWT_ELEMID e1, LWT_ELEMID e2)
 Merge two edges, modifying the first and deleting the second. More...
 
LWT_ELEMID lwt_NewEdgeHeal (LWT_TOPOLOGY *topo, LWT_ELEMID e1, LWT_ELEMID e2)
 Merge two edges, replacing both with a new one. More...
 
LWT_ELEMID lwt_GetNodeByPoint (LWT_TOPOLOGY *topo, LWPOINT *pt, double tol)
 Retrieve the id of a node at a point location. More...
 
LWT_ELEMID lwt_GetEdgeByPoint (LWT_TOPOLOGY *topo, LWPOINT *pt, double tol)
 Find the edge-id of an edge that intersects a given point. More...
 
LWT_ELEMID lwt_GetFaceByPoint (LWT_TOPOLOGY *topo, LWPOINT *pt, double tol)
 Find the face-id of a face containing a given point. More...
 
static double _lwt_minToleranceDouble (double d)
 
static double _lwt_minTolerance (LWGEOM *g)
 
static int compare_scored_pointer (const void *si1, const void *si2)
 
static LWT_ELEMID _lwt_AddPoint (LWT_TOPOLOGY *topo, LWPOINT *point, double tol, int findFace, int *moved)
 
LWT_ELEMID lwt_AddPoint (LWT_TOPOLOGY *topo, LWPOINT *point, double tol)
 Adds a point to the topology. More...
 
static LWT_ELEMID _lwt_GetEqualEdge (LWT_TOPOLOGY *topo, LWLINE *edge)
 
static LWT_ELEMID _lwt_AddLineEdge (LWT_TOPOLOGY *topo, LWLINE *edge, double tol, int handleFaceSplit)
 
static LWGEOM_lwt_split_by_nodes (const LWGEOM *g, const LWGEOM *nodes)
 
static LWT_ELEMID_lwt_AddLine (LWT_TOPOLOGY *topo, LWLINE *line, double tol, int *nedges, int handleFaceSplit)
 
LWT_ELEMIDlwt_AddLine (LWT_TOPOLOGY *topo, LWLINE *line, double tol, int *nedges)
 Adds a linestring to the topology. More...
 
LWT_ELEMIDlwt_AddLineNoFace (LWT_TOPOLOGY *topo, LWLINE *line, double tol, int *nedges)
 Adds a linestring to the topology without determining generated faces. More...
 
LWT_ELEMIDlwt_AddPolygon (LWT_TOPOLOGY *topo, LWPOLY *poly, double tol, int *nfaces)
 Adds a polygon to the topology. More...
 
static int compare_iso_edges_by_id (const void *si1, const void *si2)
 
static LWT_ISO_EDGE_lwt_getIsoEdgeById (LWT_ISO_EDGE_TABLE *tab, LWT_ELEMID id)
 
static int _lwt_EdgeRingIterator_next (LWT_EDGERING_POINT_ITERATOR *it, POINT2D *pt)
 
static LWT_EDGERING_POINT_ITERATOR_lwt_EdgeRingIterator_begin (LWT_EDGERING *er)
 
static int _lwt_FetchNextUnvisitedEdge (__attribute__((__unused__)) LWT_TOPOLOGY *topo, LWT_ISO_EDGE_TABLE *etab, int from)
 
static LWT_ISO_EDGE_lwt_FetchAllEdges (LWT_TOPOLOGY *topo, int *numedges)
 
static int _lwt_UpdateEdgeRingSideFace (LWT_TOPOLOGY *topo, LWT_EDGERING *ring, LWT_ELEMID face)
 
static LWT_EDGERING_lwt_BuildEdgeRing (__attribute__((__unused__)) LWT_TOPOLOGY *topo, LWT_ISO_EDGE_TABLE *edges, LWT_ISO_EDGE *edge, int side)
 
static double _lwt_EdgeRingSignedArea (LWT_EDGERING_POINT_ITERATOR *it)
 
static int _lwt_EdgeRingIsCCW (LWT_EDGERING *ring)
 
static int _lwt_EdgeRingCrossingCount (const POINT2D *p, LWT_EDGERING_POINT_ITERATOR *it)
 
static int _lwt_EdgeRingContainsPoint (LWT_EDGERING *ring, POINT2D *p)
 
static GBOX_lwt_EdgeRingGetBbox (LWT_EDGERING *ring)
 
static LWT_ELEMID _lwt_EdgeRingGetFace (LWT_EDGERING *ring)
 
static int _lwt_RegisterFaceOnEdgeSide (LWT_TOPOLOGY *topo, LWT_ISO_EDGE *edge, int side, LWT_ISO_EDGE_TABLE *edges, LWT_EDGERING_ARRAY *holes, LWT_EDGERING_ARRAY *shells, LWT_ELEMID *registered)
 
static void _lwt_AccumulateCanditates (void *item, void *userdata)
 
static LWT_ELEMID _lwt_FindFaceContainingRing (LWT_TOPOLOGY *topo, LWT_EDGERING *ring, LWT_EDGERING_ARRAY *shells)
 
static int _lwt_CheckFacesExist (LWT_TOPOLOGY *topo)
 
int lwt_Polygonize (LWT_TOPOLOGY *topo)