summaryrefslogtreecommitdiff
path: root/polygon/poly2tri/common
diff options
context:
space:
mode:
Diffstat (limited to 'polygon/poly2tri/common')
-rw-r--r--polygon/poly2tri/common/shapes.cc500
-rw-r--r--polygon/poly2tri/common/shapes.h351
-rw-r--r--polygon/poly2tri/common/utils.h133
3 files changed, 984 insertions, 0 deletions
diff --git a/polygon/poly2tri/common/shapes.cc b/polygon/poly2tri/common/shapes.cc
new file mode 100644
index 0000000..06eb1f8
--- /dev/null
+++ b/polygon/poly2tri/common/shapes.cc
@@ -0,0 +1,500 @@
+/*
+ * 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 "shapes.h"
+#include <iostream>
+
+namespace p2t {
+Triangle::Triangle( Point& a, Point& b, Point& c )
+{
+ points_[0] = &a; points_[1] = &b; points_[2] = &c;
+ neighbors_[0] = NULL; neighbors_[1] = NULL; neighbors_[2] = NULL;
+ constrained_edge[0] = constrained_edge[1] = constrained_edge[2] = false;
+ delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
+ interior_ = false;
+}
+
+
+// Update neighbor pointers
+void Triangle::MarkNeighbor( Point* p1, Point* p2, Triangle* t )
+{
+ if( (p1 == points_[2] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[2]) )
+ neighbors_[0] = t;
+ else if( (p1 == points_[0] && p2 == points_[2]) || (p1 == points_[2] && p2 == points_[0]) )
+ neighbors_[1] = t;
+ else if( (p1 == points_[0] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[0]) )
+ neighbors_[2] = t;
+ else
+ assert( 0 );
+}
+
+
+// Exhaustive search to update neighbor pointers
+void Triangle::MarkNeighbor( Triangle& t )
+{
+ if( t.Contains( points_[1], points_[2] ) )
+ {
+ neighbors_[0] = &t;
+ t.MarkNeighbor( points_[1], points_[2], this );
+ }
+ else if( t.Contains( points_[0], points_[2] ) )
+ {
+ neighbors_[1] = &t;
+ t.MarkNeighbor( points_[0], points_[2], this );
+ }
+ else if( t.Contains( points_[0], points_[1] ) )
+ {
+ neighbors_[2] = &t;
+ t.MarkNeighbor( points_[0], points_[1], this );
+ }
+}
+
+
+/**
+ * Clears all references to all other triangles and points
+ */
+void Triangle::Clear()
+{
+ Triangle* t;
+
+ for( int i = 0; i<3; i++ )
+ {
+ t = neighbors_[i];
+
+ if( t != NULL )
+ {
+ t->ClearNeighbor( this );
+ }
+ }
+
+ ClearNeighbors();
+ points_[0] = points_[1] = points_[2] = NULL;
+}
+
+
+void Triangle::ClearNeighbor( Triangle* triangle )
+{
+ if( neighbors_[0] == triangle )
+ {
+ neighbors_[0] = NULL;
+ }
+ else if( neighbors_[1] == triangle )
+ {
+ neighbors_[1] = NULL;
+ }
+ else
+ {
+ neighbors_[2] = NULL;
+ }
+}
+
+
+void Triangle::ClearNeighbors()
+{
+ neighbors_[0] = NULL;
+ neighbors_[1] = NULL;
+ neighbors_[2] = NULL;
+}
+
+
+void Triangle::ClearDelunayEdges()
+{
+ delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
+}
+
+
+Point* Triangle::OppositePoint( Triangle& t, Point& p )
+{
+ Point* cw = t.PointCW( p );
+
+ /*
+ double x = cw->x;
+ double y = cw->y;
+
+ x = p.x;
+ y = p.y;
+ */
+
+ return PointCW( *cw );
+}
+
+
+// Legalized triangle by rotating clockwise around point(0)
+void Triangle::Legalize( Point& point )
+{
+ points_[1] = points_[0];
+ points_[0] = points_[2];
+ points_[2] = &point;
+}
+
+
+// Legalize triagnle by rotating clockwise around oPoint
+void Triangle::Legalize( Point& opoint, Point& npoint )
+{
+ if( &opoint == points_[0] )
+ {
+ points_[1] = points_[0];
+ points_[0] = points_[2];
+ points_[2] = &npoint;
+ }
+ else if( &opoint == points_[1] )
+ {
+ points_[2] = points_[1];
+ points_[1] = points_[0];
+ points_[0] = &npoint;
+ }
+ else if( &opoint == points_[2] )
+ {
+ points_[0] = points_[2];
+ points_[2] = points_[1];
+ points_[1] = &npoint;
+ }
+ else
+ {
+ assert( 0 );
+ }
+}
+
+
+int Triangle::Index( const Point* p )
+{
+ if( p == points_[0] )
+ {
+ return 0;
+ }
+ else if( p == points_[1] )
+ {
+ return 1;
+ }
+ else if( p == points_[2] )
+ {
+ return 2;
+ }
+
+ assert( 0 );
+ return 0; // you better hope its a Debug build.
+}
+
+
+int Triangle::EdgeIndex( const Point* p1, const Point* p2 )
+{
+ if( points_[0] == p1 )
+ {
+ if( points_[1] == p2 )
+ {
+ return 2;
+ }
+ else if( points_[2] == p2 )
+ {
+ return 1;
+ }
+ }
+ else if( points_[1] == p1 )
+ {
+ if( points_[2] == p2 )
+ {
+ return 0;
+ }
+ else if( points_[0] == p2 )
+ {
+ return 2;
+ }
+ }
+ else if( points_[2] == p1 )
+ {
+ if( points_[0] == p2 )
+ {
+ return 1;
+ }
+ else if( points_[1] == p2 )
+ {
+ return 0;
+ }
+ }
+
+ return -1;
+}
+
+
+void Triangle::MarkConstrainedEdge( const int index )
+{
+ constrained_edge[index] = true;
+}
+
+
+void Triangle::MarkConstrainedEdge( Edge& edge )
+{
+ MarkConstrainedEdge( edge.p, edge.q );
+}
+
+
+// Mark edge as constrained
+void Triangle::MarkConstrainedEdge( Point* p, Point* q )
+{
+ if( (q == points_[0] && p == points_[1]) || (q == points_[1] && p == points_[0]) )
+ {
+ constrained_edge[2] = true;
+ }
+ else if( (q == points_[0] && p == points_[2]) || (q == points_[2] && p == points_[0]) )
+ {
+ constrained_edge[1] = true;
+ }
+ else if( (q == points_[1] && p == points_[2]) || (q == points_[2] && p == points_[1]) )
+ {
+ constrained_edge[0] = true;
+ }
+}
+
+
+// The point counter-clockwise to given point
+Point* Triangle::PointCW( Point& point )
+{
+ if( &point == points_[0] )
+ {
+ return points_[2];
+ }
+ else if( &point == points_[1] )
+ {
+ return points_[0];
+ }
+ else if( &point == points_[2] )
+ {
+ return points_[1];
+ }
+
+ assert( 0 );
+ return NULL; // you better hope its a Debug build.
+}
+
+
+// The point counter-clockwise to given point
+Point* Triangle::PointCCW( Point& point )
+{
+ if( &point == points_[0] )
+ {
+ return points_[1];
+ }
+ else if( &point == points_[1] )
+ {
+ return points_[2];
+ }
+ else if( &point == points_[2] )
+ {
+ return points_[0];
+ }
+
+ assert( 0 );
+ return NULL; // you better hope its a Debug build.
+}
+
+
+// The neighbor clockwise to given point
+Triangle* Triangle::NeighborCW( Point& point )
+{
+ if( &point == points_[0] )
+ {
+ return neighbors_[1];
+ }
+ else if( &point == points_[1] )
+ {
+ return neighbors_[2];
+ }
+
+ return neighbors_[0];
+}
+
+
+// The neighbor counter-clockwise to given point
+Triangle* Triangle::NeighborCCW( Point& point )
+{
+ if( &point == points_[0] )
+ {
+ return neighbors_[2];
+ }
+ else if( &point == points_[1] )
+ {
+ return neighbors_[0];
+ }
+
+ return neighbors_[1];
+}
+
+
+bool Triangle::GetConstrainedEdgeCCW( Point& p )
+{
+ if( &p == points_[0] )
+ {
+ return constrained_edge[2];
+ }
+ else if( &p == points_[1] )
+ {
+ return constrained_edge[0];
+ }
+
+ return constrained_edge[1];
+}
+
+
+bool Triangle::GetConstrainedEdgeCW( Point& p )
+{
+ if( &p == points_[0] )
+ {
+ return constrained_edge[1];
+ }
+ else if( &p == points_[1] )
+ {
+ return constrained_edge[2];
+ }
+
+ return constrained_edge[0];
+}
+
+
+void Triangle::SetConstrainedEdgeCCW( Point& p, bool ce )
+{
+ if( &p == points_[0] )
+ {
+ constrained_edge[2] = ce;
+ }
+ else if( &p == points_[1] )
+ {
+ constrained_edge[0] = ce;
+ }
+ else
+ {
+ constrained_edge[1] = ce;
+ }
+}
+
+
+void Triangle::SetConstrainedEdgeCW( Point& p, bool ce )
+{
+ if( &p == points_[0] )
+ {
+ constrained_edge[1] = ce;
+ }
+ else if( &p == points_[1] )
+ {
+ constrained_edge[2] = ce;
+ }
+ else
+ {
+ constrained_edge[0] = ce;
+ }
+}
+
+
+bool Triangle::GetDelunayEdgeCCW( Point& p )
+{
+ if( &p == points_[0] )
+ {
+ return delaunay_edge[2];
+ }
+ else if( &p == points_[1] )
+ {
+ return delaunay_edge[0];
+ }
+
+ return delaunay_edge[1];
+}
+
+
+bool Triangle::GetDelunayEdgeCW( Point& p )
+{
+ if( &p == points_[0] )
+ {
+ return delaunay_edge[1];
+ }
+ else if( &p == points_[1] )
+ {
+ return delaunay_edge[2];
+ }
+
+ return delaunay_edge[0];
+}
+
+
+void Triangle::SetDelunayEdgeCCW( Point& p, bool e )
+{
+ if( &p == points_[0] )
+ {
+ delaunay_edge[2] = e;
+ }
+ else if( &p == points_[1] )
+ {
+ delaunay_edge[0] = e;
+ }
+ else
+ {
+ delaunay_edge[1] = e;
+ }
+}
+
+
+void Triangle::SetDelunayEdgeCW( Point& p, bool e )
+{
+ if( &p == points_[0] )
+ {
+ delaunay_edge[1] = e;
+ }
+ else if( &p == points_[1] )
+ {
+ delaunay_edge[2] = e;
+ }
+ else
+ {
+ delaunay_edge[0] = e;
+ }
+}
+
+
+// The neighbor across to given point
+Triangle& Triangle::NeighborAcross( Point& opoint )
+{
+ if( &opoint == points_[0] )
+ {
+ return *neighbors_[0];
+ }
+ else if( &opoint == points_[1] )
+ {
+ return *neighbors_[1];
+ }
+
+ return *neighbors_[2];
+}
+
+
+void Triangle::DebugPrint()
+{
+ std::cout << points_[0]->x << "," << points_[0]->y << " ";
+ std::cout << points_[1]->x << "," << points_[1]->y << " ";
+ std::cout << points_[2]->x << "," << points_[2]->y << "\n";
+}
+}
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
diff --git a/polygon/poly2tri/common/utils.h b/polygon/poly2tri/common/utils.h
new file mode 100644
index 0000000..3de9fb1
--- /dev/null
+++ b/polygon/poly2tri/common/utils.h
@@ -0,0 +1,133 @@
+/*
+ * 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.
+ */
+
+#ifndef UTILS_H
+#define UTILS_H
+
+// Otherwise #defines like M_PI are undeclared under Visual Studio
+#define _USE_MATH_DEFINES
+
+#include <exception>
+#include <math.h>
+
+namespace p2t {
+const double PI_3div4 = 3 * M_PI / 4;
+const double PI_div2 = 1.57079632679489661923;
+const double EPSILON = 1e-12;
+
+enum Orientation {
+ CW, CCW, COLLINEAR
+};
+
+/**
+ * Forumla to calculate signed area<br>
+ * Positive if CCW<br>
+ * Negative if CW<br>
+ * 0 if collinear<br>
+ * <pre>
+ * A[P1,P2,P3] = (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
+ * = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
+ * </pre>
+ */
+Orientation Orient2d( Point& pa, Point& pb, Point& pc )
+{
+ double detleft = (pa.x - pc.x) * (pb.y - pc.y);
+ double detright = (pa.y - pc.y) * (pb.x - pc.x);
+ double val = detleft - detright;
+
+ if( val > -EPSILON && val < EPSILON )
+ {
+ return COLLINEAR;
+ }
+ else if( val > 0 )
+ {
+ return CCW;
+ }
+
+ return CW;
+}
+
+
+/*
+ * bool InScanArea(Point& pa, Point& pb, Point& pc, Point& pd)
+ * {
+ * double pdx = pd.x;
+ * double pdy = pd.y;
+ * double adx = pa.x - pdx;
+ * double ady = pa.y - pdy;
+ * double bdx = pb.x - pdx;
+ * double bdy = pb.y - pdy;
+ *
+ * double adxbdy = adx * bdy;
+ * double bdxady = bdx * ady;
+ * double oabd = adxbdy - bdxady;
+ *
+ * if (oabd <= EPSILON) {
+ * return false;
+ * }
+ *
+ * double cdx = pc.x - pdx;
+ * double cdy = pc.y - pdy;
+ *
+ * double cdxady = cdx * ady;
+ * double adxcdy = adx * cdy;
+ * double ocad = cdxady - adxcdy;
+ *
+ * if (ocad <= EPSILON) {
+ * return false;
+ * }
+ *
+ * return true;
+ * }
+ *
+ */
+
+bool InScanArea( Point& pa, Point& pb, Point& pc, Point& pd )
+{
+ double oadb = (pa.x - pb.x) * (pd.y - pb.y) - (pd.x - pb.x) * (pa.y - pb.y);
+
+ if( oadb >= -EPSILON )
+ {
+ return false;
+ }
+
+ double oadc = (pa.x - pc.x) * (pd.y - pc.y) - (pd.x - pc.x) * (pa.y - pc.y);
+
+ if( oadc <= EPSILON )
+ {
+ return false;
+ }
+
+ return true;
+}
+}
+
+#endif
generated by cgit (git 2.34.1) at 2024-12-19 11:56:19 +0000