QuadEdge.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2012 Excensus LLC.
* Copyright (C) 2019 Daniel Baston
*
* This is free software; you can redistribute and/or modify it under
* the terms of the GNU Lesser General Licence as published
* by the Free Software Foundation.
* See the COPYING file for more information.
*
**********************************************************************
*
* Last port: triangulate/quadedge/QuadEdge.java r524
*
**********************************************************************/
#pragma once
#include <memory>
#include <geos/triangulate/quadedge/Vertex.h>
#include <geos/geom/LineSegment.h>
namespace geos {
namespace triangulate { //geos.triangulate
namespace quadedge { //geos.triangulate.quadedge
class GEOS_DLL QuadEdgeQuartet;
class GEOS_DLL QuadEdge {
friend class QuadEdgeQuartet;
public:
static QuadEdge* makeEdge(const Vertex& o, const Vertex & d, std::deque<QuadEdgeQuartet> & edges);
static QuadEdge* connect(QuadEdge& a, QuadEdge& b, std::deque<QuadEdgeQuartet> & edges);
static void splice(QuadEdge& a, QuadEdge& b);
static void swap(QuadEdge& e);
private:
Vertex vertex; // The vertex that this edge represents
QuadEdge* next; // A reference to a connected edge
int8_t num; // the position of the QuadEdge in the quartet (0-3)
bool isAlive;
bool visited;
explicit QuadEdge(int8_t _num) :
next(nullptr),
num(_num),
isAlive(true),
visited(false) {
}
public:
const QuadEdge& getPrimary();
void remove();
inline bool
isLive() const
{
return isAlive;
}
inline bool
isVisited() const
{
return visited;
}
inline void
setVisited(bool v) {
visited = v;
}
inline void
setNext(QuadEdge* p_next)
{
this->next = p_next;
}
/***************************************************************************
* QuadEdge Algebra
***************************************************************************
*/
inline const QuadEdge&
rot() const
{
return (num < 3) ? *(this + 1) : *(this - 3);
}
inline QuadEdge&
rot()
{
return (num < 3) ? *(this + 1) : *(this - 3);
}
inline const QuadEdge&
invRot() const
{
return (num > 0) ? *(this - 1) : *(this + 3);
}
inline QuadEdge&
invRot()
{
return (num > 0) ? *(this - 1) : *(this + 3);
}
inline const QuadEdge&
sym() const
{
return (num < 2) ? *(this + 2) : *(this - 2);
}
inline QuadEdge&
sym()
{
return (num < 2) ? *(this + 2) : *(this - 2);
}
inline const QuadEdge&
oNext() const
{
return *next;
}
inline QuadEdge&
oNext()
{
return *next;
}
inline const QuadEdge&
oPrev() const
{
return rot().oNext().rot();
}
inline QuadEdge&
oPrev()
{
return rot().oNext().rot();
}
inline const QuadEdge&
dNext() const
{
return sym().oNext().sym();
}
inline const QuadEdge&
dPrev() const
{
return invRot().oNext().invRot();
}
inline QuadEdge&
dPrev()
{
return invRot().oNext().invRot();
}
inline const QuadEdge&
lNext() const
{
return invRot().oNext().rot();
}
inline QuadEdge&
lNext()
{
return invRot().oNext().rot();
}
inline const QuadEdge&
lPrev() const
{
return oNext().sym();
}
inline QuadEdge&
lPrev()
{
return oNext().sym();
}
inline const QuadEdge&
rNext() const
{
return rot().oNext().invRot();
}
inline const QuadEdge&
rPrev() const
{
return sym().oNext();
}
/***********************************************************************************************
* Data Access
**********************************************************************************************/
inline void
setOrig(const Vertex& o)
{
vertex = o;
}
inline void
setDest(const Vertex& d)
{
sym().setOrig(d);
}
const Vertex&
orig() const
{
return vertex;
}
const Vertex&
dest() const
{
return sym().orig();
}
inline double
getLength() const
{
return orig().getCoordinate().distance(dest().getCoordinate());
}
bool equalsNonOriented(const QuadEdge& qe) const;
bool equalsOriented(const QuadEdge& qe) const;
std::unique_ptr<geom::LineSegment> toLineSegment() const;
};
GEOS_DLL std::ostream& operator<< (std::ostream& os, const QuadEdge* e);
} //namespace geos.triangulate.quadedge
} //namespace geos.triangulate
} //namespace geos
geos::triangulate::quadedge::QuadEdge
A class that represents the edge data structure which implements the quadedge algebra.
Definition QuadEdge.h:53
geos::triangulate::quadedge::QuadEdge::getPrimary
const QuadEdge & getPrimary()
Gets the primary edge of this quadedge and its sym.
geos::triangulate::quadedge::QuadEdge::toLineSegment
std::unique_ptr< geom::LineSegment > toLineSegment() const
Creates a geom::LineSegment representing the geometry of this edge.
geos::triangulate::quadedge::QuadEdge::setOrig
void setOrig(const Vertex &o)
Sets the vertex for this edge's origin.
Definition QuadEdge.h:362
geos::triangulate::quadedge::QuadEdge::equalsOriented
bool equalsOriented(const QuadEdge &qe) const
Tests if this quadedge and another have the same line segment geometry with the same orientation.
geos::triangulate::quadedge::QuadEdge::makeEdge
static QuadEdge * makeEdge(const Vertex &o, const Vertex &d, std::deque< QuadEdgeQuartet > &edges)
Creates a new QuadEdge quartet from Vertex o to Vertex d.
geos::triangulate::quadedge::QuadEdge::setDest
void setDest(const Vertex &d)
Sets the vertex for this edge's destination.
Definition QuadEdge.h:373
geos::triangulate::quadedge::QuadEdge::connect
static QuadEdge * connect(QuadEdge &a, QuadEdge &b, std::deque< QuadEdgeQuartet > &edges)
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all thr...
geos::triangulate::quadedge::QuadEdge::dNext
const QuadEdge & dNext() const
Gets the next CCW edge around (into) the destination of this edge.
Definition QuadEdge.h:275
geos::triangulate::quadedge::QuadEdge::swap
static void swap(QuadEdge &e)
Turns an edge counterclockwise inside its enclosing quadrilateral.
geos::triangulate::quadedge::QuadEdge::dPrev
const QuadEdge & dPrev() const
Gets the next CW edge around (into) the destination of this edge.
Definition QuadEdge.h:286
geos::triangulate::quadedge::QuadEdge::rot
const QuadEdge & rot() const
Gets the dual of this edge, directed from its right to its left.
Definition QuadEdge.h:190
geos::triangulate::quadedge::QuadEdge::oPrev
const QuadEdge & oPrev() const
Gets the next CW edge around (from) the origin of this edge.
Definition QuadEdge.h:258
geos::triangulate::quadedge::QuadEdge::rNext
const QuadEdge & rNext() const
Gets the edge around the right face ccw following this edge.
Definition QuadEdge.h:337
geos::triangulate::quadedge::QuadEdge::remove
void remove()
Marks this quadedge as being deleted.
geos::triangulate::quadedge::QuadEdge::rPrev
const QuadEdge & rPrev() const
Gets the edge around the right face ccw before this edge.
Definition QuadEdge.h:348
geos::triangulate::quadedge::QuadEdge::isLive
bool isLive() const
Tests whether this edge has been deleted.
Definition QuadEdge.h:152
geos::triangulate::quadedge::QuadEdge::orig
const Vertex & orig() const
Gets the vertex for the edge's origin.
Definition QuadEdge.h:384
geos::triangulate::quadedge::QuadEdge::splice
static void splice(QuadEdge &a, QuadEdge &b)
Splices two edges together or apart.
geos::triangulate::quadedge::QuadEdge::getLength
double getLength() const
Gets the length of the geometry of this quadedge.
Definition QuadEdge.h:406
geos::triangulate::quadedge::QuadEdge::sym
const QuadEdge & sym() const
Gets the edge from the destination to the origin of this edge.
Definition QuadEdge.h:224
geos::triangulate::quadedge::QuadEdge::equalsNonOriented
bool equalsNonOriented(const QuadEdge &qe) const
Tests if this quadedge and another have the same line segment geometry, regardless of orientation.
geos::triangulate::quadedge::QuadEdge::dest
const Vertex & dest() const
Gets the vertex for the edge's destination.
Definition QuadEdge.h:395
geos::triangulate::quadedge::QuadEdge::lPrev
const QuadEdge & lPrev() const
Gets the CCW edge around the left face before this edge.
Definition QuadEdge.h:320
geos::triangulate::quadedge::QuadEdge::lNext
const QuadEdge & lNext() const
Gets the CCW edge around the left face following this edge.
Definition QuadEdge.h:303
geos::triangulate::quadedge::QuadEdge::oNext
const QuadEdge & oNext() const
Gets the next CCW edge around the origin of this edge.
Definition QuadEdge.h:241
geos::triangulate::quadedge::QuadEdge::setNext
void setNext(QuadEdge *p_next)
Sets the connected edge.
Definition QuadEdge.h:174
geos::triangulate::quadedge::QuadEdge::invRot
const QuadEdge & invRot() const
Gets the dual of this edge, directed from its left to its right.
Definition QuadEdge.h:207
geos::triangulate::quadedge::Vertex
Models a site (node) in a QuadEdgeSubdivision.
Definition Vertex.h:60
geos::triangulate::quadedge
Classes to implement a topological subdivision of quadeges, to support creating triangulations and Vo...
Definition ConcaveHull.h:33
geos::triangulate
Classes to compute Delaunay triangulations.
Definition ConcaveHull.h:32
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38