1 files changed, 296 insertions, 0 deletions
diff --git a/src/base/triangulate/Shapes.h b/src/base/triangulate/Shapes.h
new file mode 100644
index 0000000..0417d7c
--- /dev/null
+++ b/src/base/triangulate/Shapes.h
@@ -0,0 +1,296 @@
+//
+//  libavg - Media Playback Engine.
+//  Copyright (C) 2003-2014 Ulrich von Zadow
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+//  You should have received a copy of the GNU Lesser General Public
+//  License along with this library; if not, write to the Free Software
+//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+//
+//  Current versions can be found at www.libavg.de
+//
+
+//
+// Based on Poly2Tri algorithm.
+// Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+// http://code.google.com/p/poly2tri/
+//
+
+#ifndef SHAPES_H
+#define SHAPES_H
+
+#include <vector>
+#include <cstddef>
+#include <assert.h>
+#include <cmath>
+
+namespace avg {
+
+struct Edge;
+
+struct Point
+{
+    double m_X, m_Y;
+    int m_Index;
+
+    /// The edges this point constitutes an upper ending point
+    std::vector<Edge*> m_EdgeList;
+
+    /// Default constructor does nothing (for performance).
+    Point() {
+        m_X = 0.0;
+        m_Y = 0.0;
+        m_Index = 0;
+    }
+
+    Point(double x, double y, int index) :
+            m_X(x), m_Y(y), m_Index(index) {}
+
+    void set_zero()
+    {
+        m_X = 0.0;
+        m_Y = 0.0;
+    }
+
+    void set(double x_, double y_)
+    {
+        m_X = x_;
+        m_Y = y_;
+    }
+
+    Point operator -() const
+    {
+        Point v;
+        v.set(-m_X, -m_Y);
+        return v;
+    }
+
+    void operator +=(const Point& v)
+    {
+        m_X += v.m_X;
+        m_Y += v.m_Y;
+    }
+
+    void operator -=(const Point& v)
+    {
+        m_X -= v.m_X;
+        m_Y -= v.m_Y;
+    }
+
+    void operator *=(double a)
+    {
+        m_X *= a;
+        m_Y *= a;
+    }
+
+    double length() const
+    {
+        return sqrt(m_X * m_X + m_Y * m_Y);
+    }
+
+    /// Convert this point into a unit point. Returns the Length.
+    double normalize()
+    {
+        double len = length();
+        m_X /= len;
+        m_Y /= len;
+        return len;
+    }
+
+};
+
+
+// Represents a simple polygon's edge
+struct Edge
+{
+    Point* m_P, *m_Q;
+
+    Edge(Point& p1, Point& p2) :m_P(&p1), m_Q(&p2)
+    {
+        if (p1.m_Y > p2.m_Y) {
+            m_Q = &p1;
+            m_P = &p2;
+        } else if (p1.m_Y == p2.m_Y) {
+            if (p1.m_X > p2.m_X) {
+                m_Q = &p1;
+                m_P = &p2;
+            } else if (p1.m_X == p2.m_X) {
+                // Repeat points
+                assert(false);
+            }
+        }
+        m_Q->m_EdgeList.push_back(this);
+    }
+};
+
+
+class TriangulationTriangle
+{
+
+public:
+
+    TriangulationTriangle(Point& a, Point& b, Point& c);
+
+/// Flags to determine if an edge is a Constrained edge
+    bool m_ConstrainedEdge[3];
+/// Flags to determine if an edge is a Delauney edge
+    bool m_DelaunayEdge[3];
+
+    Point* getPoint(const int& index);
+    Point* pointCW(Point& point);
+    Point* pointCCW(Point& point);
+    Point* oppositePoint(TriangulationTriangle& t, Point& p);
+
+    TriangulationTriangle* getNeighbor(const int& index);
+    void markNeighbor(Point* p1, Point* p2, TriangulationTriangle* t);
+    void markNeighbor(TriangulationTriangle& t);
+
+    void markConstrainedEdge(const int index);
+    void markConstrainedEdge(Edge& edge);
+    void markConstrainedEdge(Point* p, Point* q);
+
+    unsigned int index(const Point* p);
+    unsigned int edgeIndex(const Point* p1, const Point* p2);
+
+    TriangulationTriangle* neighborCW(Point& point);
+    TriangulationTriangle* 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);
+
+    void clear();
+    void clearNeighbor(TriangulationTriangle *triangle);
+    void clearNeighbors();
+    void clearDelunayEdges();
+
+    inline bool isInterior();
+    inline void isInterior(bool b);
+
+    TriangulationTriangle& neighborAcross(Point& opoint);
+
+private:
+
+    Point* m_Points[3];
+
+    TriangulationTriangle* m_Neighbors[3];
+
+    bool m_Interior;
+};
+
+inline bool cmp(const Point* a, const Point* b)
+{
+    if (a->m_Y < b->m_Y) {
+        return true;
+    } else if (a->m_Y == b->m_Y) {
+        // Make sure q is point with greater x value
+        if (a->m_X < b->m_X) {
+            return true;
+        }
+    }
+    return false;
+}
+/*
+ inline Point operator +(const Point& a, const Point& b)
+ {
+ return Point(a.x + b.x, a.y + b.y);
+ }
+
+ inline Point operator -(const Point& a, const Point& b)
+ {
+ return Point(a.x - b.x, a.y - b.y);
+ }
+
+ inline Point operator *(double s, const Point& a)
+ {
+ return Point(s * a.x, s * a.y, a.index);
+ } */
+
+inline bool operator ==(const Point& a, const Point& b)
+{
+    return a.m_X == b.m_X && a.m_Y == b.m_Y;
+}
+
+inline bool operator !=(const Point& a, const Point& b)
+{
+    return a.m_X != b.m_X && a.m_Y != b.m_Y;
+}
+
+inline double dot(const Point& a, const Point& b)
+{
+    return a.m_X * b.m_X + a.m_Y * b.m_Y;
+}
+
+inline double cross(const Point& a, const Point& b)
+{
+    return a.m_X * b.m_Y - a.m_Y * b.m_X;
+}
+
+inline Point cross(const Point& a, double s)
+{
+    return Point(s * a.m_Y, -s * a.m_X, a.m_Index);
+}
+
+inline Point cross(const double s, const Point& a)
+{
+    return Point(-s * a.m_Y, s * a.m_X, a.m_Index);
+}
+
+inline Point* TriangulationTriangle::getPoint(const int& index)
+{
+    return m_Points[index];
+}
+
+inline TriangulationTriangle* TriangulationTriangle::getNeighbor(
+        const int& index)
+{
+    return m_Neighbors[index];
+}
+
+inline bool TriangulationTriangle::contains(Point* p)
+{
+    return p == m_Points[0] || p == m_Points[1] || p == m_Points[2];
+}
+
+inline bool TriangulationTriangle::contains(const Edge& e)
+{
+    return contains(e.m_P) && contains(e.m_Q);
+}
+
+inline bool TriangulationTriangle::contains(Point* p, Point* q)
+{
+    return contains(p) && contains(q);
+}
+
+inline bool TriangulationTriangle::isInterior()
+{
+    return m_Interior;
+}
+
+inline void TriangulationTriangle::isInterior(bool b)
+{
+    m_Interior = b;
+}
+
+}
+
+#endif