316 lines
8.9 KiB
C++
316 lines
8.9 KiB
C++
/**********************************************************************
|
|
*
|
|
* GEOS - Geometry Engine Open Source
|
|
* http://geos.osgeo.org
|
|
*
|
|
* Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
|
|
*
|
|
* This is free software; you can redistribute and/or modify it under
|
|
* the terms of the GNU Lesser General Public Licence as published
|
|
* by the Free Software Foundation.
|
|
* See the COPYING file for more information.
|
|
*
|
|
**********************************************************************/
|
|
|
|
|
|
#pragma once
|
|
|
|
#include <geos/export.h>
|
|
#include <string>
|
|
#include <cassert>
|
|
#include <geos/geom/Coordinate.h>
|
|
|
|
namespace geos {
|
|
namespace edgegraph { // geos.edgegraph
|
|
|
|
/**
|
|
* Represents a directed component of an edge in an {@link EdgeGraph}.
|
|
* HalfEdges link vertices whose locations are defined by {@link geom::Coordinate}s.
|
|
* HalfEdges start at an origin vertex,
|
|
* and terminate at a destination vertex.
|
|
* HalfEdges always occur in symmetric pairs, with the {@link sym()} method
|
|
* giving access to the oppositely-oriented component.
|
|
* HalfEdges and the methods on them form an edge algebra,
|
|
* which can be used to traverse and query the topology
|
|
* of the graph formed by the edges.
|
|
*
|
|
* To support graphs where the edges are sequences of coordinates
|
|
* each edge may also have a direction point supplied.
|
|
* This is used to determine the ordering
|
|
* of the edges around the origin.
|
|
* HalfEdges with the same origin are ordered
|
|
* so that the ring of edges formed by them is oriented CCW.
|
|
*
|
|
* By design HalfEdges carry minimal information
|
|
* about the actual usage of the graph they represent.
|
|
* They can be subclassed to carry more information if required.
|
|
*
|
|
* HalfEdges form a complete and consistent data structure by themselves,
|
|
* but an {@link EdgeGraph} is useful to allow retrieving edges
|
|
* by vertex and edge location, as well as ensuring
|
|
* edges are created and linked appropriately.
|
|
*
|
|
* @author Martin Davis
|
|
*
|
|
*/
|
|
class GEOS_DLL HalfEdge {
|
|
|
|
private:
|
|
|
|
/* members */
|
|
geom::CoordinateXYZM m_orig;
|
|
HalfEdge* m_sym;
|
|
HalfEdge* m_next;
|
|
|
|
|
|
/**
|
|
* Sets the symmetric (opposite) edge to this edge.
|
|
*
|
|
* @param e the sym edge to set
|
|
*/
|
|
void setSym(HalfEdge* e) { m_sym = e; };
|
|
|
|
/**
|
|
* Finds the insertion edge for a edge
|
|
* being added to this origin,
|
|
* ensuring that the star of edges
|
|
* around the origin remains fully CCW.
|
|
*
|
|
* @param eAdd the edge being added
|
|
* @return the edge to insert after
|
|
*/
|
|
HalfEdge* insertionEdge(HalfEdge* eAdd);
|
|
|
|
/**
|
|
* Insert an edge with the same origin after this one.
|
|
* Assumes that the inserted edge is in the correct
|
|
* position around the ring.
|
|
*
|
|
* @param e the edge to insert (with same origin)
|
|
*/
|
|
void insertAfter(HalfEdge* e);
|
|
|
|
/**
|
|
* Finds the lowest edge around the origin,
|
|
* using the standard edge ordering.
|
|
*
|
|
* @return the lowest edge around the origin
|
|
*/
|
|
const HalfEdge* findLowest() const;
|
|
|
|
protected:
|
|
|
|
/**
|
|
* Gets the direction point of this edge.
|
|
* In the base case this is the dest coordinate
|
|
* of the edge.
|
|
* Subclasses may override to
|
|
* allow a HalfEdge to represent an edge with more than two coordinates.
|
|
*
|
|
* @return the direction point for the edge
|
|
*/
|
|
virtual const geom::CoordinateXYZM& directionPt() const { return dest(); };
|
|
|
|
|
|
public:
|
|
|
|
/**
|
|
* Creates a half-edge originating from a given coordinate.
|
|
*
|
|
* @param p_orig the origin coordinate
|
|
*/
|
|
HalfEdge(const geom::CoordinateXYZM& p_orig) :
|
|
m_orig(p_orig)
|
|
{};
|
|
|
|
virtual ~HalfEdge() {};
|
|
|
|
/**
|
|
* Creates a HalfEge pair, using the HalfEdge type of the graph subclass.
|
|
*
|
|
* @param p0 a vertex coordinate
|
|
* @param p1 a vertex coordinate
|
|
* @return the HalfEdge with origin at p0
|
|
*/
|
|
static HalfEdge* create(const geom::CoordinateXYZM& p0, const geom::CoordinateXYZM& p1);
|
|
|
|
/**
|
|
* Links this edge with its sym (opposite) edge.
|
|
* This must be done for each pair of edges created.
|
|
*
|
|
* @param p_sym the sym edge to link.
|
|
*/
|
|
void link(HalfEdge* p_sym);
|
|
|
|
/**
|
|
* Gets the origin coordinate of this edge.
|
|
*
|
|
* @return the origin coordinate
|
|
*/
|
|
const geom::CoordinateXYZM& orig() const { return m_orig; };
|
|
|
|
/**
|
|
* Gets the destination coordinate of this edge.
|
|
*
|
|
* @return the destination coordinate
|
|
*/
|
|
const geom::CoordinateXYZM& dest() const { return m_sym->m_orig; }
|
|
|
|
/**
|
|
* The X component of the direction vector.
|
|
*
|
|
* @return the X component of the direction vector
|
|
*/
|
|
double directionX() const { return directionPt().x - m_orig.x; }
|
|
|
|
/**
|
|
* The Y component of the direction vector.
|
|
*
|
|
* @return the Y component of the direction vector
|
|
*/
|
|
double directionY() const { return directionPt().y - m_orig.y; }
|
|
|
|
/**
|
|
* Gets the symmetric pair edge of this edge.
|
|
*
|
|
* @return the symmetric pair edge
|
|
*/
|
|
HalfEdge* sym() const { return m_sym; };
|
|
|
|
/**
|
|
* Gets the next edge CCW around the
|
|
* destination vertex of this edge,
|
|
* with the dest vertex as its origin.
|
|
* If the vertex has degree 1 then this is the <b>sym</b> edge.
|
|
*
|
|
* @return the next edge
|
|
*/
|
|
HalfEdge* next() const { return m_next; };
|
|
|
|
/**
|
|
* Gets the edge previous to this one
|
|
* (with dest being the same as this orig).
|
|
*
|
|
* It is always true that e.next().prev() == e
|
|
*
|
|
* Note that this requires a scan of the origin edges,
|
|
* so may not be efficient for some uses.
|
|
*
|
|
* @return the previous edge to this one
|
|
*/
|
|
HalfEdge* prev() const;
|
|
|
|
/**
|
|
* Gets the next edge CCW around the origin of this edge,
|
|
* with the same origin.
|
|
*
|
|
* e.oNext() is equal to e.sym().next()
|
|
*
|
|
* @return the next edge around the origin
|
|
*/
|
|
HalfEdge* oNext() const { return m_sym->m_next; };
|
|
|
|
/**
|
|
* Sets the next edge CCW around the destination vertex of this edge.
|
|
*
|
|
* @param e the next edge
|
|
*/
|
|
void setNext(HalfEdge* e) { m_next = e; };
|
|
|
|
/**
|
|
* Finds the edge starting at the origin of this edge
|
|
* with the given dest vertex,
|
|
* if any.
|
|
*
|
|
* @param dest the dest vertex to search for
|
|
* @return the edge with the required dest vertex, if it exists,
|
|
* or null
|
|
*/
|
|
HalfEdge* find(const geom::CoordinateXY& dest);
|
|
|
|
/**
|
|
* Tests whether this edge has the given orig and dest vertices.
|
|
*
|
|
* @param p0 the origin vertex to test
|
|
* @param p1 the destination vertex to test
|
|
* @return true if the vertices are equal to the ones of this edge
|
|
*/
|
|
bool equals(const geom::CoordinateXY& p0, const geom::CoordinateXY& p1) const;
|
|
|
|
/**
|
|
* Inserts an edge
|
|
* into the ring of edges around the origin vertex of this edge,
|
|
* ensuring that the edges remain ordered CCW.
|
|
* The inserted edge must have the same origin as this edge.
|
|
*
|
|
* @param eAdd the edge to insert
|
|
*/
|
|
void insert(HalfEdge* eAdd);
|
|
|
|
/**
|
|
* Tests whether the edges around the origin
|
|
* are sorted correctly.
|
|
* Note that edges must be strictly increasing,
|
|
* which implies no two edges can have the same direction point.
|
|
*
|
|
* @return true if the origin edges are sorted correctly
|
|
*/
|
|
bool isEdgesSorted() const;
|
|
|
|
/**
|
|
* Implements the total order relation:
|
|
*
|
|
* The angle of edge a is greater than the angle of edge b,
|
|
* where the angle of an edge is the angle made by
|
|
* the first segment of the edge with the positive x-axis
|
|
*
|
|
* When applied to a list of edges originating at the same point,
|
|
* this produces a CCW ordering of the edges around the point.
|
|
*
|
|
* Using the obvious algorithm of computing the angle is not robust,
|
|
* since the angle calculation is susceptible to roundoff error.
|
|
* A robust algorithm is:
|
|
*
|
|
* * First, compare the quadrants the edge vectors lie in.
|
|
* If the quadrants are different,
|
|
* it is trivial to determine which edge has a greater angle.
|
|
*
|
|
* * if the vectors lie in the same quadrant, the
|
|
* geom::Orientation::index() function
|
|
* can be used to determine the relative orientation of the vectors.
|
|
*/
|
|
int compareAngularDirection(const HalfEdge* e) const;
|
|
int compareTo(const HalfEdge* e) const { return compareAngularDirection(e); };
|
|
|
|
/**
|
|
* Computes the degree of the origin vertex.
|
|
* The degree is the number of edges
|
|
* originating from the vertex.
|
|
*
|
|
* @return the degree of the origin vertex
|
|
*/
|
|
int degree();
|
|
|
|
/**
|
|
* Finds the first node previous to this edge, if any.
|
|
* A node has degree <> 2.
|
|
* If no such node exists (i.e. the edge is part of a ring)
|
|
* then null is returned.
|
|
*
|
|
* @return an edge originating at the node prior to this edge, if any,
|
|
* or null if no node exists
|
|
*/
|
|
HalfEdge* prevNode();
|
|
|
|
friend std::ostream& operator<< (std::ostream& os, const HalfEdge& el);
|
|
static void toStringNode(const HalfEdge* he, std::ostream& os);
|
|
|
|
};
|
|
|
|
|
|
} // namespace geos.edgegraph
|
|
} // namespace geos
|
|
|
|
|
|
|