Remaining files transfered

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