| /* |
| * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors |
| * http://code.google.com/p/poly2tri/ |
| * |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without modification, |
| * are permitted provided that the following conditions are met: |
| * |
| * * Redistributions of source code must retain the above copyright notice, |
| * this list of conditions and the following disclaimer. |
| * * Redistributions in binary form must reproduce the above copyright notice, |
| * this list of conditions and the following disclaimer in the documentation |
| * and/or other materials provided with the distribution. |
| * * Neither the name of Poly2Tri nor the names of its contributors may be |
| * used to endorse or promote products derived from this software without specific |
| * prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| // Include guard |
| #ifndef SHAPES_H |
| #define SHAPES_H |
| |
| #include <vector> |
| #include <cstddef> |
| #include <assert.h> |
| #include <cmath> |
| |
| namespace p2t { |
| |
| struct Edge; |
| |
| struct Point { |
| |
| double x, y; |
| |
| /// Default constructor does nothing (for performance). |
| Point() |
| { |
| x = 0.0; |
| y = 0.0; |
| } |
| |
| /// The edges this point constitutes an upper ending point |
| std::vector<Edge*> edge_list; |
| |
| /// Construct using coordinates. |
| Point(double x, double y) : x(x), y(y) {} |
| |
| /// Set this point to all zeros. |
| void set_zero() |
| { |
| x = 0.0; |
| y = 0.0; |
| } |
| |
| /// Set this point to some specified coordinates. |
| void set(double x_, double y_) |
| { |
| x = x_; |
| y = y_; |
| } |
| |
| /// Negate this point. |
| Point operator -() const |
| { |
| Point v; |
| v.set(-x, -y); |
| return v; |
| } |
| |
| /// Add a point to this point. |
| void operator +=(const Point& v) |
| { |
| x += v.x; |
| y += v.y; |
| } |
| |
| /// Subtract a point from this point. |
| void operator -=(const Point& v) |
| { |
| x -= v.x; |
| y -= v.y; |
| } |
| |
| /// Multiply this point by a scalar. |
| void operator *=(double a) |
| { |
| x *= a; |
| y *= a; |
| } |
| |
| /// Get the length of this point (the norm). |
| double Length() const |
| { |
| return std::sqrt(x * x + y * y); |
| } |
| |
| /// Convert this point into a unit point. Returns the Length. |
| double Normalize() |
| { |
| double len = Length(); |
| x /= len; |
| y /= len; |
| return len; |
| } |
| |
| }; |
| |
| // Represents a simple polygon's edge |
| struct Edge { |
| |
| Point* p, *q; |
| |
| /// Constructor |
| Edge(Point& p1, Point& p2) : p(&p1), q(&p2) |
| { |
| if (p1.y > p2.y) { |
| q = &p1; |
| p = &p2; |
| } else if (p1.y == p2.y) { |
| if (p1.x > p2.x) { |
| q = &p1; |
| p = &p2; |
| } else if (p1.x == p2.x) { |
| // Repeat points |
| assert(false); |
| } |
| } |
| |
| q->edge_list.push_back(this); |
| } |
| }; |
| |
| // Triangle-based data structures are know to have better performance than quad-edge structures |
| // See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator" |
| // "Triangulations in CGAL" |
| class Triangle { |
| public: |
| |
| /// Constructor |
| Triangle(Point& a, Point& b, Point& c); |
| |
| /// Flags to determine if an edge is a Constrained edge |
| bool constrained_edge[3]; |
| /// Flags to determine if an edge is a Delauney edge |
| bool delaunay_edge[3]; |
| |
| Point* GetPoint(const int& index); |
| Point* PointCW(Point& point); |
| Point* PointCCW(Point& point); |
| Point* OppositePoint(Triangle& t, Point& p); |
| |
| Triangle* GetNeighbor(const int& index); |
| void MarkNeighbor(Point* p1, Point* p2, Triangle* t); |
| void MarkNeighbor(Triangle& t); |
| |
| void MarkConstrainedEdge(const int index); |
| void MarkConstrainedEdge(Edge& edge); |
| void MarkConstrainedEdge(Point* p, Point* q); |
| |
| int Index(const Point* p); |
| int EdgeIndex(const Point* p1, const Point* p2); |
| |
| Triangle* NeighborCW(Point& point); |
| Triangle* NeighborCCW(Point& point); |
| bool GetConstrainedEdgeCCW(Point& p); |
| bool GetConstrainedEdgeCW(Point& p); |
| void SetConstrainedEdgeCCW(Point& p, bool ce); |
| void SetConstrainedEdgeCW(Point& p, bool ce); |
| bool GetDelunayEdgeCCW(Point& p); |
| bool GetDelunayEdgeCW(Point& p); |
| void SetDelunayEdgeCCW(Point& p, bool e); |
| void SetDelunayEdgeCW(Point& p, bool e); |
| |
| bool Contains(Point* p); |
| bool Contains(const Edge& e); |
| bool Contains(Point* p, Point* q); |
| void Legalize(Point& point); |
| void Legalize(Point& opoint, Point& npoint); |
| /** |
| * Clears all references to all other triangles and points |
| */ |
| void Clear(); |
| void ClearNeighbor(Triangle *triangle ); |
| void ClearNeighbors(); |
| void ClearDelunayEdges(); |
| |
| inline bool IsInterior(); |
| inline void IsInterior(bool b); |
| |
| Triangle& NeighborAcross(Point& opoint); |
| |
| void DebugPrint(); |
| |
| private: |
| |
| /// Triangle points |
| Point* points_[3]; |
| /// Neighbor list |
| Triangle* neighbors_[3]; |
| |
| /// Has this triangle been marked as an interior triangle? |
| bool interior_; |
| }; |
| |
| inline bool cmp(const Point* a, const Point* b) |
| { |
| if (a->y < b->y) { |
| return true; |
| } else if (a->y == b->y) { |
| // Make sure q is point with greater x value |
| if (a->x < b->x) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /// Add two points_ component-wise. |
| inline Point operator +(const Point& a, const Point& b) |
| { |
| return Point(a.x + b.x, a.y + b.y); |
| } |
| |
| /// Subtract two points_ component-wise. |
| inline Point operator -(const Point& a, const Point& b) |
| { |
| return Point(a.x - b.x, a.y - b.y); |
| } |
| |
| /// Multiply point by scalar |
| inline Point operator *(double s, const Point& a) |
| { |
| return Point(s * a.x, s * a.y); |
| } |
| |
| inline bool operator ==(const Point& a, const Point& b) |
| { |
| return a.x == b.x && a.y == b.y; |
| } |
| |
| inline bool operator !=(const Point& a, const Point& b) |
| { |
| return !(a.x == b.x) && !(a.y == b.y); |
| } |
| |
| /// Peform the dot product on two vectors. |
| inline double Dot(const Point& a, const Point& b) |
| { |
| return a.x * b.x + a.y * b.y; |
| } |
| |
| /// Perform the cross product on two vectors. In 2D this produces a scalar. |
| inline double Cross(const Point& a, const Point& b) |
| { |
| return a.x * b.y - a.y * b.x; |
| } |
| |
| /// Perform the cross product on a point and a scalar. In 2D this produces |
| /// a point. |
| inline Point Cross(const Point& a, double s) |
| { |
| return Point(s * a.y, -s * a.x); |
| } |
| |
| /// Perform the cross product on a scalar and a point. In 2D this produces |
| /// a point. |
| inline Point Cross(const double s, const Point& a) |
| { |
| return Point(-s * a.y, s * a.x); |
| } |
| |
| inline Point* Triangle::GetPoint(const int& index) |
| { |
| return points_[index]; |
| } |
| |
| inline Triangle* Triangle::GetNeighbor(const int& index) |
| { |
| return neighbors_[index]; |
| } |
| |
| inline bool Triangle::Contains(Point* p) |
| { |
| return p == points_[0] || p == points_[1] || p == points_[2]; |
| } |
| |
| inline bool Triangle::Contains(const Edge& e) |
| { |
| return Contains(e.p) && Contains(e.q); |
| } |
| |
| inline bool Triangle::Contains(Point* p, Point* q) |
| { |
| return Contains(p) && Contains(q); |
| } |
| |
| inline bool Triangle::IsInterior() |
| { |
| return interior_; |
| } |
| |
| inline void Triangle::IsInterior(bool b) |
| { |
| interior_ = b; |
| } |
| |
| } |
| |
| #endif |
| |
| |