Mesh.h 7.6 KB
Newer Older
1
2
3
4
5
6
#ifndef OERSTED_MESH_H
#define OERSTED_MESH_H

#include <algorithm>
#include <fstream>
#include <numeric>
7
#include <set>
8

9
10
#include "Sketch.hpp"

11
#include "BoundaryConstraint.h"
12
13
#include "Edge.h"
#include "InsertionQueuer.h"
14
#include "Point.h"
15
#include "DartTriangle.h"
16

17
18
19
20
21
22
23
24
enum class LocateTriangleResult {
    Interior, Exterior, Boundary, Point // TODO: Enumerate cases in function when triangle is located by a point near the boundary
};

enum class InsertPointResult {
    Success, Midpoint, Duplicate, Failure
};

25
class Mesh { // TODO: Namespaces. Also, need to rename a bunch of things to be more consistent and clear w.r.t. how various arrays are accessed (e.g. by edge/dart index versus plain index)
26
public:
27
28
    Mesh(Sketch &s);

29
    friend class BoundaryConstraint;
30
31
32
    friend class CircumcenterQueuer;
    friend class MidpointQueuer;

33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
    double MinimumElementQuality = 0.0;
    double MinimumElementSize = 0.0;
    double MaximumElementSize = DBL_MAX;

    bool are_intersecting(size_t ei, size_t ej) const;

    bool edges_are_valid() const;

    bool in_triangle(Point const p, size_t ei) const;

    bool is_constrained(size_t ei) const { return Edges[ei].Constraint != 0; };

    bool is_encroached(Point const p, size_t ei) const;

    bool is_locally_optimal(size_t ei) const;

    bool is_protruding(size_t ei) const;

    bool is_valid(size_t ei) const;

    bool orientation(size_t ei) const { return Edges[ei].Orientation; };

    bool refine();

    bool refine_once();

    double circumradius(size_t ei) const;

    double length(size_t ei) const;

    double shortest_edge_length(size_t ei) const;

    size_t next(size_t ei) const { return Edges[ei].Next; };

    size_t node(size_t ei) const { return Edges[ei].Node; };

    size_t node(Edge const e) const { return e.Node; };

    size_t num_points() const { return Points.size(); };

    size_t num_edges() const;

    size_t num_triangles() const { return Triangles.size(); };

    size_t prev(size_t ei) const { return Edges[ei].Prev; };

79
    size_t size_dart_constraints() const {return DartConstraints.size(); };
80
81
82

    size_t size_edges() const { return Edges.size(); };

83
84
    size_t size_points() const { return Points.size(); };

85
86
    size_t size_triangles() const { return Triangles.size(); };

87
88
    size_t size_contours() const { return Contours.size(); };

89
90
    size_t size_boundary_constraints() const { return BoundaryConstraints.size(); };

91
92
    size_t twin(size_t ei) const { return Edges[ei].Twin; };

93
94
    void add_to_queue(std::unique_ptr<InsertionQueuer> ic) { Queue.push_back(std::move(ic)); };

95
96
97
98
    void create();

    void save_as(std::string path, std::string file_name) const;

99
    // TODO: rename these methods something like, dart_constraint_from_edge_index, curve_from_edge_index
100
101
102
    DartConstraint const dart_constraint_from_edge(size_t ei) const { return DartConstraints[Edges[ei].Constraint]; };

    std::shared_ptr<Curve const> curve_from_edge(size_t ei) const { return DartConstraints[Edges[ei].Constraint].curve(); };
103

104
    std::shared_ptr<Curve const> curve(size_t i) const {return BoundaryConstraints[i]->curve(); };
105

106
107
    std::shared_ptr<BoundaryConstraint> boundary_constraint(std::shared_ptr<Curve const> const &c) const;

108
109
    std::shared_ptr<BoundaryConstraint> boundary_constraint(size_t i) const {return BoundaryConstraints[i]; };

110
    DartConstraint const dart_constraint(size_t i) const { return DartConstraints[i]; };
111

112
113
114
115
    DartTriangle const &triangle(size_t i) const { return Triangles[i]; };

    Point circumcenter(size_t ei) const;

116
    Point const &base(Edge const &e) const { return Points[e.Node]; };
117

118
    Point const &base(size_t i) const { return Points[node(i)]; };
119

120
    Point const &point(size_t i) const { return Points[i]; };
121

122
    Point const &point(Edge const &e) const { return Points[e.Node]; };
123

124
    Point const &tip(Edge const &e) const { return Points[next(e).Node]; };
125

126
    Point const &tip(size_t i) const { return Points[node(next(i))]; };
127

128
    Point midpoint(size_t e) { return midpoint(Edges[e]); };
129

130
131
132
    Point midpoint(Edge const e) const {
        Point const &p0 = base(e);
        Point const &p1 = tip(e);
133

134
135
136
137
138
139
140
141
        return Point((p0.X + p1.X) / 2.0, (p0.Y + p1.Y) / 2.0);
    }

    Edge const &edge(size_t i) const { return Edges[i]; };

    Edge const &next(Edge const &e) const { return Edges[e.Next]; };

    Edge const &prev(Edge const &e) const { return Edges[e.Prev]; };
142

143
    Edge const &twin(Edge const &e) const { return Edges[e.Twin]; };
144

145
146
    Edge const &edge_from_triangle_index(size_t i) const { return Edges[Triangles[i].Edge]; }; // TODO: Rename to triangle_dart

147
    Edge const &edge_from_triangle(DartTriangle const &dt) const { return Edges[dt.Edge]; };
148

149
    std::array<size_t,3> nodes_from_triangle(DartTriangle const & dt) const {
150
151
152
153
154
155
156
157
158
159
        Edge const &e = edge_from_triangle(dt);

        std::array<size_t,3> n;

        n[0] = e.Node;
        n[1] = next(e).Node;
        n[2] = prev(e).Node;

        return n;
    };
160

161
162
    std::vector<size_t> boundary_nodes(size_t i) const { return BoundaryConstraints[i]->nodes(*this); }

163
164
165
166
167
168
169
    LocateTriangleResult locate_triangle(Point const p, size_t &ei) const;

    LocateTriangleResult locate_triangle(Point const p) const {
        size_t ei = Edges.size() - 1;
        return locate_triangle(p, ei);
    };

170
171
172
173
174
    AddToQueueResult add_circumcenter_to_queue(size_t dart);

    AddToQueueResult add_point_to_queue(Point const p, size_t dart);

    AddToQueueResult add_point_to_queue(Point const p) { return add_point_to_queue(p, Edges.size() - 1); };
175
176
177
178

protected:
    std::shared_ptr<Contour const> Boundary;
    std::vector<std::shared_ptr<Contour const>> Contours;
179
    std::vector<std::shared_ptr<BoundaryConstraint>> BoundaryConstraints;
180
181
182

    std::vector<Point> Points;
    std::vector<Edge> Edges;
183
    std::vector<DartConstraint> DartConstraints;
184
    std::vector<DartTriangle> Triangles;
185

186
    std::vector<std::unique_ptr<InsertionQueuer>> Queue;
187

188
189
190
191
192
193
194
195
196
private:
    bool find_attached(Point const p, size_t &ei);

    bool recursive_swap(size_t ei);

    bool swap(size_t ei);

    size_t new_edges(size_t num_new) {
        for (size_t i = 0; i != num_new; ++i) {
197
            Edges.emplace_back(Edges.size());
198
199
200
201
202
            Edges.back().Constraint = 0;
        }
        return Edges.size();
    }

203
204
205
206
207
    DartConstraint &new_dart_constraint(DartConstraint &dc) {
        return new_dart_constraint(dc.S0, dc.S1, dc.boundary_constraint());
    }

    DartConstraint &new_dart_constraint(double s0, double s1, std::shared_ptr<BoundaryConstraint> bc) {
208
        bc->add_dart_constraint(DartConstraints.size());
209
210
211
212
        DartConstraints.emplace_back(s0, s1, bc, DartConstraints.size());
        return DartConstraints.back();
    }

213
    Edge &new_edge(size_t p, size_t c, bool dir) {
214
        Edges.emplace_back(p, Edges.size(), c, dir);
215
216
217
218
219
220
221
222
223
        return Edges.back();
    }

    void create_boundary_polygon();

    void element_quality(std::vector<double> &radii, std::vector<double> &quality);

    void get_triangles();

224
225
    void insert_from_queue();

226
227
228
229
230
231
    void insert_internal_boundaries();

    void mark_triangles();

    void refine_once(std::vector<size_t> index, std::vector<double> circumradius, std::vector<double> quality);

232
233
    void sort_constraints();

234
235
236
237
238
239
240
241
242
243
    void sort_permutation_ascending(std::vector<double> &value, std::vector<size_t> &index) const;

    void sort_permutation_descending(std::vector<double> &values, std::vector<size_t> &index) const;

    void split_edge(size_t ei);

    void split_encroached_edges();

    void triangulate_boundary_polygon();

244
    std::vector<size_t> get_encroached_edges(Point const p, size_t edge);
245
246
247
248
249
250
251

    InsertPointResult insert_point(Point const p, size_t ei);

    InsertPointResult insert_midpoint(size_t ei);
};

#endif //OERSTED_MESH_H