10 : tds(), vertices(), neighbors(), poly_n(-1)
19 : tds(that.tds), vertices(), neighbors(), poly_n(that.poly_n)
24 auto vi =
tds.vertices_begin();
25 auto vend =
tds.vertices_end();
26 for( ; vi != vend; ++vi) {
30 else if (vi->pindex >= 0)
81 e =
tds.mirror_edge(e);
100 Q_ASSERT(i>=0 && i <
vertices.size());
132 for (
int i=
vertices.size()-1; i >= sz; --i)
203 f = e.first->neighbor(2);
211 while((v2->offset != 0.0) && (v2->offset < x)) {
222 Q_ASSERT(
tds.is_valid());
230 return Segment(v1->pindex,v2->pindex);
283 Q_ASSERT(v->is_valid());
284 Q_ASSERT(v->face()->is_valid());
285 Q_ASSERT(v->face()->has_vertex(v));
286 Q_ASSERT(
tds.is_valid());
294 v->setData(p,
size()-1,-1,x);
321 e =
tds.mirror_edge(e);
324 Edge(e.first,e.first->cw(e.second)));
339 f = f->neighbor(e.second);
345 if (vv.first->pindex==i2)
347 Q_ASSERT(vv.first->pindex==i1);
348 Q_ASSERT(vv.second->pindex==i2);
353 Edge(f,f->index(v1)));
370 if (
tds.is_edge(v1,v2, result.first, i)) {
371 result.second = result.first->neighbor(i);
378 return tds.incident_faces(v);
382 e =
tds.mirror_edge(e);
383 return e.first->vertex(e.second);
392 e =
tds.mirror_edge(e);
393 c = e.first->vertex(e.second);
404 bool ok =
tds.is_edge(vi,vj, e.first,e.second);
407 e =
tds.mirror_edge(e);
415 int i1 = e.first->ccw(e.second);
416 int i2 = e.first->cw(e.second);
418 e.first->vertex(i2));
422 auto v =
tds.vertices_begin();
423 auto vend =
tds.vertices_end();
424 for( ; v != vend; ++v)
429 auto v =
tds.vertices_begin();
430 auto vend =
tds.vertices_end();
431 for( ; v != vend; ++v)
442 if (
tds.is_edge(v1,v2, e.first,e.second))
444 result.first = e.first->vertex(e.second);
445 e =
tds.mirror_edge(e);
446 result.second = e.first->vertex(e.second);
465 TDS::Face_handle f =
tds.create_face(va,vb,vc);
468 Q_ASSERT(f != TDS::Face_handle());
498 Q_ASSERT(s.first>=0);
499 Q_ASSERT(s.second>=0);
512 Q_ASSERT(first_edge <= 2);
516 TDS::Vertex_iterator vit =
tds.vertices_begin();
519 Q_ASSERT(
tds.is_valid());
535 tds.set_adjacency(e.first,e.second, e2.first,e2.second);
547 Q_ASSERT(f->has_vertex(v1));
548 Q_ASSERT(f->has_vertex(v2));
550 for(
int i=0; i < 3; ++i) {
552 if (v3!=v1 && v3!=v2)
561 return third_vertex(f, (*
this)[s.first], (*
this)[s.second]);
568 && PolygonShortestPaths::halfplaneTest<double>(f->vertex(0), f->vertex(1), f->vertex(2)) < 0
569 && PolygonShortestPaths::halfplaneTest<double>(f->vertex(1), f->vertex(2), f->vertex(0)) < 0
570 && PolygonShortestPaths::halfplaneTest<double>(f->vertex(2), f->vertex(0), f->vertex(1)) < 0;
592 CGAL::Triangulation_ds_vertex_base_2<TDS>(),
593 pindex(pi), dindex(-1), offset(offs),
594 prev(nullptr), target(nullptr),
595 L(),R(),B(), LR(),BR(),RR()
609 return f->vertex((i+1)%3);
615 return f->vertex((i+2)%3);
651 Q_ASSERT(
tds.number_of_vertices()==that.
tds.number_of_vertices());
652 Q_ASSERT(
tds.number_of_faces()==that.
tds.number_of_faces());
653 Q_ASSERT(
tds.number_of_edges()==that.
tds.number_of_edges());
656 for(
int i=0; i <
vertices.size(); ++i)
665 auto v1i =
tds.vertices_begin();
666 auto v1end =
tds.vertices_end();
674 for( ; v1i != v1end; ++v1i)
675 if (v1i->pindex >= 0)
676 Q_ASSERT(v1i ==
vertices[v1i->pindex]);
678 Q_ASSERT(v1i==v1end);
683 template<
typename TDS>
686 Q_ASSERT(this->pindex == that.
pindex);
691 Q_ASSERT(this->dindex == that.dindex);
692 Q_ASSERT(this->offset == that.offset);
702 for(
auto t=tbegin; t!=tend; ++t) {
703 if (t!=tbegin) out <<
",";
712 <<f->vertex(0)->pindex<<
"-" 713 <<f->vertex(1)->pindex<<
"-" 714 <<f->vertex(2)->pindex<<
"]";
Represents a polygon line segment from node i to j.
void complement()
after all faces have been added, create the complementary "outer" edges (connected to the south-pole)...
void swap(gpuword **A, gpuword **B)
NeighborMap neighbors
Keeps track of diagonals and their neighborhood during construction.
void setPolygonSize(int n)
set number of polygon vertexes
static Vertex_handle vertex1(Edge e)
Edge edge(int i, int j) const
construct an edge from two vertexes
TwoVertices adjacentVertices(Segment s) const
std::vector< frechet::reach::Placement > Placements
a list of Placement objects
static Vertex_handle third_vertex(Face_handle f, Vertex_handle v1, Vertex_handle v2)
given two vertexes and a face, find the third vertex of the triangle
std::pair< Vertex_handle, Vertex_handle > VertexPair
a pair of vertexes
Vertex_handle addTargetVertex(const frechet::reach::Placement *p)
add a vertex for computing valid placements
Edge_iterator(TDS::Edge_iterator i)
default constructor
global definitions for all algorithms.
void mirror(Edge &e) const
flip the direction of an edge. Keep in mind that Edge object are desribed as a Face + opposite vertex...
static Segment segment(Edge e)
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
Face_circulator incidentFaces(Vertex_handle v) const
a circular (never-ending) iterator that traverses all faces incident to a given vertex.
bool assertEquals(const Vertex_base &that)
debug assertion
~Triangulation()
destructor
static bool is_inner_face(Face_handle f)
EdgePair adjacentEdges(Edge e) const
TDS::Face_handle Face_handle
handle to a triangulation face (handles are managed by TDS base class)
static bool is_polygon_edge(Edge e)
int thirdVertex(int a, int b) const
given two vertexes, find the third vertex to complement a triangle
int pindex
Index of polygon vertex (if this object refers to a polygon vertex; invalid for extra points)
void clearTargets()
clear targets for shortest-path tree search
Vertex_handle createVertex(const Point &p, int i)
create a new triangulation vertex
void resize(int sz)
reset number of vertexes in triangulation
static Vertex_handle vertex2(Edge e)
Vertex_handle addVertex(double w)
add a triangulation vertex on the edge of the polygon (does not correspond to a polygon vertex)
Vertex_handle vertex2() const
static bool is_diagonal(Edge e)
FacePair adjacentFaces(Segment s) const
void addTargetVertices(const frechet::reach::Placements &p)
add vertexes for computing valid placements
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
Vertex_handle vertex1() const
void createFace(int a, int b, int c)
insert a new face. Caller is responsible for keeping the triangulation in a consistent state....
static bool is_south_pole(Vertex_handle v)
static const int SOUTH_POLE_INDEX
artifical vertex used by Triangulation
base class for vertexes in a Triangulation Data Structure.
Point between(Point p, Point q, double w)
compute a point on a line segment
bool is_ccw_face(Face_handle f)
bool is_outer_edge() const
std::pair< Face_handle, Face_handle > FacePair
a pair of faces
std::pair< Edge, Edge > EdgePair
a pair of edges
void linkNeighbors(Segment s, Edge e)
keep track of neighboring faces during construction of the triangulation.
Edge_iterator edges_end() const
Edge_iterator edges_begin() const
bool assertEquals(const Triangulation &that) const
equality assertion for debugging
Vertex_handle insertVertexOnEdge(double x)
split an edge into two
~Vertex_base()
destructor (empty, actually)
std::pair< Vertex_handle, Vertex_handle > TwoVertices
a pair of vertex handles
placement of a diagonal point in free-space diagram When calculating valid placements in [buchin06]
Vertex_base()
empty constructore; creates an invalid vertex
Vertex_handle oppositeVertex(Edge e) const
the second vertex opposite to an edge. Keep in mind that Edge object are desribed as a Face + opposit...
TDS tds
CGAL Triangulation Data Structure.
CGAL::Triangulation_data_structure_2< Vertex_base<>, CGAL::Triangulation_ds_face_base_2<> > TDS
Triangulation Data Structure. Instantiates CGAL::Triangulation_data_structure_2 with our customized V...
VertexPair incidentVertexes(Edge e) const
TDS::Face_circulator Face_circulator
a circulating iterator
TDS::Vertex_handle south_pole
a special vertex that completes the TDS structure
Interval fs
Free-Space Interval.
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
bool is_polygon_edge() const
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
static bool is_outer_face(Face_handle f)
static bool is_outer_edge(Edge e)
void clearPredecessors()
used during shortest-paths computation: reset shortest-path tree information on all vertexes
Triangulation(int capacity=-1)
default constructor
Vertex_handle operator[](int i)
edge iterator. Traverses all edges of the triangulation. Derives from TDS::Edge_iterator and supplies...
std::ostream & operator<<(std::ostream &out, const frechet::poly::CgalPolygon &poly)
print operator (for debugging)
int poly_n
polygon size, number of vertexes in polyong
void removeVertexFromEdge(int index)
remove a vertex