28 Q_ASSERT(p.isClosed());
34 auto vend = p.cend()-1;
36 for(
int i=0; v!=vend; ++v,++i)
40 Q_ASSERT(
cgp.size()+1 == p.size());
45 return cgp.is_simple();
50 return cgp.is_convex();
55 return cgp.is_counterclockwise_oriented();
69 CGAL::greene_approx_convex_partition_2(
70 cgp.vertices_begin(),
cgp.vertices_end(),
71 std::back_inserter(
convex), traits);
76 CGAL::approx_convex_partition_2(
77 cgp.vertices_begin(),
cgp.vertices_end(),
78 std::back_inserter(
convex),
83 CGAL::optimal_convex_partition_2(
84 cgp.vertices_begin(),
cgp.vertices_end(),
85 std::back_inserter(
convex),
91 bool ok = CGAL::convex_partition_is_valid_2(
92 cgp.vertices_begin(),
cgp.vertices_end(),
98 }
catch (std::exception& error) {
99 std::cerr << error.what() << std::endl;
110 Q_ASSERT(!
convex.empty());
115 for(
const auto& part :
convex)
119 Q_ASSERT(! part.is_empty());
120 Q_ASSERT(part.size() >= 3);
122 auto v1 = part.vertices_begin();
124 auto vend = part.vertices_end();
126 for( ; v2!=vend; ++v1,++v2)
129 v2 = part.vertices_begin();
148 auto p =
cgp.vertices_begin();
150 auto end =
cgp.vertices_end();
153 for( ; q!=end; ++p,++q,++j) {
157 Q_ASSERT(p->i+1 == q->i);
165 Q_ASSERT(!
convex.empty());
166 CgalPolygonList::iterator i =
convex.begin();
167 CgalPolygonList::iterator iend =
convex.end();
184 if (poly.size() <= 2)
189 CgalPolygon::Vertex_circulator pbegin = poly.vertices_circulator();
190 CgalPolygon::Vertex_circulator p = pbegin;
197 }
while(++p != pbegin);
200 auto q = poly.vertices_begin();
201 while(q != poly.vertices_end())
207 return poly.size() > 2;
228 auto p0 = poly.vertices_begin();
231 if (poly.size() < 3) {
242 auto pend = poly.vertices_end();
247 for( ; p2!=pend; p1=p2++) {
256 Q_ASSERT(!
convex.empty());
267 for (
int i=0; i <
cgp.size(); ++i)
271 Q_ASSERT(v->pindex == i);
272 Q_ASSERT(v->pindex ==
cgp[i].i);
273 Q_ASSERT(
cgp[i].erase==
false);
281 CgalPolygon::Vertex_circulator pbegin =
cgp.vertices_circulator();
282 CgalPolygon::Vertex_circulator p = pbegin;
286 reflex.push_back(p->i);
287 }
while(++p != pbegin);
307 double A = (p.y()-a.y()) * (b.x()-a.x());
308 double B = (p.x()-a.x()) * (b.y()-a.y());
309 return A < B+tolerance;
322 :
super(x,y), i(ai), erase(false)
327 super::operator=(
super(p.x(),-p.y()));
332 CgalPoint::operator QPointF()
const 334 return QPointF(x(),-y());
341 auto pbegin = poly.vertices_begin();
342 auto pend = poly.vertices_end();
343 for(
auto p=pbegin; p != pend; ++p)
345 if (p != pbegin) out <<
",";
354 auto pbegin = polys.begin();
355 auto pend = polys.end();
356 for(
auto p=pbegin; p != pend; ++p)
358 if (p != pbegin) out <<
", ";
Represents a polygon line segment from node i to j.
CgalPolygon cgp
the polygon under examination
void complement()
after all faces have been added, create the complementary "outer" edges (connected to the south-pole)...
Greene's approximation algorithm.
static int distance(int a, int b, int n)
int decompose(DecompositionAlgorithm algo, bool verify)
compute a convex decomposition of the polygon. Store results in the member variable 'convex'.
int partition(Partition &partition) const
compute a list of sub-polygons, one for each convex part. This is mainly copying data to a more conve...
static bool create1Diagonal(int u, int v, int n, Partition &partition)
create a diagonal in a convex partition
void findReflexVertices(Polygon &poly, double tolerance=0.0)
find all reflex (concave) vertices.
global definitions for all algorithms.
PolygonUtilities()
empty constructor
bool is_edge(int n) const
bool assertStrictlySorted(const CgalPolygon &)
debug assertion
bool is_counter_clockwise()
Hertel and Mehlhorn's approximation algorithm.
CgalPolygonList convex
list of convex parts. created by decompose().
Vertex_handle createVertex(const Point &p, int i)
create a new triangulation vertex
int i
index of polygon vertex (-1 if not available)
int simplify()
Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges....
Greene's optimal algorithm.
std::list< CgalPolygon > CgalPolygonList
a list of CgalPolygons
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
static bool is_edge(int a, int b, int n)
void createFace(int a, int b, int c)
insert a new face. Caller is responsible for keeping the triangulation in a consistent state....
CGAL::Point_2< Kernel > super
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
bool is_diagonal(int n) const
std::list< Polygon > Partition
a partitioning of a polygon, that is a list of sub-sets
void fanTriangulate(Triangulation &tri) const
compute a fan-triangulation from a list of convex parts. Each convex sub-polygon is triangulated usin...
CgalPoint & operator=(const QPointF &p)
assignment operator from QPointF
CGAL::Polygon_2< PolygonTraits > CgalPolygon
CGAL::Polygon_2 built upon custom type.
static bool is_reflex_vertex(const CgalPolygon::Vertex_circulator &p, double precision=0.0)
test whether a vertex is a reflex (concave) vertex
CgalPoint()
empty constructor
DecompositionAlgorithm
choice of decomposition algorithm
std::vector< int > Polygon
Polygon a sub-set of vertex indexes.
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
static bool is_diagonal(int a, int b, int n)
a polygon vertex to be used with CGAL::Polygon_2. Derives from CGAL::Point_2 but is convertible to an...
type traits for a polygon partition Defines the type for Points and Polygons
std::ostream & operator<<(std::ostream &out, const frechet::poly::CgalPolygon &poly)
print operator (for debugging)