← Back to branch summary

~ubuntu-branches/ubuntu/utopic/slic3r/utopic

« back to all changes in this revision

Viewing changes to xs/src/poly2tri/common/shapes.h

  • Committer: Package Import Robot
  • Author(s): Chow Loong Jin
  • Date: 2014-06-17 01:27:26 UTC
  • Revision ID: package-import@ubuntu.com-20140617012726-2wrs4zdo251nr4vg
Tags: upstream-1.1.4+dfsg
Import upstream version 1.1.4+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
xs/src/poly2tri/common/shapes.h
 
1
/*
 
2
 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
 
3
 * http://code.google.com/p/poly2tri/
 
4
 *
 
5
 * All rights reserved.
 
6
 *
 
7
 * Redistribution and use in source and binary forms, with or without modification,
 
8
 * are permitted provided that the following conditions are met:
 
9
 *
 
10
 * * Redistributions of source code must retain the above copyright notice,
 
11
 *   this list of conditions and the following disclaimer.
 
12
 * * Redistributions in binary form must reproduce the above copyright notice,
 
13
 *   this list of conditions and the following disclaimer in the documentation
 
14
 *   and/or other materials provided with the distribution.
 
15
 * * Neither the name of Poly2Tri nor the names of its contributors may be
 
16
 *   used to endorse or promote products derived from this software without specific
 
17
 *   prior written permission.
 
18
 *
 
19
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 
20
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 
21
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 
22
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 
23
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 
24
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 
25
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 
26
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 
27
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 
28
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 
29
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
30
 */
 
31
 
 
32
// Include guard
 
33
#ifndef SHAPES_H
 
34
#define SHAPES_H
 
35
 
 
36
#include <vector>
 
37
#include <cstddef>
 
38
#include <assert.h>
 
39
#include <cmath>
 
40
 
 
41
namespace p2t {
 
42
 
 
43
struct Edge;
 
44
 
 
45
struct Point {
 
46
 
 
47
  double x, y;
 
48
 
 
49
  /// Default constructor does nothing (for performance).
 
50
  Point()
 
51
  {
 
52
    x = 0.0;
 
53
    y = 0.0;
 
54
  }
 
55
 
 
56
  /// The edges this point constitutes an upper ending point
 
57
  std::vector<Edge*> edge_list;
 
58
 
 
59
  /// Construct using coordinates.
 
60
  Point(double x, double y) : x(x), y(y) {}
 
61
 
 
62
  /// Set this point to all zeros.
 
63
  void set_zero()
 
64
  {
 
65
    x = 0.0;
 
66
    y = 0.0;
 
67
  }
 
68
 
 
69
  /// Set this point to some specified coordinates.
 
70
  void set(double x_, double y_)
 
71
  {
 
72
    x = x_;
 
73
    y = y_;
 
74
  }
 
75
 
 
76
  /// Negate this point.
 
77
  Point operator -() const
 
78
  {
 
79
    Point v;
 
80
    v.set(-x, -y);
 
81
    return v;
 
82
  }
 
83
 
 
84
  /// Add a point to this point.
 
85
  void operator +=(const Point& v)
 
86
  {
 
87
    x += v.x;
 
88
    y += v.y;
 
89
  }
 
90
 
 
91
  /// Subtract a point from this point.
 
92
  void operator -=(const Point& v)
 
93
  {
 
94
    x -= v.x;
 
95
    y -= v.y;
 
96
  }
 
97
 
 
98
  /// Multiply this point by a scalar.
 
99
  void operator *=(double a)
 
100
  {
 
101
    x *= a;
 
102
    y *= a;
 
103
  }
 
104
 
 
105
  /// Get the length of this point (the norm).
 
106
  double Length() const
 
107
  {
 
108
    return sqrt(x * x + y * y);
 
109
  }
 
110
 
 
111
  /// Convert this point into a unit point. Returns the Length.
 
112
  double Normalize()
 
113
  {
 
114
    const double len = Length();
 
115
    x /= len;
 
116
    y /= len;
 
117
    return len;
 
118
  }
 
119
 
 
120
};
 
121
 
 
122
// Represents a simple polygon's edge
 
123
struct Edge {
 
124
 
 
125
  Point* p, *q;
 
126
 
 
127
  /// Constructor
 
128
  Edge(Point& p1, Point& p2) : p(&p1), q(&p2)
 
129
  {
 
130
    if (p1.y > p2.y) {
 
131
      q = &p1;
 
132
      p = &p2;
 
133
    } else if (p1.y == p2.y) {
 
134
      if (p1.x > p2.x) {
 
135
        q = &p1;
 
136
        p = &p2;
 
137
      } else if (p1.x == p2.x) {
 
138
        // Repeat points
 
139
        assert(false);
 
140
      }
 
141
    }
 
142
 
 
143
    q->edge_list.push_back(this);
 
144
  }
 
145
};
 
146
 
 
147
// Triangle-based data structures are know to have better performance than quad-edge structures
 
148
// See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
 
149
//      "Triangulations in CGAL"
 
150
class Triangle {
 
151
public:
 
152
 
 
153
/// Constructor
 
154
Triangle(Point& a, Point& b, Point& c);
 
155
 
 
156
/// Flags to determine if an edge is a Constrained edge
 
157
bool constrained_edge[3];
 
158
/// Flags to determine if an edge is a Delauney edge
 
159
bool delaunay_edge[3];
 
160
 
 
161
Point* GetPoint(int index);
 
162
Point* PointCW(const Point& point);
 
163
Point* PointCCW(const Point& point);
 
164
Point* OppositePoint(Triangle& t, const Point& p);
 
165
 
 
166
Triangle* GetNeighbor(int index);
 
167
void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
 
168
void MarkNeighbor(Triangle& t);
 
169
 
 
170
void MarkConstrainedEdge(int index);
 
171
void MarkConstrainedEdge(Edge& edge);
 
172
void MarkConstrainedEdge(Point* p, Point* q);
 
173
 
 
174
int Index(const Point* p);
 
175
int EdgeIndex(const Point* p1, const Point* p2);
 
176
 
 
177
Triangle* NeighborCW(const Point& point);
 
178
Triangle* NeighborCCW(const Point& point);
 
179
bool GetConstrainedEdgeCCW(const Point& p);
 
180
bool GetConstrainedEdgeCW(const Point& p);
 
181
void SetConstrainedEdgeCCW(const Point& p, bool ce);
 
182
void SetConstrainedEdgeCW(const Point& p, bool ce);
 
183
bool GetDelunayEdgeCCW(const Point& p);
 
184
bool GetDelunayEdgeCW(const Point& p);
 
185
void SetDelunayEdgeCCW(const Point& p, bool e);
 
186
void SetDelunayEdgeCW(const Point& p, bool e);
 
187
 
 
188
bool Contains(const Point* p);
 
189
bool Contains(const Edge& e);
 
190
bool Contains(const Point* p, const Point* q);
 
191
void Legalize(Point& point);
 
192
void Legalize(Point& opoint, Point& npoint);
 
193
/**
 
194
 * Clears all references to all other triangles and points
 
195
 */
 
196
void Clear();
 
197
void ClearNeighbor(const Triangle *triangle);
 
198
void ClearNeighbors();
 
199
void ClearDelunayEdges();
 
200
 
 
201
inline bool IsInterior();
 
202
inline void IsInterior(bool b);
 
203
 
 
204
Triangle& NeighborAcross(const Point& opoint);
 
205
 
 
206
void DebugPrint();
 
207
 
 
208
private:
 
209
 
 
210
/// Triangle points
 
211
Point* points_[3];
 
212
/// Neighbor list
 
213
Triangle* neighbors_[3];
 
214
 
 
215
/// Has this triangle been marked as an interior triangle?
 
216
bool interior_;
 
217
};
 
218
 
 
219
inline bool cmp(const Point* a, const Point* b)
 
220
{
 
221
  if (a->y < b->y) {
 
222
    return true;
 
223
  } else if (a->y == b->y) {
 
224
    // Make sure q is point with greater x value
 
225
    if (a->x < b->x) {
 
226
      return true;
 
227
    }
 
228
  }
 
229
  return false;
 
230
}
 
231
 
 
232
/// Add two points_ component-wise.
 
233
inline Point operator +(const Point& a, const Point& b)
 
234
{
 
235
  return Point(a.x + b.x, a.y + b.y);
 
236
}
 
237
 
 
238
/// Subtract two points_ component-wise.
 
239
inline Point operator -(const Point& a, const Point& b)
 
240
{
 
241
  return Point(a.x - b.x, a.y - b.y);
 
242
}
 
243
 
 
244
/// Multiply point by scalar
 
245
inline Point operator *(double s, const Point& a)
 
246
{
 
247
  return Point(s * a.x, s * a.y);
 
248
}
 
249
 
 
250
inline bool operator ==(const Point& a, const Point& b)
 
251
{
 
252
  return a.x == b.x && a.y == b.y;
 
253
}
 
254
 
 
255
inline bool operator !=(const Point& a, const Point& b)
 
256
{
 
257
  return !(a.x == b.x) && !(a.y == b.y);
 
258
}
 
259
 
 
260
/// Peform the dot product on two vectors.
 
261
inline double Dot(const Point& a, const Point& b)
 
262
{
 
263
  return a.x * b.x + a.y * b.y;
 
264
}
 
265
 
 
266
/// Perform the cross product on two vectors. In 2D this produces a scalar.
 
267
inline double Cross(const Point& a, const Point& b)
 
268
{
 
269
  return a.x * b.y - a.y * b.x;
 
270
}
 
271
 
 
272
/// Perform the cross product on a point and a scalar. In 2D this produces
 
273
/// a point.
 
274
inline Point Cross(const Point& a, double s)
 
275
{
 
276
  return Point(s * a.y, -s * a.x);
 
277
}
 
278
 
 
279
/// Perform the cross product on a scalar and a point. In 2D this produces
 
280
/// a point.
 
281
inline Point Cross(double s, const Point& a)
 
282
{
 
283
  return Point(-s * a.y, s * a.x);
 
284
}
 
285
 
 
286
inline Point* Triangle::GetPoint(int index)
 
287
{
 
288
  return points_[index];
 
289
}
 
290
 
 
291
inline Triangle* Triangle::GetNeighbor(int index)
 
292
{
 
293
  return neighbors_[index];
 
294
}
 
295
 
 
296
inline bool Triangle::Contains(const Point* p)
 
297
{
 
298
  return p == points_[0] || p == points_[1] || p == points_[2];
 
299
}
 
300
 
 
301
inline bool Triangle::Contains(const Edge& e)
 
302
{
 
303
  return Contains(e.p) && Contains(e.q);
 
304
}
 
305
 
 
306
inline bool Triangle::Contains(const Point* p, const Point* q)
 
307
{
 
308
  return Contains(p) && Contains(q);
 
309
}
 
310
 
 
311
inline bool Triangle::IsInterior()
 
312
{
 
313
  return interior_;
 
314
}
 
315
 
 
316
inline void Triangle::IsInterior(bool b)
 
317
{
 
318
  interior_ = b;
 
319
}
 
320
 
 
321
}
 
322
 
 
323
#endif
 
 
b'\\ No newline at end of file'