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-2017 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, int 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, int* numelems, int fields
  );
 
  LWT_ISO_NODE* (*getNodeWithinDistance2D) (
      const LWT_BE_TOPOLOGY* topo,
      const LWPOINT* pt, double dist, int* numelems,
      int fields, int limit
  );
 
  int (*insertNodes) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ISO_NODE* nodes,
      int numelems
  );
 
  LWT_ISO_EDGE* (*getEdgeById) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ELEMID* ids, int* numelems, int fields
  );
 
  LWT_ISO_EDGE* (*getEdgeWithinDistance2D) (
      const LWT_BE_TOPOLOGY* topo,
      const LWPOINT* pt, double dist, int* numelems,
      int fields, int limit
  );
 
  LWT_ELEMID (*getNextEdgeId) (
      const LWT_BE_TOPOLOGY* topo
  );
 
  int (*insertEdges) (
      const LWT_BE_TOPOLOGY* topo,
      LWT_ISO_EDGE* edges,
      int 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, int* numelems, int fields
  );
 
  LWT_ELEMID (*getFaceContainingPoint) (
      const LWT_BE_TOPOLOGY* topo,
      const LWPOINT* pt
  );
 
  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,
      int* numelems, int fields, int limit
  );
 
  LWT_ISO_EDGE* (*getEdgeWithinBox2D) (
      const LWT_BE_TOPOLOGY* topo,
      const GBOX* box,
      int* numelems, int fields, int limit
  );
 
  LWT_ISO_EDGE* (*getEdgeByNode) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ELEMID* ids, int* 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,
      int numelems
  );
 
  int (*updateFacesById) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ISO_FACE* faces, int 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, int *numedges, int limit
  );
 
  int (*updateEdgesById) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ISO_EDGE* edges, int numedges,
      int upd_fields
  );
 
  LWT_ISO_EDGE* (*getEdgeByFace) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ELEMID* ids, int* numelems, int fields,
      const GBOX *box
  );
 
  LWT_ISO_NODE* (*getNodeByFace) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ELEMID* faces, int* numelems, int fields,
      const GBOX *box
  );
 
  int (*updateNodesById) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ISO_NODE* nodes, int numnodes,
      int upd_fields
  );
 
  int (*deleteFacesById) (
      const LWT_BE_TOPOLOGY* topo,
      const LWT_ELEMID* ids,
      int 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,
      int 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,
      int* numelems, int fields, int limit
  );
 
} 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,
                        int 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, LWPOINT *pt, double tol);
 
 
/*******************************************************************
 *
 * 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);
 
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);
 
/*******************************************************************
 *
 * 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 */