liblwgeom_topo.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 (C) 2015-2021 Sandro Santilli <strk@kbt.io>
 *
 **********************************************************************/
 
 
#ifndef LIBLWGEOM_TOPO_H
#define LIBLWGEOM_TOPO_H 1
 
#include "liblwgeom.h"
 
/* INT64 */
typedef int64_t LWT_INT64;
 
typedef LWT_INT64 LWT_ELEMID;
 
/*
 * ISO primitive elements
 */
 
typedef struct
{
  LWT_ELEMID node_id;
  LWT_ELEMID containing_face; /* -1 if not isolated */
  LWPOINT *geom;
}
LWT_ISO_NODE;
 
void lwt_iso_node_release(LWT_ISO_NODE* node);
 
#define LWT_COL_NODE_NODE_ID         1<<0
#define LWT_COL_NODE_CONTAINING_FACE 1<<1
#define LWT_COL_NODE_GEOM            1<<2
#define LWT_COL_NODE_ALL            (1<<3)-1
 
typedef struct
{
  LWT_ELEMID edge_id;
  LWT_ELEMID start_node;
  LWT_ELEMID end_node;
  LWT_ELEMID face_left;
  LWT_ELEMID face_right;
  LWT_ELEMID next_left;
  LWT_ELEMID next_right;
  LWLINE *geom;
}
LWT_ISO_EDGE;
 
#define LWT_COL_EDGE_EDGE_ID         1<<0
#define LWT_COL_EDGE_START_NODE      1<<1
#define LWT_COL_EDGE_END_NODE        1<<2
#define LWT_COL_EDGE_FACE_LEFT       1<<3
#define LWT_COL_EDGE_FACE_RIGHT      1<<4
#define LWT_COL_EDGE_NEXT_LEFT       1<<5
#define LWT_COL_EDGE_NEXT_RIGHT      1<<6
#define LWT_COL_EDGE_GEOM            1<<7
#define LWT_COL_EDGE_ALL            (1<<8)-1
 
typedef struct
{
  LWT_ELEMID face_id;
  GBOX *mbr;
}
LWT_ISO_FACE;
 
#define LWT_COL_FACE_FACE_ID         1<<0
#define LWT_COL_FACE_MBR             1<<1
#define LWT_COL_FACE_ALL            (1<<2)-1
 
typedef enum LWT_SPATIALTYPE_T {
  LWT_PUNTAL = 0,
  LWT_LINEAL = 1,
  LWT_AREAL = 2,
  LWT_COLLECTION = 3
} LWT_SPATIALTYPE;
 
/*
 * Backend handling functions
 */
 
/* opaque pointers referencing native backend objects */
 
typedef struct LWT_BE_DATA_T LWT_BE_DATA;
 
typedef struct LWT_BE_IFACE_T LWT_BE_IFACE;
 
typedef struct LWT_BE_TOPOLOGY_T LWT_BE_TOPOLOGY;
 
typedef struct LWT_BE_CALLBACKS_T {
 
  const char* (*lastErrorMessage) (const LWT_BE_DATA* be);
 
  LWT_BE_TOPOLOGY *(*createTopology)(const LWT_BE_DATA *be, const char *name, int32_t srid, double precision, int hasZ);
 
  LWT_BE_TOPOLOGY* (*loadTopologyByName) (
    const LWT_BE_DATA* be,
    const char* name
  );
 
  int (*freeTopology) (LWT_BE_TOPOLOGY* topo);
 
  LWT_ISO_NODE *(*getNodeById)(const LWT_BE_TOPOLOGY *topo, const LWT_ELEMID *ids, uint64_t *numelems, int fields);
 
  LWT_ISO_NODE *(*getNodeWithinDistance2D)(const LWT_BE_TOPOLOGY *topo,
                                           const LWPOINT *pt,
                                           double dist,
                                           uint64_t *numelems,
                                           int fields,
                                           int64_t limit);
 
  int (*insertNodes)(const LWT_BE_TOPOLOGY *topo, LWT_ISO_NODE *nodes, uint64_t numelems);
 
  LWT_ISO_EDGE *(*getEdgeById)(const LWT_BE_TOPOLOGY *topo, const LWT_ELEMID *ids, uint64_t *numelems, int fields);
 
  LWT_ISO_EDGE *(*getEdgeWithinDistance2D)(const LWT_BE_TOPOLOGY *topo,
                                           const LWPOINT *pt,
                                           double dist,
                                           uint64_t *numelems,
                                           int fields,
                                           int64_t limit);
 
  LWT_ELEMID (*getNextEdgeId) (
      const LWT_BE_TOPOLOGY* topo
  );
 
  int (*insertEdges)(const LWT_BE_TOPOLOGY *topo, LWT_ISO_EDGE *edges, uint64_t numelems);
 
  int (*updateEdges) (
      const LWT_BE_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
  );
 
  LWT_ISO_FACE *(*getFaceById)(const LWT_BE_TOPOLOGY *topo, const LWT_ELEMID *ids, uint64_t *numelems, int fields);
 
  int (*updateTopoGeomEdgeSplit) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID split_edge, LWT_ELEMID new_edge1, LWT_ELEMID new_edge2
  );
 
  int (*deleteEdges) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ISO_EDGE* sel_edge, int sel_fields
  );
 
  LWT_ISO_NODE *(
      *getNodeWithinBox2D)(const LWT_BE_TOPOLOGY *topo, const GBOX *box, uint64_t *numelems, int fields, int limit);
 
  LWT_ISO_EDGE *(
      *getEdgeWithinBox2D)(const LWT_BE_TOPOLOGY *topo, const GBOX *box, uint64_t *numelems, int fields, int limit);
 
  LWT_ISO_EDGE *(*getEdgeByNode)(const LWT_BE_TOPOLOGY *topo, const LWT_ELEMID *ids, uint64_t *numelems, int fields);
 
  int (*updateNodes) (
      const LWT_BE_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
  );
 
  int (*updateTopoGeomFaceSplit) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID split_face, LWT_ELEMID new_face1, LWT_ELEMID new_face2
  );
 
  int (*insertFaces)(const LWT_BE_TOPOLOGY *topo, LWT_ISO_FACE *faces, uint64_t numelems);
 
  uint64_t (*updateFacesById) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ISO_FACE* faces, uint64_t numfaces
  );
 
  /*
   * Get the ordered list edge visited by a side walk
   *
   * The walk starts from the side of an edge and stops when
   * either the max number of visited edges OR the starting
   * position is reached. The output list never includes a
   * duplicated signed edge identifier.
   *
   * It is expected that the walk uses the "next_left" and "next_right"
   * attributes of ISO edges to perform the walk (rather than recomputing
   * the turns at each node).
   *
   * @param topo the topology to operate on
   * @param edge walk start position and direction:
   *             abs value identifies the edge, sign expresses
   *             side (left if positive, right if negative)
   *             and direction (forward if positive, backward if negative).
   * @param numedges output parameter, gets the number of edges visited
   *
   * @param limit max edges to return (to avoid an infinite loop in case
   *              of a corrupted topology). 0 is for unlimited.
   *              The function is expected to error out if the limit is hit.
   *
   * @return an array of signed edge identifiers (positive edges being
   *         walked in their direction, negative ones in opposite) or
   *         NULL on error (@see lastErrorMessage)
   */
  LWT_ELEMID *(*getRingEdges)(const LWT_BE_TOPOLOGY *topo, LWT_ELEMID edge, uint64_t *numedges, int limit);
 
  int (*updateEdgesById)(const LWT_BE_TOPOLOGY *topo, const LWT_ISO_EDGE *edges, uint64_t numedges, int upd_fields);
 
  LWT_ISO_EDGE *(*getEdgeByFace)(const LWT_BE_TOPOLOGY *topo,
                                 const LWT_ELEMID *ids,
                                 uint64_t *numelems,
                                 int fields,
                                 const GBOX *box);
 
  LWT_ISO_NODE *(*getNodeByFace)(const LWT_BE_TOPOLOGY *topo,
                                 const LWT_ELEMID *faces,
                                 uint64_t *numelems,
                                 int fields,
                                 const GBOX *box);
 
  int (*updateNodesById)(const LWT_BE_TOPOLOGY *topo, const LWT_ISO_NODE *nodes, uint64_t numnodes, int upd_fields);
 
  int (*deleteFacesById)(const LWT_BE_TOPOLOGY *topo, const LWT_ELEMID *ids, uint64_t numelems);
 
  int (*topoGetSRID) (
      const LWT_BE_TOPOLOGY* topo
  );
 
  double (*topoGetPrecision) (
      const LWT_BE_TOPOLOGY* topo
  );
 
  int (*topoHasZ) (
      const LWT_BE_TOPOLOGY* topo
  );
 
  int (*deleteNodesById)(const LWT_BE_TOPOLOGY *topo, const LWT_ELEMID *ids, uint64_t numelems);
 
  int (*checkTopoGeomRemEdge) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID rem_edge,
      LWT_ELEMID face_left,
      LWT_ELEMID face_right
  );
 
  int (*updateTopoGeomFaceHeal) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID face1, LWT_ELEMID face2, LWT_ELEMID newface
  );
 
  int (*checkTopoGeomRemNode) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID rem_node,
      LWT_ELEMID e1,
      LWT_ELEMID e2
  );
 
  int (*updateTopoGeomEdgeHeal) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID edge1, LWT_ELEMID edge2, LWT_ELEMID newedge
  );
 
  LWT_ISO_FACE *(*getFaceWithinBox2D)(const LWT_BE_TOPOLOGY *topo,
                                      const GBOX *box,
                                      uint64_t *numelems,
                                      int fields,
                                      int limit);
 
  int (*checkTopoGeomRemIsoNode) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID rem_node
  );
 
  int (*checkTopoGeomRemIsoEdge) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ELEMID rem_edge
  );
 
 
  LWT_ISO_EDGE *(*getClosestEdge)(const LWT_BE_TOPOLOGY *topo,
                                           const LWPOINT *pt,
                                           uint64_t *numelems,
                                           int fields);
 
  GBOX *(*computeFaceMBR)(const LWT_BE_TOPOLOGY *topo, LWT_ELEMID face);
 
} LWT_BE_CALLBACKS;
 
 
LWT_BE_IFACE* lwt_CreateBackendIface(const LWT_BE_DATA* data);
 
void lwt_BackendIfaceRegisterCallbacks(LWT_BE_IFACE* iface, const LWT_BE_CALLBACKS* cb);
 
void lwt_FreeBackendIface(LWT_BE_IFACE* iface);
 
/********************************************************************
 *
 * End of BE interface
 *
 *******************************************************************/
 
typedef enum LWT_TOPOERR_TYPE_T {
  LWT_TOPOERR_EDGE_CROSSES_NODE,
  LWT_TOPOERR_EDGE_INVALID,
  LWT_TOPOERR_EDGE_NOT_SIMPLE,
  LWT_TOPOERR_EDGE_CROSSES_EDGE,
  LWT_TOPOERR_EDGE_STARTNODE_MISMATCH,
  LWT_TOPOERR_EDGE_ENDNODE_MISMATCH,
  LWT_TOPOERR_FACE_WITHOUT_EDGES,
  LWT_TOPOERR_FACE_HAS_NO_RINGS,
  LWT_TOPOERR_FACE_OVERLAPS_FACE,
  LWT_TOPOERR_FACE_WITHIN_FACE
} LWT_TOPOERR_TYPE;
 
typedef struct LWT_TOPOERR_T {
  LWT_TOPOERR_TYPE err;
  LWT_ELEMID elem1;
  LWT_ELEMID elem2;
} LWT_TOPOERR;
 
/*
 * Topology functions
 */
 
typedef struct LWT_TOPOLOGY_T LWT_TOPOLOGY;
 
 
/*******************************************************************
 *
 * Non-ISO signatures here
 *
 *******************************************************************/
 
LWT_TOPOLOGY *lwt_CreateTopology(LWT_BE_IFACE *iface, const char *name, int32_t srid, double prec, int hasz);
 
LWT_TOPOLOGY *lwt_LoadTopology(LWT_BE_IFACE *iface, const char *name);
 
void lwt_DropTopology(LWT_TOPOLOGY* topo);
 
void lwt_FreeTopology(LWT_TOPOLOGY* topo);
 
LWT_ELEMID lwt_GetNodeByPoint(LWT_TOPOLOGY *topo, LWPOINT *pt, double tol);
 
LWT_ELEMID lwt_GetEdgeByPoint(LWT_TOPOLOGY *topo, LWPOINT *pt, double tol);
 
LWT_ELEMID lwt_GetFaceByPoint(LWT_TOPOLOGY *topo, const LWPOINT *pt, double tol);
 
LWT_ELEMID lwt_GetFaceContainingPoint(LWT_TOPOLOGY* topo, const LWPOINT* pt);
 
 
 
/*******************************************************************
 *
 * Topology population (non-ISO)
 *
 *******************************************************************/
 
LWT_ELEMID lwt_AddPoint(LWT_TOPOLOGY* topo, LWPOINT* point, double tol);
 
LWT_ELEMID* lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol,
                        int* nedges, int max_edges);
 
LWT_ELEMID* lwt_AddLineNoFace(LWT_TOPOLOGY* topo, LWLINE* line, double tol,
                        int* nedges);
 
/*
 * Determine and register all topology faces:
 *
 *  - Determines which faces are generated by existing
 *    edges.
 *  - Creates face records with correct mbr
 *  - Update edge left/right face attributes
 *
 *  Precondition:
 *     - the topology edges are correctly linked
 *     - there are no faces registered in the topology
 *
 *  Postconditions:
 *     - all left/right face attributes of edges
 *       reference faces with correct mbr.
 *
 *  Notes:
 *     - does not attempt to assign isolated nodes to their
 *       containing faces
 *     - does not remove existing face records
 *     - loads in memory all the topology edges
 *
 * @param topo the topology to operate on
 *
 * @return 0 on success, -1 on error
 *         (librtgeom error handler will be invoked with error
 *         message)
 */
int lwt_Polygonize(LWT_TOPOLOGY* topo);
 
LWT_ELEMID* lwt_AddPolygon(LWT_TOPOLOGY* topo, LWPOLY* poly, double tol,
                        int* nfaces);
 
void lwt_LoadGeometry(LWT_TOPOLOGY* topo, LWGEOM* geom, double tol);
 
/*******************************************************************
 *
 * ISO signatures here
 *
 *******************************************************************/
 
void lwt_CreateTopoGeo(LWT_TOPOLOGY* topo, LWGEOM *geom);
 
LWT_ELEMID lwt_AddIsoNode(LWT_TOPOLOGY* topo, LWT_ELEMID face,
                          LWPOINT* pt, int skipChecks);
 
int lwt_MoveIsoNode(LWT_TOPOLOGY* topo,
                    LWT_ELEMID node, LWPOINT* pt);
 
int lwt_RemoveIsoNode(LWT_TOPOLOGY* topo, LWT_ELEMID node);
 
int lwt_RemIsoEdge(LWT_TOPOLOGY* topo, LWT_ELEMID edge);
 
LWT_ELEMID lwt_AddIsoEdge(LWT_TOPOLOGY* topo,
                          LWT_ELEMID startNode, LWT_ELEMID endNode,
                          const LWLINE *geom);
 
LWT_ELEMID lwt_AddEdgeModFace(LWT_TOPOLOGY* topo,
                              LWT_ELEMID start_node, LWT_ELEMID end_node,
                              LWLINE *geom, int skipChecks);
 
LWT_ELEMID lwt_AddEdgeNewFaces(LWT_TOPOLOGY* topo,
                              LWT_ELEMID start_node, LWT_ELEMID end_node,
                              LWLINE *geom, int skipChecks);
 
LWT_ELEMID lwt_RemEdgeNewFace(LWT_TOPOLOGY* topo, LWT_ELEMID edge);
 
LWT_ELEMID lwt_RemEdgeModFace(LWT_TOPOLOGY* topo, LWT_ELEMID edge);
 
int lwt_ChangeEdgeGeom(LWT_TOPOLOGY* topo, LWT_ELEMID edge, LWLINE* curve);
 
LWT_ELEMID lwt_ModEdgeSplit(LWT_TOPOLOGY* topo, LWT_ELEMID edge, LWPOINT* pt, int skipChecks);
 
LWT_ELEMID lwt_NewEdgesSplit(LWT_TOPOLOGY* topo, LWT_ELEMID edge, LWPOINT* pt, int skipChecks);
 
LWT_ELEMID lwt_ModEdgeHeal(LWT_TOPOLOGY* topo, LWT_ELEMID e1, LWT_ELEMID e2);
 
LWT_ELEMID lwt_NewEdgeHeal(LWT_TOPOLOGY* topo, LWT_ELEMID e1, LWT_ELEMID e2);
 
int lwt_GetFaceEdges(LWT_TOPOLOGY* topo, LWT_ELEMID face, LWT_ELEMID **edges);
 
LWGEOM* lwt_GetFaceGeometry(LWT_TOPOLOGY* topo, LWT_ELEMID face);
 
#endif /* LIBLWGEOM_TOPO_H */