Root/poly2d/f2d_tri_holes.cpp

1/*
2 * f2d_tri_holes.cpp - Triangulate a polygon with holes
3 *
4 * Written 2013 by Werner Almesberger
5 * Copyright 2013 by Werner Almesberger
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 */
12
13/*
14 * References:
15 * http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/
16 * Chapter_main.html#Subsection_37.8.2
17 * http://www.cgal.org/Manual/latest/examples/Triangulation_2/
18 * polygon_triangulation.cpp
19 */
20
21extern "C" {
22    #include <assert.h>
23
24    #include "util.h"
25    #include "poly2d.h"
26}
27
28#if 0
29/*
30 * @@@ Prevent spurious aborts with
31 *
32 * terminate called after throwing an instance of 'CGAL::Precondition_exception'
33 * what(): CGAL ERROR: precondition violation!
34 * Expr: is_simple_2(first, last, traits)
35 * File: /usr/include/CGAL/Polygon_2/Polygon_2_algorithms_impl.h
36 * Line: 420
37 *
38 * Note that we also need to check the polygons for simplicity in recurse_area,
39 * or this may still lead to assertion failures.
40 */
41
42#define CGAL_POLYGON_NO_PRECONDITIONS
43#endif
44
45#include "cgal_helper.h"
46
47//#include <vector>
48//#include <boost/shared_ptr.hpp>
49
50#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
51#include <CGAL/Constrained_Delaunay_triangulation_2.h>
52#include <CGAL/Triangulation_face_base_with_info_2.h>
53#include <CGAL/Polygon_2.h>
54
55
56struct FaceInfo2 {
57    FaceInfo2(){}
58    int nesting_level;
59
60    bool in_domain(void)
61    {
62        return nesting_level % 2 == 1;
63    }
64};
65
66
67typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
68typedef CGAL::Triangulation_vertex_base_2<K> Vb;
69typedef CGAL::Triangulation_face_base_with_info_2<FaceInfo2, K> Fbb;
70typedef CGAL::Constrained_triangulation_face_base_2<K, Fbb> Fb;
71typedef CGAL::Triangulation_data_structure_2<Vb, Fb> TDS;
72typedef CGAL::Exact_predicates_tag Itag;
73typedef CGAL::Constrained_Delaunay_triangulation_2<K, TDS, Itag> CDT;
74typedef CDT::Point Point;
75typedef CGAL::Polygon_2<K> Polygon_2;
76
77
78#if 0
79typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes;
80
81typedef boost::shared_ptr<Polygon_with_holes> PolygonPtr;
82
83typedef std::vector<PolygonPtr> PolygonPtrVector;
84
85    struct p2d *res = NULL, **last = &res, *np;
86
87
88static void append_poly(Polygon_2 poly, struct p2d ***last)
89{
90    **last = P2_to_p2d(poly);
91    *last = &(**last)->next;
92}
93#endif
94
95
96/* ----- Mark domains ------------------------------------------------------ */
97
98
99static void mark_domains(CDT &ct, CDT::Face_handle start, int index,
100    std::list<CDT::Edge> &border)
101{
102    std::list<CDT::Face_handle> queue;
103
104    if (start->info().nesting_level != -1)
105        return;
106
107    queue.push_back(start);
108    while (!queue.empty()) {
109        CDT::Face_handle fh = queue.front();
110
111        queue.pop_front();
112        if (fh->info().nesting_level == -1){
113            fh->info().nesting_level = index;
114            for (int i = 0; i < 3; i++) {
115                CDT::Edge e(fh, i);
116                CDT::Face_handle n = fh->neighbor(i);
117                if (n->info().nesting_level == -1) {
118                    if (ct.is_constrained(e))
119                        border.push_back(e);
120                    else
121                        queue.push_back(n);
122                }
123            }
124        }
125    }
126}
127
128
129static void mark_domains(CDT &cdt)
130{
131    int index = 0;
132
133    for (CDT::All_faces_iterator it = cdt.all_faces_begin();
134        it != cdt.all_faces_end(); ++it)
135        it->info().nesting_level = -1;
136
137    std::list<CDT::Edge> border;
138    mark_domains(cdt, cdt.infinite_face(), index++, border);
139    while(!border.empty()) {
140        CDT::Edge e = border.front();
141
142        border.pop_front();
143        CDT::Face_handle n = e.first->neighbor(e.second);
144        if (n->info().nesting_level == -1)
145            mark_domains(cdt, n, e.first->info().nesting_level+1,
146                border);
147    }
148}
149
150
151/* ----- Inser polygon ----------------------------------------------------- */
152
153
154void insert_polygon(CDT &cdt, const Polygon_2 &polygon)
155{
156    if (polygon.is_empty())
157        return;
158    CDT::Vertex_handle v_prev =
159        cdt.insert(*CGAL::cpp0x::prev(polygon.vertices_end()));
160    for (Polygon_2::Vertex_iterator vit = polygon.vertices_begin();
161        vit != polygon.vertices_end(); ++vit) {
162        CDT::Vertex_handle vh = cdt.insert(*vit);
163
164        cdt.insert_constraint(vh, v_prev);
165        v_prev = vh;
166    }
167}
168
169
170static const struct v2d *find_point(const struct p2d *p, double x, double y)
171{
172    const struct v2d *v = p->v;
173
174    while (v) {
175        if (v->x == x && v->y == y)
176            break;
177        v = v->next;
178        if (v == p->v)
179            return NULL;
180    }
181    return v;
182}
183
184
185static struct f2d *make_face(CDT::Finite_faces_iterator fit,
186    const struct p2d *p, const struct p2d *holes)
187{
188    struct f2d *f;
189    const struct v2d *v[3];
190    const struct p2d *h;
191    int i, j;
192
193    for (i = 0; i != 3; i++) {
194        Point point = fit->vertex(i)->point();
195        const struct v2d *m;
196
197        m = find_point(p, point.x(), point.y());
198        if (m) {
199            v[i] = m;
200            continue;
201        }
202        for (h = holes; h; h = h->next) {
203            m = find_point(h, point.x(), point.y());
204            if (!m)
205                continue;
206            v[i] = m;
207            break;
208        }
209        assert(m);
210    }
211
212    f = alloc_type(struct f2d);
213    for (i = 0; i != 3; i++) {
214        f->x[i] = v[i]->x;
215        f->y[i] = v[i]->y;
216        j = i+1;
217        if (j == 3)
218            j = 0;
219        f->side[i] = v[i]->next == v[j] || v[j]->next == v[i];
220    }
221    f->next = NULL;
222    
223    return f;
224}
225
226
227void f2d_tri_holes_append(const struct p2d *p, const struct p2d *holes,
228    struct f2d ***last)
229{
230    CDT cdt;
231    const struct p2d *h;
232    struct f2d *f;
233
234    insert_polygon(cdt, p2d_to_P2(p, 0));
235    for (h = holes; h; h = h->next) {
236        assert(p2d_is_closed(h));
237        insert_polygon(cdt, p2d_to_P2(h, 0));
238    }
239    mark_domains(cdt);
240
241    for (CDT::Finite_faces_iterator fit = cdt.finite_faces_begin();
242        fit != cdt.finite_faces_end(); ++fit)
243        if (fit->info().in_domain()) {
244            f = make_face(fit, p, holes);
245            **last = f;
246            *last = &f->next;
247        }
248}
249
250
251extern "C" struct f2d *f2d_tri_holes(const struct p2d *p,
252    const struct p2d *holes)
253{
254    struct f2d *res = NULL, **last = &res;
255
256    f2d_tri_holes_append(p, holes, &last);
257    return res;
258}
259

Archive Download this file

Branches:
master



interactive