summaryrefslogtreecommitdiff
path: root/polygon/poly2tri/common/shapes.h
diff options
context:
space:
mode:
Diffstat (limited to 'polygon/poly2tri/common/shapes.h')
-rw-r--r--polygon/poly2tri/common/shapes.h351
1 files changed, 351 insertions, 0 deletions
diff --git a/polygon/poly2tri/common/shapes.h b/polygon/poly2tri/common/shapes.h
new file mode 100644
index 0000000..c65f485
--- /dev/null
+++ b/polygon/poly2tri/common/shapes.h
@@ -0,0 +1,351 @@
+/*
+ * 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 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