Polygons
+ {
+ get { return _polygons; }
+ }
+
+ public void Add(Polygon p)
+ {
+ _polygons.Add(p);
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/Sets/ConstrainedPointSet.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/Sets/ConstrainedPointSet.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,114 @@
+/* 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.
+ */
+
+using System.Collections.Generic;
+
+namespace Poly2Tri.Triangulation.Sets
+{
+ /*
+ * Extends the PointSet by adding some Constraints on how it will be triangulated
+ * A constraint defines an edge between two points in the set, these edges can not
+ * be crossed. They will be enforced triangle edges after a triangulation.
+ *
+ *
+ *
+ * @author Thomas Åhlén, thahlen@gmail.com
+ */
+
+ public class ConstrainedPointSet : PointSet
+ {
+ private List _constrainedPointList = null;
+
+ public ConstrainedPointSet(List points, int[] index)
+ : base(points)
+ {
+ EdgeIndex = index;
+ }
+
+ /**
+ *
+ * @param points - A list of all points in PointSet
+ * @param constraints - Pairs of two points defining a constraint, all points must be part of given PointSet!
+ */
+
+ public ConstrainedPointSet(List points, IEnumerable constraints)
+ : base(points)
+ {
+ _constrainedPointList = new List();
+ _constrainedPointList.AddRange(constraints);
+ }
+
+ public int[] EdgeIndex { get; private set; }
+
+ public override TriangulationMode TriangulationMode
+ {
+ get { return TriangulationMode.Constrained; }
+ }
+
+ public override void PrepareTriangulation(TriangulationContext tcx)
+ {
+ base.PrepareTriangulation(tcx);
+ if (_constrainedPointList != null)
+ {
+ TriangulationPoint p1, p2;
+ List.Enumerator iterator = _constrainedPointList.GetEnumerator();
+ while (iterator.MoveNext())
+ {
+ p1 = iterator.Current;
+ iterator.MoveNext();
+ p2 = iterator.Current;
+ tcx.NewConstraint(p1, p2);
+ }
+ }
+ else
+ {
+ for (int i = 0; i < EdgeIndex.Length; i += 2)
+ {
+ // XXX: must change!!
+ tcx.NewConstraint(Points[EdgeIndex[i]], Points[EdgeIndex[i + 1]]);
+ }
+ }
+ }
+
+ /**
+ * TODO: TO BE IMPLEMENTED!
+ * Peforms a validation on given input
+ * 1. Check's if there any constraint edges are crossing or collinear
+ * 2.
+ * @return
+ */
+
+ public bool isValid()
+ {
+ return true;
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/Sets/PointSet.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/Sets/PointSet.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,84 @@
+/* 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.
+ */
+
+using System.Collections.Generic;
+using Poly2Tri.Triangulation.Delaunay;
+
+namespace Poly2Tri.Triangulation.Sets
+{
+ public class PointSet : Triangulatable
+ {
+ public PointSet(List points)
+ {
+ Points = new List(points);
+ }
+
+ #region Triangulatable Members
+
+ public IList Points { get; private set; }
+ public IList Triangles { get; private set; }
+
+ public virtual TriangulationMode TriangulationMode
+ {
+ get { return TriangulationMode.Unconstrained; }
+ }
+
+ public void AddTriangle(DelaunayTriangle t)
+ {
+ Triangles.Add(t);
+ }
+
+ public void AddTriangles(IEnumerable list)
+ {
+ foreach (DelaunayTriangle tri in list) Triangles.Add(tri);
+ }
+
+ public void ClearTriangles()
+ {
+ Triangles.Clear();
+ }
+
+ public virtual void PrepareTriangulation(TriangulationContext tcx)
+ {
+ if (Triangles == null)
+ {
+ Triangles = new List(Points.Count);
+ }
+ else
+ {
+ Triangles.Clear();
+ }
+ tcx.Points.AddRange(Points);
+ }
+
+ #endregion
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/TriangulationConstraint.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/TriangulationConstraint.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,46 @@
+/* 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.
+ */
+
+/**
+ * Forces a triangle edge between two points p and q
+ * when triangulating. For example used to enforce
+ * Polygon Edges during a polygon triangulation.
+ *
+ * @author Thomas Åhlén, thahlen@gmail.com
+ */
+namespace Poly2Tri.Triangulation
+{
+ public class TriangulationConstraint
+ {
+ public TriangulationPoint P;
+ public TriangulationPoint Q;
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/TriangulationContext.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/TriangulationContext.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,87 @@
+/* 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.
+ */
+
+using System.Collections.Generic;
+using System.Runtime.CompilerServices;
+using Poly2Tri.Triangulation.Delaunay;
+
+namespace Poly2Tri.Triangulation
+{
+ public abstract class TriangulationContext
+ {
+ public readonly List Points = new List(200);
+ public readonly List Triangles = new List();
+
+#pragma warning disable 414
+ private int _stepTime = -1;
+#pragma warning restore 414
+
+ public TriangulationContext()
+ {
+ Terminated = false;
+ }
+
+ public TriangulationMode TriangulationMode { get; protected set; }
+ public Triangulatable Triangulatable { get; private set; }
+
+ public bool WaitUntilNotified { get; private set; }
+ public bool Terminated { get; set; }
+
+ public int StepCount { get; private set; }
+ public virtual bool IsDebugEnabled { get; protected set; }
+
+ public void Done()
+ {
+ StepCount++;
+ }
+
+ public virtual void PrepareTriangulation(Triangulatable t)
+ {
+ Triangulatable = t;
+ TriangulationMode = t.TriangulationMode;
+ t.PrepareTriangulation(this);
+ }
+
+ public abstract TriangulationConstraint NewConstraint(TriangulationPoint a, TriangulationPoint b);
+
+ [MethodImpl(MethodImplOptions.Synchronized)]
+ public void Update(string message)
+ {
+ }
+
+ public virtual void Clear()
+ {
+ Points.Clear();
+ Terminated = false;
+ StepCount = 0;
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/TriangulationMode.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/TriangulationMode.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,40 @@
+/* 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.
+ */
+
+namespace Poly2Tri.Triangulation
+{
+ public enum TriangulationMode
+ {
+ Unconstrained,
+ Constrained,
+ Polygon
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/TriangulationPoint.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/TriangulationPoint.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,82 @@
+/* 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.
+ */
+
+using System.Collections.Generic;
+using Poly2Tri.Triangulation.Delaunay.Sweep;
+
+namespace Poly2Tri.Triangulation
+{
+ public class TriangulationPoint
+ {
+ // List of edges this point constitutes an upper ending point (CDT)
+
+ public double X, Y;
+
+ public TriangulationPoint(double x, double y)
+ {
+ X = x;
+ Y = y;
+ }
+
+ public List Edges { get; private set; }
+
+ public float Xf
+ {
+ get { return (float) X; }
+ set { X = value; }
+ }
+
+ public float Yf
+ {
+ get { return (float) Y; }
+ set { Y = value; }
+ }
+
+ public bool HasEdges
+ {
+ get { return Edges != null; }
+ }
+
+ public override string ToString()
+ {
+ return "[" + X + "," + Y + "]";
+ }
+
+ public void AddEdge(DTSweepConstraint e)
+ {
+ if (Edges == null)
+ {
+ Edges = new List();
+ }
+ Edges.Add(e);
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/TriangulationUtil.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/TriangulationUtil.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,160 @@
+/* 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.
+ */
+
+using FarseerPhysics.Common.Decomposition.CDT;
+
+namespace Poly2Tri.Triangulation
+{
+ /**
+ * @author Thomas Åhlén, thahlen@gmail.com
+ */
+
+ public class TriangulationUtil
+ {
+ public static double EPSILON = 1e-12;
+
+ ///
+ /// Requirements:
+ /// 1. a,b and c form a triangle.
+ /// 2. a and d is know to be on opposite side of bc
+ ///
+ /// a
+ /// +
+ /// / \
+ /// / \
+ /// b/ \c
+ /// +-------+
+ /// / B \
+ /// / \
+ ///
+ /// Facts:
+ /// d has to be in area B to have a chance to be inside the circle formed by a,b and c
+ /// d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW
+ /// This preknowledge gives us a way to optimize the incircle test
+ ///
+ /// triangle point, opposite d
+ /// triangle point
+ /// triangle point
+ /// point opposite a
+ /// true if d is inside circle, false if on circle edge
+ public static bool SmartIncircle(TriangulationPoint pa, TriangulationPoint pb, TriangulationPoint pc,
+ TriangulationPoint 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;
+ // oabd = orient2d(pa,pb,pd);
+ if (oabd <= 0) return false;
+
+ double cdx = pc.X - pdx;
+ double cdy = pc.Y - pdy;
+
+ double cdxady = cdx*ady;
+ double adxcdy = adx*cdy;
+ double ocad = cdxady - adxcdy;
+ // ocad = orient2d(pc,pa,pd);
+ if (ocad <= 0) return false;
+
+ double bdxcdy = bdx*cdy;
+ double cdxbdy = cdx*bdy;
+
+ double alift = adx*adx + ady*ady;
+ double blift = bdx*bdx + bdy*bdy;
+ double clift = cdx*cdx + cdy*cdy;
+
+ double det = alift*(bdxcdy - cdxbdy) + blift*ocad + clift*oabd;
+
+ return det > 0;
+ }
+
+ public static bool InScanArea(TriangulationPoint pa, TriangulationPoint pb, TriangulationPoint pc,
+ TriangulationPoint 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;
+ // oabd = orient2d(pa,pb,pd);
+ if (oabd <= 0)
+ {
+ return false;
+ }
+
+ double cdx = pc.X - pdx;
+ double cdy = pc.Y - pdy;
+
+ double cdxady = cdx*ady;
+ double adxcdy = adx*cdy;
+ double ocad = cdxady - adxcdy;
+ // ocad = orient2d(pc,pa,pd);
+ if (ocad <= 0)
+ {
+ return false;
+ }
+ return true;
+ }
+
+ /// Forumla to calculate signed area
+ /// Positive if CCW
+ /// Negative if CW
+ /// 0 if collinear
+ /// A[P1,P2,P3] = (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
+ /// = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
+ public static Orientation Orient2d(TriangulationPoint pa, TriangulationPoint pb, TriangulationPoint 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 Orientation.Collinear;
+ }
+ else if (val > 0)
+ {
+ return Orientation.CCW;
+ }
+ return Orientation.CW;
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/Util/FixedArray3.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/Util/FixedArray3.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,118 @@
+/* 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.
+ */
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+
+namespace Poly2Tri.Triangulation.Util
+{
+ public struct FixedArray3 : IEnumerable where T : class
+ {
+ public T _0, _1, _2;
+
+ public T this[int index]
+ {
+ get
+ {
+ switch (index)
+ {
+ case 0:
+ return _0;
+ case 1:
+ return _1;
+ case 2:
+ return _2;
+ default:
+ throw new IndexOutOfRangeException();
+ }
+ }
+ set
+ {
+ switch (index)
+ {
+ case 0:
+ _0 = value;
+ break;
+ case 1:
+ _1 = value;
+ break;
+ case 2:
+ _2 = value;
+ break;
+ default:
+ throw new IndexOutOfRangeException();
+ }
+ }
+ }
+
+ #region IEnumerable Members
+
+ public IEnumerator GetEnumerator()
+ {
+ return Enumerate().GetEnumerator();
+ }
+
+ IEnumerator IEnumerable.GetEnumerator()
+ {
+ return GetEnumerator();
+ }
+
+ #endregion
+
+ public bool Contains(T value)
+ {
+ for (int i = 0; i < 3; ++i) if (this[i] == value) return true;
+ return false;
+ }
+
+ public int IndexOf(T value)
+ {
+ for (int i = 0; i < 3; ++i) if (this[i] == value) return i;
+ return -1;
+ }
+
+ public void Clear()
+ {
+ _0 = _1 = _2 = null;
+ }
+
+ public void Clear(T value)
+ {
+ for (int i = 0; i < 3; ++i) if (this[i] == value) this[i] = null;
+ }
+
+ private IEnumerable Enumerate()
+ {
+ for (int i = 0; i < 3; ++i) yield return this[i];
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/Util/FixedBitArray3.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/Util/FixedBitArray3.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,118 @@
+/* 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.
+ */
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+
+namespace Poly2Tri.Triangulation.Util
+{
+ public struct FixedBitArray3 : IEnumerable
+ {
+ public bool _0, _1, _2;
+
+ public bool this[int index]
+ {
+ get
+ {
+ switch (index)
+ {
+ case 0:
+ return _0;
+ case 1:
+ return _1;
+ case 2:
+ return _2;
+ default:
+ throw new IndexOutOfRangeException();
+ }
+ }
+ set
+ {
+ switch (index)
+ {
+ case 0:
+ _0 = value;
+ break;
+ case 1:
+ _1 = value;
+ break;
+ case 2:
+ _2 = value;
+ break;
+ default:
+ throw new IndexOutOfRangeException();
+ }
+ }
+ }
+
+ #region IEnumerable Members
+
+ public IEnumerator GetEnumerator()
+ {
+ return Enumerate().GetEnumerator();
+ }
+
+ IEnumerator IEnumerable.GetEnumerator()
+ {
+ return GetEnumerator();
+ }
+
+ #endregion
+
+ public bool Contains(bool value)
+ {
+ for (int i = 0; i < 3; ++i) if (this[i] == value) return true;
+ return false;
+ }
+
+ public int IndexOf(bool value)
+ {
+ for (int i = 0; i < 3; ++i) if (this[i] == value) return i;
+ return -1;
+ }
+
+ public void Clear()
+ {
+ _0 = _1 = _2 = false;
+ }
+
+ public void Clear(bool value)
+ {
+ for (int i = 0; i < 3; ++i) if (this[i] == value) this[i] = false;
+ }
+
+ private IEnumerable Enumerate()
+ {
+ for (int i = 0; i < 3; ++i) yield return this[i];
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/Util/PointGenerator.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/Util/PointGenerator.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,38 @@
+using System;
+using System.Collections.Generic;
+
+namespace Poly2Tri.Triangulation.Util
+{
+ public class PointGenerator
+ {
+ private static readonly Random RNG = new Random();
+
+ public static List UniformDistribution(int n, double scale)
+ {
+ List points = new List();
+ for (int i = 0; i < n; i++)
+ {
+ points.Add(new TriangulationPoint(scale*(0.5 - RNG.NextDouble()), scale*(0.5 - RNG.NextDouble())));
+ }
+ return points;
+ }
+
+ public static List UniformGrid(int n, double scale)
+ {
+ double x = 0;
+ double size = scale/n;
+ double halfScale = 0.5*scale;
+
+ List points = new List();
+ for (int i = 0; i < n + 1; i++)
+ {
+ x = halfScale - i*size;
+ for (int j = 0; j < n + 1; j++)
+ {
+ points.Add(new TriangulationPoint(x, halfScale - j*size));
+ }
+ }
+ return points;
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDT/Util/PolygonGenerator.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDT/Util/PolygonGenerator.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,98 @@
+/* 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.
+ */
+
+using System;
+using Poly2Tri.Triangulation.Polygon;
+
+namespace Poly2Tri.Triangulation.Util
+{
+ public class PolygonGenerator
+ {
+ private static readonly Random RNG = new Random();
+
+ private static double PI_2 = 2.0*Math.PI;
+
+ public static Polygon.Polygon RandomCircleSweep(double scale, int vertexCount)
+ {
+ PolygonPoint point;
+ PolygonPoint[] points;
+ double radius = scale/4;
+
+ points = new PolygonPoint[vertexCount];
+ for (int i = 0; i < vertexCount; i++)
+ {
+ do
+ {
+ if (i%250 == 0)
+ {
+ radius += scale/2*(0.5 - RNG.NextDouble());
+ }
+ else if (i%50 == 0)
+ {
+ radius += scale/5*(0.5 - RNG.NextDouble());
+ }
+ else
+ {
+ radius += 25*scale/vertexCount*(0.5 - RNG.NextDouble());
+ }
+ radius = radius > scale/2 ? scale/2 : radius;
+ radius = radius < scale/10 ? scale/10 : radius;
+ } while (radius < scale/10 || radius > scale/2);
+ point = new PolygonPoint(radius*Math.Cos((PI_2*i)/vertexCount),
+ radius*Math.Sin((PI_2*i)/vertexCount));
+ points[i] = point;
+ }
+ return new Polygon.Polygon(points);
+ }
+
+ public static Polygon.Polygon RandomCircleSweep2(double scale, int vertexCount)
+ {
+ PolygonPoint point;
+ PolygonPoint[] points;
+ double radius = scale/4;
+
+ points = new PolygonPoint[vertexCount];
+ for (int i = 0; i < vertexCount; i++)
+ {
+ do
+ {
+ radius += scale/5*(0.5 - RNG.NextDouble());
+ radius = radius > scale/2 ? scale/2 : radius;
+ radius = radius < scale/10 ? scale/10 : radius;
+ } while (radius < scale/10 || radius > scale/2);
+ point = new PolygonPoint(radius*Math.Cos((PI_2*i)/vertexCount),
+ radius*Math.Sin((PI_2*i)/vertexCount));
+ points[i] = point;
+ }
+ return new Polygon.Polygon(points);
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/CDTDecomposer.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/CDTDecomposer.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,110 @@
+/* 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.
+ */
+
+using System.Collections.Generic;
+using Microsoft.Xna.Framework;
+using Poly2Tri.Triangulation;
+using Poly2Tri.Triangulation.Delaunay;
+using Poly2Tri.Triangulation.Delaunay.Sweep;
+using Poly2Tri.Triangulation.Polygon;
+
+using System.Linq;
+
+namespace FarseerPhysics.Common.Decomposition
+{
+ public static class CDTDecomposer
+ {
+ public static List ConvexPartition(Vertices vertices)
+ {
+ Polygon poly = new Polygon();
+
+ foreach (Vector2 vertex in vertices)
+ {
+ poly.Points.Add(new TriangulationPoint(vertex.X, vertex.Y));
+ }
+
+ DTSweepContext tcx = new DTSweepContext();
+ tcx.PrepareTriangulation(poly);
+ DTSweep.Triangulate(tcx);
+
+ List results = new List();
+
+ foreach (DelaunayTriangle triangle in poly.Triangles)
+ {
+ Vertices v = new Vertices();
+ foreach (TriangulationPoint p in triangle.Points)
+ {
+ v.Add(new Vector2((float)p.X, (float)p.Y));
+ }
+ results.Add(v);
+ }
+
+ return results;
+ }
+
+ public static List ConvexPartition(DetectedVertices vertices)
+ {
+ Polygon poly = new Polygon();
+ foreach (var vertex in vertices)
+ poly.Points.Add(new TriangulationPoint(vertex.X, vertex.Y));
+
+ if (vertices.Holes != null)
+ {
+ foreach (var holeVertices in vertices.Holes)
+ {
+ Polygon hole = new Polygon();
+ foreach (var vertex in holeVertices)
+ hole.Points.Add(new TriangulationPoint(vertex.X, vertex.Y));
+
+ poly.AddHole(hole);
+ }
+ }
+
+ DTSweepContext tcx = new DTSweepContext();
+ tcx.PrepareTriangulation(poly);
+ DTSweep.Triangulate(tcx);
+
+ List results = new List();
+
+ foreach (DelaunayTriangle triangle in poly.Triangles)
+ {
+ Vertices v = new Vertices();
+ foreach (TriangulationPoint p in triangle.Points)
+ {
+ v.Add(new Vector2((float)p.X, (float)p.Y));
+ }
+ results.Add(v);
+ }
+
+ return results;
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/EarclipDecomposer.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/EarclipDecomposer.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,691 @@
+/*
+ * C# Version Ported by Matt Bettcher and Ian Qvist 2009-2010
+ *
+ * Original C++ Version Copyright (c) 2007 Eric Jordan
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ * 3. This notice may not be removed or altered from any source distribution.
+ */
+
+using System;
+using System.Collections.Generic;
+using FarseerPhysics.Common.PolygonManipulation;
+using Microsoft.Xna.Framework;
+
+namespace FarseerPhysics.Common.Decomposition
+{
+ ///
+ /// Ported from jBox2D. Original author: ewjordan
+ /// Triangulates a polygon using simple ear-clipping algorithm.
+ ///
+ /// Only works on simple polygons.
+ ///
+ /// Triangles may be degenerate, especially if you have identical points
+ /// in the input to the algorithm. Check this before you use them.
+ ///
+ public static class EarclipDecomposer
+ {
+ //box2D rev 32 - for details, see http://www.box2d.org/forum/viewtopic.php?f=4&t=83&start=50
+
+ private const float Tol = .001f;
+
+ ///
+ /// Decomposes a non-convex polygon into a number of convex polygons, up
+ /// to maxPolys (remaining pieces are thrown out).
+ ///
+ /// Each resulting polygon will have no more than Settings.MaxPolygonVertices
+ /// vertices.
+ ///
+ /// Warning: Only works on simple polygons
+ ///
+ /// The vertices.
+ ///
+ public static List ConvexPartition(Vertices vertices)
+ {
+ return ConvexPartition(vertices, int.MaxValue, 0);
+ }
+
+ ///
+ /// Decomposes a non-convex polygon into a number of convex polygons, up
+ /// to maxPolys (remaining pieces are thrown out).
+ /// Each resulting polygon will have no more than Settings.MaxPolygonVertices
+ /// vertices.
+ /// Warning: Only works on simple polygons
+ ///
+ /// The vertices.
+ /// The maximum number of polygons.
+ /// The tolerance.
+ ///
+ public static List ConvexPartition(Vertices vertices, int maxPolys, float tolerance)
+ {
+ if (vertices.Count < 3)
+ return new List { vertices };
+ /*
+ if (vertices.IsConvex() && vertices.Count <= Settings.MaxPolygonVertices)
+ {
+ if (vertices.IsCounterClockWise())
+ {
+ Vertices tempP = new Vertices(vertices);
+ tempP.Reverse();
+ tempP = SimplifyTools.CollinearSimplify(tempP);
+ tempP.ForceCounterClockWise();
+ return new List { tempP };
+ }
+ vertices = SimplifyTools.CollinearSimplify(vertices);
+ vertices.ForceCounterClockWise();
+ return new List { vertices };
+ }
+ */
+ List triangulated;
+
+ if (vertices.IsCounterClockWise())
+ {
+ Vertices tempP = new Vertices(vertices);
+ tempP.Reverse();
+ triangulated = TriangulatePolygon(tempP);
+ }
+ else
+ {
+ triangulated = TriangulatePolygon(vertices);
+ }
+ if (triangulated.Count < 1)
+ {
+ //Still no luck? Oh well...
+ throw new Exception("Can't triangulate your polygon.");
+ }
+
+ List polygonizedTriangles = PolygonizeTriangles(triangulated, maxPolys, tolerance);
+
+ //The polygonized triangles are not guaranteed to be without collinear points. We remove
+ //them to be sure.
+ for (int i = 0; i < polygonizedTriangles.Count; i++)
+ {
+ polygonizedTriangles[i] = SimplifyTools.CollinearSimplify(polygonizedTriangles[i], 0);
+ }
+
+ //Remove empty vertice collections
+ for (int i = polygonizedTriangles.Count - 1; i >= 0; i--)
+ {
+ if (polygonizedTriangles[i].Count == 0)
+ polygonizedTriangles.RemoveAt(i);
+ }
+
+ return polygonizedTriangles;
+ }
+
+ ///
+ /// Turns a list of triangles into a list of convex polygons. Very simple
+ /// method - start with a seed triangle, keep adding triangles to it until
+ /// you can't add any more without making the polygon non-convex.
+ ///
+ /// Returns an integer telling how many polygons were created. Will fill
+ /// polys array up to polysLength entries, which may be smaller or larger
+ /// than the return value.
+ ///
+ /// Takes O(N///P) where P is the number of resultant polygons, N is triangle
+ /// count.
+ ///
+ /// The final polygon list will not necessarily be minimal, though in
+ /// practice it works fairly well.
+ ///
+ /// The triangulated.
+ ///The maximun number of polygons
+ ///The tolerance
+ ///
+ public static List PolygonizeTriangles(List triangulated, int maxPolys, float tolerance)
+ {
+ List polys = new List(50);
+
+ int polyIndex = 0;
+
+ if (triangulated.Count <= 0)
+ {
+ //return empty polygon list
+ return polys;
+ }
+
+ bool[] covered = new bool[triangulated.Count];
+ for (int i = 0; i < triangulated.Count; ++i)
+ {
+ covered[i] = false;
+
+ //Check here for degenerate triangles
+ if (((triangulated[i].X[0] == triangulated[i].X[1]) && (triangulated[i].Y[0] == triangulated[i].Y[1]))
+ ||
+ ((triangulated[i].X[1] == triangulated[i].X[2]) && (triangulated[i].Y[1] == triangulated[i].Y[2]))
+ ||
+ ((triangulated[i].X[0] == triangulated[i].X[2]) && (triangulated[i].Y[0] == triangulated[i].Y[2])))
+ {
+ covered[i] = true;
+ }
+ }
+
+ bool notDone = true;
+ while (notDone)
+ {
+ int currTri = -1;
+ for (int i = 0; i < triangulated.Count; ++i)
+ {
+ if (covered[i])
+ continue;
+ currTri = i;
+ break;
+ }
+ if (currTri == -1)
+ {
+ notDone = false;
+ }
+ else
+ {
+ Vertices poly = new Vertices(3);
+
+ for (int i = 0; i < 3; i++)
+ {
+ poly.Add(new Vector2(triangulated[currTri].X[i], triangulated[currTri].Y[i]));
+ }
+
+ covered[currTri] = true;
+ int index = 0;
+ for (int i = 0; i < 2 * triangulated.Count; ++i, ++index)
+ {
+ while (index >= triangulated.Count) index -= triangulated.Count;
+ if (covered[index])
+ {
+ continue;
+ }
+ Vertices newP = AddTriangle(triangulated[index], poly);
+ if (newP == null)
+ continue; // is this right
+
+ if (newP.Count > Settings.MaxPolygonVertices)
+ continue;
+
+ if (newP.IsConvex())
+ {
+ //Or should it be IsUsable? Maybe re-write IsConvex to apply the angle threshold from Box2d
+ poly = new Vertices(newP);
+ covered[index] = true;
+ }
+ }
+
+ //We have a maximum of polygons that we need to keep under.
+ if (polyIndex < maxPolys)
+ {
+ //SimplifyTools.MergeParallelEdges(poly, tolerance);
+
+ //If identical points are present, a triangle gets
+ //borked by the MergeParallelEdges function, hence
+ //the vertex number check
+ if (poly.Count >= 3)
+ polys.Add(new Vertices(poly));
+ //else
+ // printf("Skipping corrupt poly\n");
+ }
+ if (poly.Count >= 3)
+ polyIndex++; //Must be outside (polyIndex < polysLength) test
+ }
+ }
+
+ return polys;
+ }
+
+ ///
+ /// Triangulates a polygon using simple ear-clipping algorithm. Returns
+ /// size of Triangle array unless the polygon can't be triangulated.
+ /// This should only happen if the polygon self-intersects,
+ /// though it will not _always_ return null for a bad polygon - it is the
+ /// caller's responsibility to check for self-intersection, and if it
+ /// doesn't, it should at least check that the return value is non-null
+ /// before using. You're warned!
+ ///
+ /// Triangles may be degenerate, especially if you have identical points
+ /// in the input to the algorithm. Check this before you use them.
+ ///
+ /// This is totally unoptimized, so for large polygons it should not be part
+ /// of the simulation loop.
+ ///
+ /// Warning: Only works on simple polygons.
+ ///
+ ///
+ public static List TriangulatePolygon(Vertices vertices)
+ {
+ List results = new List();
+ if (vertices.Count < 3)
+ return new List();
+
+ //Recurse and split on pinch points
+ Vertices pA, pB;
+ Vertices pin = new Vertices(vertices);
+ if (ResolvePinchPoint(pin, out pA, out pB))
+ {
+ List mergeA = TriangulatePolygon(pA);
+ List mergeB = TriangulatePolygon(pB);
+
+ if (mergeA.Count == -1 || mergeB.Count == -1)
+ throw new Exception("Can't triangulate your polygon.");
+
+ for (int i = 0; i < mergeA.Count; ++i)
+ {
+ results.Add(new Triangle(mergeA[i]));
+ }
+ for (int i = 0; i < mergeB.Count; ++i)
+ {
+ results.Add(new Triangle(mergeB[i]));
+ }
+
+ return results;
+ }
+
+ Triangle[] buffer = new Triangle[vertices.Count - 2];
+ int bufferSize = 0;
+ float[] xrem = new float[vertices.Count];
+ float[] yrem = new float[vertices.Count];
+ for (int i = 0; i < vertices.Count; ++i)
+ {
+ xrem[i] = vertices[i].X;
+ yrem[i] = vertices[i].Y;
+ }
+
+ int vNum = vertices.Count;
+
+ while (vNum > 3)
+ {
+ // Find an ear
+ int earIndex = -1;
+ float earMaxMinCross = -10.0f;
+ for (int i = 0; i < vNum; ++i)
+ {
+ if (IsEar(i, xrem, yrem, vNum))
+ {
+ int lower = Remainder(i - 1, vNum);
+ int upper = Remainder(i + 1, vNum);
+ Vector2 d1 = new Vector2(xrem[upper] - xrem[i], yrem[upper] - yrem[i]);
+ Vector2 d2 = new Vector2(xrem[i] - xrem[lower], yrem[i] - yrem[lower]);
+ Vector2 d3 = new Vector2(xrem[lower] - xrem[upper], yrem[lower] - yrem[upper]);
+
+ d1.Normalize();
+ d2.Normalize();
+ d3.Normalize();
+ float cross12;
+ MathUtils.Cross(ref d1, ref d2, out cross12);
+ cross12 = Math.Abs(cross12);
+
+ float cross23;
+ MathUtils.Cross(ref d2, ref d3, out cross23);
+ cross23 = Math.Abs(cross23);
+
+ float cross31;
+ MathUtils.Cross(ref d3, ref d1, out cross31);
+ cross31 = Math.Abs(cross31);
+
+ //Find the maximum minimum angle
+ float minCross = Math.Min(cross12, Math.Min(cross23, cross31));
+ if (minCross > earMaxMinCross)
+ {
+ earIndex = i;
+ earMaxMinCross = minCross;
+ }
+ }
+ }
+
+ // If we still haven't found an ear, we're screwed.
+ // Note: sometimes this is happening because the
+ // remaining points are collinear. Really these
+ // should just be thrown out without halting triangulation.
+ if (earIndex == -1)
+ {
+ for (int i = 0; i < bufferSize; i++)
+ {
+ results.Add(new Triangle(buffer[i]));
+ }
+
+ return results;
+ }
+
+ // Clip off the ear:
+ // - remove the ear tip from the list
+
+ --vNum;
+ float[] newx = new float[vNum];
+ float[] newy = new float[vNum];
+ int currDest = 0;
+ for (int i = 0; i < vNum; ++i)
+ {
+ if (currDest == earIndex) ++currDest;
+ newx[i] = xrem[currDest];
+ newy[i] = yrem[currDest];
+ ++currDest;
+ }
+
+ // - add the clipped triangle to the triangle list
+ int under = (earIndex == 0) ? (vNum) : (earIndex - 1);
+ int over = (earIndex == vNum) ? 0 : (earIndex + 1);
+ Triangle toAdd = new Triangle(xrem[earIndex], yrem[earIndex], xrem[over], yrem[over], xrem[under],
+ yrem[under]);
+ buffer[bufferSize] = toAdd;
+ ++bufferSize;
+
+ // - replace the old list with the new one
+ xrem = newx;
+ yrem = newy;
+ }
+
+ Triangle tooAdd = new Triangle(xrem[1], yrem[1], xrem[2], yrem[2], xrem[0], yrem[0]);
+ buffer[bufferSize] = tooAdd;
+ ++bufferSize;
+
+ for (int i = 0; i < bufferSize; i++)
+ {
+ results.Add(new Triangle(buffer[i]));
+ }
+
+ return results;
+ }
+
+ ///
+ /// Finds and fixes "pinch points," points where two polygon
+ /// vertices are at the same point.
+ ///
+ /// If a pinch point is found, pin is broken up into poutA and poutB
+ /// and true is returned; otherwise, returns false.
+ ///
+ /// Mostly for internal use.
+ ///
+ /// O(N^2) time, which sucks...
+ ///
+ /// The pin.
+ /// The pout A.
+ /// The pout B.
+ ///
+ private static bool ResolvePinchPoint(Vertices pin, out Vertices poutA, out Vertices poutB)
+ {
+ poutA = new Vertices();
+ poutB = new Vertices();
+
+ if (pin.Count < 3)
+ return false;
+
+ bool hasPinchPoint = false;
+ int pinchIndexA = -1;
+ int pinchIndexB = -1;
+ for (int i = 0; i < pin.Count; ++i)
+ {
+ for (int j = i + 1; j < pin.Count; ++j)
+ {
+ //Don't worry about pinch points where the points
+ //are actually just dupe neighbors
+ if (Math.Abs(pin[i].X - pin[j].X) < Tol && Math.Abs(pin[i].Y - pin[j].Y) < Tol && j != i + 1)
+ {
+ pinchIndexA = i;
+ pinchIndexB = j;
+ hasPinchPoint = true;
+ break;
+ }
+ }
+ if (hasPinchPoint) break;
+ }
+ if (hasPinchPoint)
+ {
+ int sizeA = pinchIndexB - pinchIndexA;
+ if (sizeA == pin.Count) return false; //has dupe points at wraparound, not a problem here
+ for (int i = 0; i < sizeA; ++i)
+ {
+ int ind = Remainder(pinchIndexA + i, pin.Count); // is this right
+ poutA.Add(pin[ind]);
+ }
+
+ int sizeB = pin.Count - sizeA;
+ for (int i = 0; i < sizeB; ++i)
+ {
+ int ind = Remainder(pinchIndexB + i, pin.Count); // is this right
+ poutB.Add(pin[ind]);
+ }
+ }
+ return hasPinchPoint;
+ }
+
+ ///
+ /// Fix for obnoxious behavior for the % operator for negative numbers...
+ ///
+ /// The x.
+ /// The modulus.
+ ///
+ private static int Remainder(int x, int modulus)
+ {
+ int rem = x % modulus;
+ while (rem < 0)
+ {
+ rem += modulus;
+ }
+ return rem;
+ }
+
+ private static Vertices AddTriangle(Triangle t, Vertices vertices)
+ {
+ // First, find vertices that connect
+ int firstP = -1;
+ int firstT = -1;
+ int secondP = -1;
+ int secondT = -1;
+ for (int i = 0; i < vertices.Count; i++)
+ {
+ if (t.X[0] == vertices[i].X && t.Y[0] == vertices[i].Y)
+ {
+ if (firstP == -1)
+ {
+ firstP = i;
+ firstT = 0;
+ }
+ else
+ {
+ secondP = i;
+ secondT = 0;
+ }
+ }
+ else if (t.X[1] == vertices[i].X && t.Y[1] == vertices[i].Y)
+ {
+ if (firstP == -1)
+ {
+ firstP = i;
+ firstT = 1;
+ }
+ else
+ {
+ secondP = i;
+ secondT = 1;
+ }
+ }
+ else if (t.X[2] == vertices[i].X && t.Y[2] == vertices[i].Y)
+ {
+ if (firstP == -1)
+ {
+ firstP = i;
+ firstT = 2;
+ }
+ else
+ {
+ secondP = i;
+ secondT = 2;
+ }
+ }
+ }
+ // Fix ordering if first should be last vertex of poly
+ if (firstP == 0 && secondP == vertices.Count - 1)
+ {
+ firstP = vertices.Count - 1;
+ secondP = 0;
+ }
+
+ // Didn't find it
+ if (secondP == -1)
+ {
+ return null;
+ }
+
+ // Find tip index on triangle
+ int tipT = 0;
+ if (tipT == firstT || tipT == secondT)
+ tipT = 1;
+ if (tipT == firstT || tipT == secondT)
+ tipT = 2;
+
+ Vertices result = new Vertices(vertices.Count + 1);
+ for (int i = 0; i < vertices.Count; i++)
+ {
+ result.Add(vertices[i]);
+
+ if (i == firstP)
+ result.Add(new Vector2(t.X[tipT], t.Y[tipT]));
+ }
+
+ return result;
+ }
+
+ ///
+ /// Checks if vertex i is the tip of an ear in polygon defined by xv[] and
+ /// yv[].
+ ///
+ /// Assumes clockwise orientation of polygon...ick
+ ///
+ /// The i.
+ /// The xv.
+ /// The yv.
+ /// Length of the xv.
+ ///
+ /// true if the specified i is ear; otherwise, false.
+ ///
+ private static bool IsEar(int i, float[] xv, float[] yv, int xvLength)
+ {
+ float dx0, dy0, dx1, dy1;
+ if (i >= xvLength || i < 0 || xvLength < 3)
+ {
+ return false;
+ }
+ int upper = i + 1;
+ int lower = i - 1;
+ if (i == 0)
+ {
+ dx0 = xv[0] - xv[xvLength - 1];
+ dy0 = yv[0] - yv[xvLength - 1];
+ dx1 = xv[1] - xv[0];
+ dy1 = yv[1] - yv[0];
+ lower = xvLength - 1;
+ }
+ else if (i == xvLength - 1)
+ {
+ dx0 = xv[i] - xv[i - 1];
+ dy0 = yv[i] - yv[i - 1];
+ dx1 = xv[0] - xv[i];
+ dy1 = yv[0] - yv[i];
+ upper = 0;
+ }
+ else
+ {
+ dx0 = xv[i] - xv[i - 1];
+ dy0 = yv[i] - yv[i - 1];
+ dx1 = xv[i + 1] - xv[i];
+ dy1 = yv[i + 1] - yv[i];
+ }
+ float cross = dx0 * dy1 - dx1 * dy0;
+ if (cross > 0)
+ return false;
+ Triangle myTri = new Triangle(xv[i], yv[i], xv[upper], yv[upper],
+ xv[lower], yv[lower]);
+ for (int j = 0; j < xvLength; ++j)
+ {
+ if (j == i || j == lower || j == upper)
+ continue;
+ if (myTri.IsInside(xv[j], yv[j]))
+ return false;
+ }
+ return true;
+ }
+ }
+
+ public class Triangle
+ {
+ public float[] X;
+ public float[] Y;
+
+ //Constructor automatically fixes orientation to ccw
+ public Triangle(float x1, float y1, float x2, float y2, float x3, float y3)
+ {
+ X = new float[3];
+ Y = new float[3];
+ float dx1 = x2 - x1;
+ float dx2 = x3 - x1;
+ float dy1 = y2 - y1;
+ float dy2 = y3 - y1;
+ float cross = dx1 * dy2 - dx2 * dy1;
+ bool ccw = (cross > 0);
+ if (ccw)
+ {
+ X[0] = x1;
+ X[1] = x2;
+ X[2] = x3;
+ Y[0] = y1;
+ Y[1] = y2;
+ Y[2] = y3;
+ }
+ else
+ {
+ X[0] = x1;
+ X[1] = x3;
+ X[2] = x2;
+ Y[0] = y1;
+ Y[1] = y3;
+ Y[2] = y2;
+ }
+ }
+
+ public Triangle(Triangle t)
+ {
+ X = new float[3];
+ Y = new float[3];
+
+ X[0] = t.X[0];
+ X[1] = t.X[1];
+ X[2] = t.X[2];
+ Y[0] = t.Y[0];
+ Y[1] = t.Y[1];
+ Y[2] = t.Y[2];
+ }
+
+ public bool IsInside(float x, float y)
+ {
+ if (x < X[0] && x < X[1] && x < X[2]) return false;
+ if (x > X[0] && x > X[1] && x > X[2]) return false;
+ if (y < Y[0] && y < Y[1] && y < Y[2]) return false;
+ if (y > Y[0] && y > Y[1] && y > Y[2]) return false;
+
+ float vx2 = x - X[0];
+ float vy2 = y - Y[0];
+ float vx1 = X[1] - X[0];
+ float vy1 = Y[1] - Y[0];
+ float vx0 = X[2] - X[0];
+ float vy0 = Y[2] - Y[0];
+
+ float dot00 = vx0 * vx0 + vy0 * vy0;
+ float dot01 = vx0 * vx1 + vy0 * vy1;
+ float dot02 = vx0 * vx2 + vy0 * vy2;
+ float dot11 = vx1 * vx1 + vy1 * vy1;
+ float dot12 = vx1 * vx2 + vy1 * vy2;
+ float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
+ float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+ float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
+
+ return ((u > 0) && (v > 0) && (u + v < 1));
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/FlipcodeDecomposer.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/FlipcodeDecomposer.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,160 @@
+using System.Collections.Generic;
+using Microsoft.Xna.Framework;
+
+namespace FarseerPhysics.Common.Decomposition
+{
+ // Original code can be found here: http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
+
+ ///
+ /// Triangulates a polygon into triangles.
+ /// Doesn't handle holes.
+ ///
+ public static class FlipcodeDecomposer
+ {
+ private static Vector2 _tmpA;
+ private static Vector2 _tmpB;
+ private static Vector2 _tmpC;
+
+ ///
+ /// Check if the point P is inside the triangle defined by
+ /// the points A, B, C
+ ///
+ /// The A point.
+ /// The B point.
+ /// The C point.
+ /// The point to be tested.
+ /// True if the point is inside the triangle
+ private static bool InsideTriangle(ref Vector2 a, ref Vector2 b, ref Vector2 c, ref Vector2 p)
+ {
+ //A cross bp
+ float abp = (c.X - b.X) * (p.Y - b.Y) - (c.Y - b.Y) * (p.X - b.X);
+
+ //A cross ap
+ float aap = (b.X - a.X) * (p.Y - a.Y) - (b.Y - a.Y) * (p.X - a.X);
+
+ //b cross cp
+ float bcp = (a.X - c.X) * (p.Y - c.Y) - (a.Y - c.Y) * (p.X - c.X);
+
+ return ((abp >= 0.0f) && (bcp >= 0.0f) && (aap >= 0.0f));
+ }
+
+ ///
+ /// Cut a the contour and add a triangle into V to describe the
+ /// location of the cut
+ ///
+ /// The list of points defining the polygon
+ /// The index of the first point
+ /// The index of the second point
+ /// The index of the third point
+ /// The number of elements in the array.
+ /// The array to populate with indicies of triangles.
+ /// True if a triangle was found
+ private static bool Snip(Vertices contour, int u, int v, int w, int n,
+ int[] V)
+ {
+ if (Settings.Epsilon > MathUtils.Area(ref _tmpA, ref _tmpB, ref _tmpC))
+ {
+ return false;
+ }
+
+ for (int p = 0; p < n; p++)
+ {
+ if ((p == u) || (p == v) || (p == w))
+ {
+ continue;
+ }
+
+ Vector2 point = contour[V[p]];
+
+ if (InsideTriangle(ref _tmpA, ref _tmpB, ref _tmpC, ref point))
+ {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ ///
+ /// Decompose the polygon into triangles
+ ///
+ /// The list of points describing the polygon
+ ///
+ public static List ConvexPartition(Vertices contour)
+ {
+ int n = contour.Count;
+ if (n < 3)
+ return new List();
+
+ int[] V = new int[n];
+
+ // We want a counter-clockwise polygon in V
+ if (contour.IsCounterClockWise())
+ {
+ for (int v = 0; v < n; v++)
+ V[v] = v;
+ }
+ else
+ {
+ for (int v = 0; v < n; v++)
+ V[v] = (n - 1) - v;
+ }
+
+ int nv = n;
+
+ // Remove nv-2 Vertices, creating 1 triangle every time
+ int count = 2 * nv; /* error detection */
+
+ List result = new List();
+
+ for (int v = nv - 1; nv > 2; )
+ {
+ // If we loop, it is probably a non-simple polygon
+ if (0 >= (count--))
+ {
+ // Triangulate: ERROR - probable bad polygon!
+ return new List();
+ }
+
+ // Three consecutive vertices in current polygon,
+ int u = v;
+ if (nv <= u)
+ u = 0; // Previous
+ v = u + 1;
+ if (nv <= v)
+ v = 0; // New v
+ int w = v + 1;
+ if (nv <= w)
+ w = 0; // Next
+
+ _tmpA = contour[V[u]];
+ _tmpB = contour[V[v]];
+ _tmpC = contour[V[w]];
+
+ if (Snip(contour, u, v, w, nv, V))
+ {
+ int s, t;
+
+ // Output Triangle
+ Vertices triangle = new Vertices(3);
+ triangle.Add(_tmpA);
+ triangle.Add(_tmpB);
+ triangle.Add(_tmpC);
+ result.Add(triangle);
+
+ // Remove v from remaining polygon
+ for (s = v, t = v + 1; t < nv; s++, t++)
+ {
+ V[s] = V[t];
+ }
+ nv--;
+
+ // Reset error detection counter
+ count = 2 * nv;
+ }
+ }
+
+ return result;
+ }
+ }
+}
\ No newline at end of file
diff -r 0000000000000000000000000000000000000000 -r bffd63700ae09c651a9a8266b0e39b0834f738fd axios/Common/Decomposition/SeidelDecomposer.cs
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/axios/Common/Decomposition/SeidelDecomposer.cs Mon Mar 19 18:57:59 2012 -0500
@@ -0,0 +1,1057 @@
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using Microsoft.Xna.Framework;
+
+namespace FarseerPhysics.Common.Decomposition
+{
+ //From the Poly2Tri project by Mason Green: http://code.google.com/p/poly2tri/source/browse?repo=archive#hg/scala/src/org/poly2tri/seidel
+
+ ///
+ /// Convex decomposition algorithm based on Raimund Seidel's paper "A simple and fast incremental randomized
+ /// algorithm for computing trapezoidal decompositions and for triangulating polygons"
+ /// See also: "Computational Geometry", 3rd edition, by Mark de Berg et al, Chapter 6.2
+ /// "Computational Geometry in C", 2nd edition, by Joseph O'Rourke
+ ///
+ public static class SeidelDecomposer
+ {
+ ///
+ /// Decompose the polygon into several smaller non-concave polygon.
+ ///
+ /// The polygon to decompose.
+ /// The sheer to use. If you get bad results, try using a higher value. The default value is 0.001
+ /// A list of triangles
+ public static List ConvexPartition(Vertices vertices, float sheer)
+ {
+ List compatList = new List(vertices.Count);
+
+ foreach (Vector2 vertex in vertices)
+ {
+ compatList.Add(new Point(vertex.X, vertex.Y));
+ }
+
+ Triangulator t = new Triangulator(compatList, sheer);
+
+ List list = new List();
+
+ foreach (List triangle in t.Triangles)
+ {
+ Vertices verts = new Vertices(triangle.Count);
+
+ foreach (Point point in triangle)
+ {
+ verts.Add(new Vector2(point.X, point.Y));
+ }
+
+ list.Add(verts);
+ }
+
+ return list;
+ }
+
+ ///
+ /// Decompose the polygon into several smaller non-concave polygon.
+ ///
+ /// The polygon to decompose.
+ /// The sheer to use. If you get bad results, try using a higher value. The default value is 0.001
+ /// A list of trapezoids
+ public static List ConvexPartitionTrapezoid(Vertices vertices, float sheer)
+ {
+ List compatList = new List(vertices.Count);
+
+ foreach (Vector2 vertex in vertices)
+ {
+ compatList.Add(new Point(vertex.X, vertex.Y));
+ }
+
+ Triangulator t = new Triangulator(compatList, sheer);
+
+ List list = new List();
+
+ foreach (Trapezoid trapezoid in t.Trapezoids)
+ {
+ Vertices verts = new Vertices();
+
+ List points = trapezoid.Vertices();
+ foreach (Point point in points)
+ {
+ verts.Add(new Vector2(point.X, point.Y));
+ }
+
+ list.Add(verts);
+ }
+
+ return list;
+ }
+ }
+
+ internal class MonotoneMountain
+ {
+ private const float PiSlop = 3.1f;
+ public List> Triangles;
+ private HashSet _convexPoints;
+ private Point _head;
+
+ // Monotone mountain points
+ private List _monoPoly;
+
+ // Triangles that constitute the mountain
+
+ // Used to track which side of the line we are on
+ private bool _positive;
+ private int _size;
+ private Point _tail;
+
+ // Almost Pi!
+
+ public MonotoneMountain()
+ {
+ _size = 0;
+ _tail = null;
+ _head = null;
+ _positive = false;
+ _convexPoints = new HashSet();
+ _monoPoly = new List();
+ Triangles = new List>();
+ }
+
+ // Append a point to the list
+ public void Add(Point point)
+ {
+ if (_size == 0)
+ {
+ _head = point;
+ _size = 1;
+ }
+ else if (_size == 1)
+ {
+ // Keep repeat points out of the list
+ _tail = point;
+ _tail.Prev = _head;
+ _head.Next = _tail;
+ _size = 2;
+ }
+ else
+ {
+ // Keep repeat points out of the list
+ _tail.Next = point;
+ point.Prev = _tail;
+ _tail = point;
+ _size += 1;
+ }
+ }
+
+ // Remove a point from the list
+ public void Remove(Point point)
+ {
+ Point next = point.Next;
+ Point prev = point.Prev;
+ point.Prev.Next = next;
+ point.Next.Prev = prev;
+ _size -= 1;
+ }
+
+ // Partition a x-monotone mountain into triangles O(n)
+ // See "Computational Geometry in C", 2nd edition, by Joseph O'Rourke, page 52
+ public void Process()
+ {
+ // Establish the proper sign
+ _positive = AngleSign();
+ // create monotone polygon - for dubug purposes
+ GenMonoPoly();
+
+ // Initialize internal angles at each nonbase vertex
+ // Link strictly convex vertices into a list, ignore reflex vertices
+ Point p = _head.Next;
+ while (p.Neq(_tail))
+ {
+ float a = Angle(p);
+ // If the point is almost colinear with it's neighbor, remove it!
+ if (a >= PiSlop || a <= -PiSlop || a == 0.0)
+ Remove(p);
+ else if (IsConvex(p))
+ _convexPoints.Add(p);
+ p = p.Next;
+ }
+
+ Triangulate();
+ }
+
+ private void Triangulate()
+ {
+ while (_convexPoints.Count != 0)
+ {
+ IEnumerator e = _convexPoints.GetEnumerator();
+ e.MoveNext();
+ Point ear = e.Current;
+
+ _convexPoints.Remove(ear);
+ Point a = ear.Prev;
+ Point b = ear;
+ Point c = ear.Next;
+ List triangle = new List(3);
+ triangle.Add(a);
+ triangle.Add(b);
+ triangle.Add(c);
+
+ Triangles.Add(triangle);
+
+ // Remove ear, update angles and convex list
+ Remove(ear);
+ if (Valid(a))
+ _convexPoints.Add(a);
+ if (Valid(c))
+ _convexPoints.Add(c);
+ }
+
+ Debug.Assert(_size <= 3, "Triangulation bug, please report");
+ }
+
+ private bool Valid(Point p)
+ {
+ return p.Neq(_head) && p.Neq(_tail) && IsConvex(p);
+ }
+
+ // Create the monotone polygon
+ private void GenMonoPoly()
+ {
+ Point p = _head;
+ while (p != null)
+ {
+ _monoPoly.Add(p);
+ p = p.Next;
+ }
+ }
+
+ private float Angle(Point p)
+ {
+ Point a = (p.Next - p);
+ Point b = (p.Prev - p);
+ return (float)Math.Atan2(a.Cross(b), a.Dot(b));
+ }
+
+ private bool AngleSign()
+ {
+ Point a = (_head.Next - _head);
+ Point b = (_tail - _head);
+ return Math.Atan2(a.Cross(b), a.Dot(b)) >= 0;
+ }
+
+ // Determines if the inslide angle is convex or reflex
+ private bool IsConvex(Point p)
+ {
+ if (_positive != (Angle(p) >= 0))
+ return false;
+ return true;
+ }
+ }
+
+ // Node for a Directed Acyclic graph (DAG)
+ internal abstract class Node
+ {
+ protected Node LeftChild;
+ public List ParentList;
+ protected Node RightChild;
+
+ protected Node(Node left, Node right)
+ {
+ ParentList = new List();
+ LeftChild = left;
+ RightChild = right;
+
+ if (left != null)
+ left.ParentList.Add(this);
+ if (right != null)
+ right.ParentList.Add(this);
+ }
+
+ public abstract Sink Locate(Edge s);
+
+ // Replace a node in the graph with this node
+ // Make sure parent pointers are updated
+ public void Replace(Node node)
+ {
+ foreach (Node parent in node.ParentList)
+ {
+ // Select the correct node to replace (left or right child)
+ if (parent.LeftChild == node)
+ parent.LeftChild = this;
+ else
+ parent.RightChild = this;
+ }
+ ParentList.AddRange(node.ParentList);
+ }
+ }
+
+ // Directed Acyclic graph (DAG)
+ // See "Computational Geometry", 3rd edition, by Mark de Berg et al, Chapter 6.2
+ internal class QueryGraph
+ {
+ private Node _head;
+
+ public QueryGraph(Node head)
+ {
+ _head = head;
+ }
+
+ private Trapezoid Locate(Edge edge)
+ {
+ return _head.Locate(edge).Trapezoid;
+ }
+
+ public List FollowEdge(Edge edge)
+ {
+ List trapezoids = new List();
+ trapezoids.Add(Locate(edge));
+ int j = 0;
+
+ while (edge.Q.X > trapezoids[j].RightPoint.X)
+ {
+ if (edge.IsAbove(trapezoids[j].RightPoint))
+ {
+ trapezoids.Add(trapezoids[j].UpperRight);
+ }
+ else
+ {
+ trapezoids.Add(trapezoids[j].LowerRight);
+ }
+ j += 1;
+ }
+ return trapezoids;
+ }
+
+ private void Replace(Sink sink, Node node)
+ {
+ if (sink.ParentList.Count == 0)
+ _head = node;
+ else
+ node.Replace(sink);
+ }
+
+ public void Case1(Sink sink, Edge edge, Trapezoid[] tList)
+ {
+ YNode yNode = new YNode(edge, Sink.Isink(tList[1]), Sink.Isink(tList[2]));
+ XNode qNode = new XNode(edge.Q, yNode, Sink.Isink(tList[3]));
+ XNode pNode = new XNode(edge.P, Sink.Isink(tList[0]), qNode);
+ Replace(sink, pNode);
+ }
+
+ public void Case2(Sink sink, Edge edge, Trapezoid[] tList)
+ {
+ YNode yNode = new YNode(edge, Sink.Isink(tList[1]), Sink.Isink(tList[2]));
+ XNode pNode = new XNode(edge.P, Sink.Isink(tList[0]), yNode);
+ Replace(sink, pNode);
+ }
+
+ public void Case3(Sink sink, Edge edge, Trapezoid[] tList)
+ {
+ YNode yNode = new YNode(edge, Sink.Isink(tList[0]), Sink.Isink(tList[1]));
+ Replace(sink, yNode);
+ }
+
+ public void Case4(Sink sink, Edge edge, Trapezoid[] tList)
+ {
+ YNode yNode = new YNode(edge, Sink.Isink(tList[0]), Sink.Isink(tList[1]));
+ XNode qNode = new XNode(edge.Q, yNode, Sink.Isink(tList[2]));
+ Replace(sink, qNode);
+ }
+ }
+
+ internal class Sink : Node
+ {
+ public Trapezoid Trapezoid;
+
+ private Sink(Trapezoid trapezoid)
+ : base(null, null)
+ {
+ Trapezoid = trapezoid;
+ trapezoid.Sink = this;
+ }
+
+ public static Sink Isink(Trapezoid trapezoid)
+ {
+ if (trapezoid.Sink == null)
+ return new Sink(trapezoid);
+ return trapezoid.Sink;
+ }
+
+ public override Sink Locate(Edge edge)
+ {
+ return this;
+ }
+ }
+
+ // See "Computational Geometry", 3rd edition, by Mark de Berg et al, Chapter 6.2
+ internal class TrapezoidalMap
+ {
+ // Trapezoid container
+ public HashSet Map;
+
+ // AABB margin
+
+ // Bottom segment that spans multiple trapezoids
+ private Edge _bCross;
+
+ // Top segment that spans multiple trapezoids
+ private Edge _cross;
+ private float _margin;
+
+ public TrapezoidalMap()
+ {
+ Map = new HashSet();
+ _margin = 50.0f;
+ _bCross = null;
+ _cross = null;
+ }
+
+ public void Clear()
+ {
+ _bCross = null;
+ _cross = null;
+ }
+
+ // Case 1: segment completely enclosed by trapezoid
+ // break trapezoid into 4 smaller trapezoids
+ public Trapezoid[] Case1(Trapezoid t, Edge e)
+ {
+ Trapezoid[] trapezoids = new Trapezoid[4];
+ trapezoids[0] = new Trapezoid(t.LeftPoint, e.P, t.Top, t.Bottom);
+ trapezoids[1] = new Trapezoid(e.P, e.Q, t.Top, e);
+ trapezoids[2] = new Trapezoid(e.P, e.Q, e, t.Bottom);
+ trapezoids[3] = new Trapezoid(e.Q, t.RightPoint, t.Top, t.Bottom);
+
+ trapezoids[0].UpdateLeft(t.UpperLeft, t.LowerLeft);
+ trapezoids[1].UpdateLeftRight(trapezoids[0], null, trapezoids[3], null);
+ trapezoids[2].UpdateLeftRight(null, trapezoids[0], null, trapezoids[3]);
+ trapezoids[3].UpdateRight(t.UpperRight, t.LowerRight);
+
+ return trapezoids;
+ }
+
+ // Case 2: Trapezoid contains point p, q lies outside
+ // break trapezoid into 3 smaller trapezoids
+ public Trapezoid[] Case2(Trapezoid t, Edge e)
+ {
+ Point rp;
+ if (e.Q.X == t.RightPoint.X)
+ rp = e.Q;
+ else
+ rp = t.RightPoint;
+
+ Trapezoid[] trapezoids = new Trapezoid[3];
+ trapezoids[0] = new Trapezoid(t.LeftPoint, e.P, t.Top, t.Bottom);
+ trapezoids[1] = new Trapezoid(e.P, rp, t.Top, e);
+ trapezoids[2] = new Trapezoid(e.P, rp, e, t.Bottom);
+
+ trapezoids[0].UpdateLeft(t.UpperLeft, t.LowerLeft);
+ trapezoids[1].UpdateLeftRight(trapezoids[0], null, t.UpperRight, null);
+ trapezoids[2].UpdateLeftRight(null, trapezoids[0], null, t.LowerRight);
+
+ _bCross = t.Bottom;
+ _cross = t.Top;
+
+ e.Above = trapezoids[1];
+ e.Below = trapezoids[2];
+
+ return trapezoids;
+ }
+
+ // Case 3: Trapezoid is bisected
+ public Trapezoid[] Case3(Trapezoid t, Edge e)
+ {
+ Point lp;
+ if (e.P.X == t.LeftPoint.X)
+ lp = e.P;
+ else
+ lp = t.LeftPoint;
+
+ Point rp;
+ if (e.Q.X == t.RightPoint.X)
+ rp = e.Q;
+ else
+ rp = t.RightPoint;
+
+ Trapezoid[] trapezoids = new Trapezoid[2];
+
+ if (_cross == t.Top)
+ {
+ trapezoids[0] = t.UpperLeft;
+ trapezoids[0].UpdateRight(t.UpperRight, null);
+ trapezoids[0].RightPoint = rp;
+ }
+ else
+ {
+ trapezoids[0] = new Trapezoid(lp, rp, t.Top, e);
+ trapezoids[0].UpdateLeftRight(t.UpperLeft, e.Above, t.UpperRight, null);
+ }
+
+ if (_bCross == t.Bottom)
+ {
+ trapezoids[1] = t.LowerLeft;
+ trapezoids[1].UpdateRight(null, t.LowerRight);
+ trapezoids[1].RightPoint = rp;
+ }
+ else
+ {
+ trapezoids[1] = new Trapezoid(lp, rp, e, t.Bottom);
+ trapezoids[1].UpdateLeftRight(e.Below, t.LowerLeft, null, t.LowerRight);
+ }
+
+ _bCross = t.Bottom;
+ _cross = t.Top;
+
+ e.Above = trapezoids[0];
+ e.Below = trapezoids[1];
+
+ return trapezoids;
+ }
+
+ // Case 4: Trapezoid contains point q, p lies outside
+ // break trapezoid into 3 smaller trapezoids
+ public Trapezoid[] Case4(Trapezoid t, Edge e)
+ {
+ Point lp;
+ if (e.P.X == t.LeftPoint.X)
+ lp = e.P;
+ else
+ lp = t.LeftPoint;
+
+ Trapezoid[] trapezoids = new Trapezoid[3];
+
+ if (_cross == t.Top)
+ {
+ trapezoids[0] = t.UpperLeft;
+ trapezoids[0].RightPoint = e.Q;
+ }
+ else
+ {
+ trapezoids[0] = new Trapezoid(lp, e.Q, t.Top, e);
+ trapezoids[0].UpdateLeft(t.UpperLeft, e.Above);
+ }
+
+ if (_bCross == t.Bottom)
+ {
+ trapezoids[1] = t.LowerLeft;
+ trapezoids[1].RightPoint = e.Q;
+ }
+ else
+ {
+ trapezoids[1] = new Trapezoid(lp, e.Q, e, t.Bottom);
+ trapezoids[1].UpdateLeft(e.Below, t.LowerLeft);
+ }
+
+ trapezoids[2] = new Trapezoid(e.Q, t.RightPoint, t.Top, t.Bottom);
+ trapezoids[2].UpdateLeftRight(trapezoids[0], trapezoids[1], t.UpperRight, t.LowerRight);
+
+ return trapezoids;
+ }
+
+ // Create an AABB around segments
+ public Trapezoid BoundingBox(List edges)
+ {
+ Point max = edges[0].P + _margin;
+ Point min = edges[0].Q - _margin;
+
+ foreach (Edge e in edges)
+ {
+ if (e.P.X > max.X) max = new Point(e.P.X + _margin, max.Y);
+ if (e.P.Y > max.Y) max = new Point(max.X, e.P.Y + _margin);
+ if (e.Q.X > max.X) max = new Point(e.Q.X + _margin, max.Y);
+ if (e.Q.Y > max.Y) max = new Point(max.X, e.Q.Y + _margin);
+ if (e.P.X < min.X) min = new Point(e.P.X - _margin, min.Y);
+ if (e.P.Y < min.Y) min = new Point(min.X, e.P.Y - _margin);
+ if (e.Q.X < min.X) min = new Point(e.Q.X - _margin, min.Y);
+ if (e.Q.Y < min.Y) min = new Point(min.X, e.Q.Y - _margin);
+ }
+
+ Edge top = new Edge(new Point(min.X, max.Y), new Point(max.X, max.Y));
+ Edge bottom = new Edge(new Point(min.X, min.Y), new Point(max.X, min.Y));
+ Point left = bottom.P;
+ Point right = top.Q;
+
+ return new Trapezoid(left, right, top, bottom);
+ }
+ }
+
+ internal class Point
+ {
+ // Pointers to next and previous points in Monontone Mountain
+ public Point Next, Prev;
+ public float X, Y;
+
+ public Point(float x, float y)
+ {
+ X = x;
+ Y = y;
+ Next = null;
+ Prev = null;
+ }
+
+ public static Point operator -(Point p1, Point p2)
+ {
+ return new Point(p1.X - p2.X, p1.Y - p2.Y);
+ }
+
+ public static Point operator +(Point p1, Point p2)
+ {
+ return new Point(p1.X + p2.X, p1.Y + p2.Y);
+ }
+
+ public static Point operator -(Point p1, float f)
+ {
+ return new Point(p1.X - f, p1.Y - f);
+ }
+
+ public static Point operator +(Point p1, float f)
+ {
+ return new Point(p1.X + f, p1.Y + f);
+ }
+
+ public float Cross(Point p)
+ {
+ return X * p.Y - Y * p.X;
+ }
+
+ public float Dot(Point p)
+ {
+ return X * p.X + Y * p.Y;
+ }
+
+ public bool Neq(Point p)
+ {
+ return p.X != X || p.Y != Y;
+ }
+
+ public float Orient2D(Point pb, Point pc)
+ {
+ float acx = X - pc.X;
+ float bcx = pb.X - pc.X;
+ float acy = Y - pc.Y;
+ float bcy = pb.Y - pc.Y;
+ return acx * bcy - acy * bcx;
+ }
+ }
+
+ internal class Edge
+ {
+ // Pointers used for building trapezoidal map
+ public Trapezoid Above;
+ public float B;
+ public Trapezoid Below;
+
+ // Equation of a line: y = m*x + b
+ // Slope of the line (m)
+
+ // Montone mountain points
+ public HashSet MPoints;
+ public Point P;
+ public Point Q;
+ public float Slope;
+
+ // Y intercept
+
+ public Edge(Point p, Point q)
+ {
+ P = p;
+ Q = q;
+
+ if (q.X - p.X != 0)
+ Slope = (q.Y - p.Y) / (q.X - p.X);
+ else
+ Slope = 0;
+
+ B = p.Y - (p.X * Slope);
+ Above = null;
+ Below = null;
+ MPoints = new HashSet();
+ MPoints.Add(p);
+ MPoints.Add(q);
+ }
+
+ public bool IsAbove(Point point)
+ {
+ return P.Orient2D(Q, point) < 0;
+ }
+
+ public bool IsBelow(Point point)
+ {
+ return P.Orient2D(Q, point) > 0;
+ }
+
+ public void AddMpoint(Point point)
+ {
+ foreach (Point mp in MPoints)
+ if (!mp.Neq(point))
+ return;
+
+ MPoints.Add(point);
+ }
+ }
+
+ internal class Trapezoid
+ {
+ public Edge Bottom;
+ public bool Inside;
+ public Point LeftPoint;
+
+ // Neighbor pointers
+ public Trapezoid LowerLeft;
+ public Trapezoid LowerRight;
+
+ public Point RightPoint;
+ public Sink Sink;
+
+ public Edge Top;
+ public Trapezoid UpperLeft;
+ public Trapezoid UpperRight;
+
+ public Trapezoid(Point leftPoint, Point rightPoint, Edge top, Edge bottom)
+ {
+ LeftPoint = leftPoint;
+ RightPoint = rightPoint;
+ Top = top;
+ Bottom = bottom;
+ UpperLeft = null;
+ UpperRight = null;
+ LowerLeft = null;
+ LowerRight = null;
+ Inside = true;
+ Sink = null;
+ }
+
+ // Update neighbors to the left
+ public void UpdateLeft(Trapezoid ul, Trapezoid ll)
+ {
+ UpperLeft = ul;
+ if (ul != null) ul.UpperRight = this;
+ LowerLeft = ll;
+ if (ll != null) ll.LowerRight = this;
+ }
+
+ // Update neighbors to the right
+ public void UpdateRight(Trapezoid ur, Trapezoid lr)
+ {
+ UpperRight = ur;
+ if (ur != null) ur.UpperLeft = this;
+ LowerRight = lr;
+ if (lr != null) lr.LowerLeft = this;
+ }
+
+ // Update neighbors on both sides
+ public void UpdateLeftRight(Trapezoid ul, Trapezoid ll, Trapezoid ur, Trapezoid lr)
+ {
+ UpperLeft = ul;
+ if (ul != null) ul.UpperRight = this;
+ LowerLeft = ll;
+ if (ll != null) ll.LowerRight = this;
+ UpperRight = ur;
+ if (ur != null) ur.UpperLeft = this;
+ LowerRight = lr;
+ if (lr != null) lr.LowerLeft = this;
+ }
+
+ // Recursively trim outside neighbors
+ public void TrimNeighbors()
+ {
+ if (Inside)
+ {
+ Inside = false;
+ if (UpperLeft != null) UpperLeft.TrimNeighbors();
+ if (LowerLeft != null) LowerLeft.TrimNeighbors();
+ if (UpperRight != null) UpperRight.TrimNeighbors();
+ if (LowerRight != null) LowerRight.TrimNeighbors();
+ }
+ }
+
+ // Determines if this point lies inside the trapezoid
+ public bool Contains(Point point)
+ {
+ return (point.X > LeftPoint.X && point.X < RightPoint.X && Top.IsAbove(point) && Bottom.IsBelow(point));
+ }
+
+ public List Vertices()
+ {
+ List verts = new List(4);
+ verts.Add(LineIntersect(Top, LeftPoint.X));
+ verts.Add(LineIntersect(Bottom, LeftPoint.X));
+ verts.Add(LineIntersect(Bottom, RightPoint.X));
+ verts.Add(LineIntersect(Top, RightPoint.X));
+ return verts;
+ }
+
+ private Point LineIntersect(Edge edge, float x)
+ {
+ float y = edge.Slope * x + edge.B;
+ return new Point(x, y);
+ }
+
+ // Add points to monotone mountain
+ public void AddPoints()
+ {
+ if (LeftPoint != Bottom.P)
+ {
+ Bottom.AddMpoint(LeftPoint);
+ }
+ if (RightPoint != Bottom.Q)
+ {
+ Bottom.AddMpoint(RightPoint);
+ }
+ if (LeftPoint != Top.P)
+ {
+ Top.AddMpoint(LeftPoint);
+ }
+ if (RightPoint != Top.Q)
+ {
+ Top.AddMpoint(RightPoint);
+ }
+ }
+ }
+
+ internal class XNode : Node
+ {
+ private Point _point;
+
+ public XNode(Point point, Node lChild, Node rChild)
+ : base(lChild, rChild)
+ {
+ _point = point;
+ }
+
+ public override Sink Locate(Edge edge)
+ {
+ if (edge.P.X >= _point.X)
+ // Move to the right in the graph
+ return RightChild.Locate(edge);
+ // Move to the left in the graph
+ return LeftChild.Locate(edge);
+ }
+ }
+
+ internal class YNode : Node
+ {
+ private Edge _edge;
+
+ public YNode(Edge edge, Node lChild, Node rChild)
+ : base(lChild, rChild)
+ {
+ _edge = edge;
+ }
+
+ public override Sink Locate(Edge edge)
+ {
+ if (_edge.IsAbove(edge.P))
+ // Move down the graph
+ return RightChild.Locate(edge);
+
+ if (_edge.IsBelow(edge.P))
+ // Move up the graph
+ return LeftChild.Locate(edge);
+
+ // s and segment share the same endpoint, p
+ if (edge.Slope < _edge.Slope)
+ // Move down the graph
+ return RightChild.Locate(edge);
+
+ // Move up the graph
+ return LeftChild.Locate(edge);
+ }
+ }
+
+ internal class Triangulator
+ {
+ // Trapezoid decomposition list
+ public List Trapezoids;
+ public List> Triangles;
+
+ // Initialize trapezoidal map and query structure
+ private Trapezoid _boundingBox;
+ private List _edgeList;
+ private QueryGraph _queryGraph;
+ private float _sheer = 0.001f;
+ private TrapezoidalMap _trapezoidalMap;
+ private List _xMonoPoly;
+
+ public Triangulator(List polyLine, float sheer)
+ {
+ _sheer = sheer;
+ Triangles = new List>();
+ Trapezoids = new List();
+ _xMonoPoly = new List();
+ _edgeList = InitEdges(polyLine);
+ _trapezoidalMap = new TrapezoidalMap();
+ _boundingBox = _trapezoidalMap.BoundingBox(_edgeList);
+ _queryGraph = new QueryGraph(Sink.Isink(_boundingBox));
+
+ Process();
+ }
+
+ // Build the trapezoidal map and query graph
+ private void Process()
+ {
+ foreach (Edge edge in _edgeList)
+ {
+ List traps = _queryGraph.FollowEdge(edge);
+
+ // Remove trapezoids from trapezoidal Map
+ foreach (Trapezoid t in traps)
+ {
+ _trapezoidalMap.Map.Remove(t);
+
+ bool cp = t.Contains(edge.P);
+ bool cq = t.Contains(edge.Q);
+ Trapezoid[] tList;
+
+ if (cp && cq)
+ {
+ tList = _trapezoidalMap.Case1(t, edge);
+ _queryGraph.Case1(t.Sink, edge, tList);
+ }
+ else if (cp && !cq)
+ {
+ tList = _trapezoidalMap.Case2(t, edge);
+ _queryGraph.Case2(t.Sink, edge, tList);
+ }
+ else if (!cp && !cq)
+ {
+ tList = _trapezoidalMap.Case3(t, edge);
+ _queryGraph.Case3(t.Sink, edge, tList);
+ }
+ else
+ {
+ tList = _trapezoidalMap.Case4(t, edge);
+ _queryGraph.Case4(t.Sink, edge, tList);
+ }
+ // Add new trapezoids to map
+ foreach (Trapezoid y in tList)
+ {
+ _trapezoidalMap.Map.Add(y);
+ }
+ }
+ _trapezoidalMap.Clear();
+ }
+
+ // Mark outside trapezoids
+ foreach (Trapezoid t in _trapezoidalMap.Map)
+ {
+ MarkOutside(t);
+ }
+
+ // Collect interior trapezoids
+ foreach (Trapezoid t in _trapezoidalMap.Map)
+ {
+ if (t.Inside)
+ {
+ Trapezoids.Add(t);
+ t.AddPoints();
+ }
+ }
+
+ // Generate the triangles
+ CreateMountains();
+ }
+
+ // Build a list of x-monotone mountains
+ private void CreateMountains()
+ {
+ foreach (Edge edge in _edgeList)
+ {
+ if (edge.MPoints.Count > 2)
+ {
+ MonotoneMountain mountain = new MonotoneMountain();
+
+ // Sorting is a perfromance hit. Literature says this can be accomplised in
+ // linear time, although I don't see a way around using traditional methods
+ // when using a randomized incremental algorithm
+
+ // Insertion sort is one of the fastest algorithms for sorting arrays containing
+ // fewer than ten elements, or for lists that are already mostly sorted.
+
+ List