37239732ac
- Globe Asset - Spatial Anchors - Photon Implementation - Scripts for Globe Control and Initial Country Colorizing - Script for Reading csv file
871 lines
32 KiB
C#
871 lines
32 KiB
C#
/* 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.
|
|
*/
|
|
|
|
/*
|
|
* The Following notice applies to the Methods CheckPolygon and
|
|
* MergeParallelEdges. Both are altered only enough to convert to C#
|
|
* and take advantage of some of C#'s language features. Any errors
|
|
* are thus mine from the conversion and not Eric's.
|
|
*
|
|
* 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;
|
|
using System.Collections.Generic;
|
|
using System.Text;
|
|
|
|
namespace WPM.Poly2Tri {
|
|
public class Point2DList : IEnumerable<Point2D>, IList<Point2D> {
|
|
// : List<Point2D>
|
|
public static readonly int kMaxPolygonVertices = 100000;
|
|
// adjust to suit...
|
|
|
|
/// A small length used as a collision and constraint tolerance. Usually it is
|
|
/// chosen to be numerically significant, but visually insignificant.
|
|
public static readonly double kLinearSlop = 0.005;
|
|
|
|
/// A small angle used as a collision and constraint tolerance. Usually it is
|
|
/// chosen to be numerically significant, but visually insignificant.
|
|
public static readonly double kAngularSlop = (2.0 / (180.0 * Math.PI));
|
|
|
|
public enum WindingOrderType {
|
|
CW,
|
|
CCW,
|
|
Unknown,
|
|
|
|
Default = CCW,
|
|
}
|
|
|
|
[Flags]
|
|
public enum PolygonError : uint {
|
|
None = 0,
|
|
NotEnoughVertices = 1 << 0,
|
|
NotConvex = 1 << 1,
|
|
NotSimple = 1 << 2,
|
|
AreaTooSmall = 1 << 3,
|
|
SidesTooCloseToParallel = 1 << 4,
|
|
TooThin = 1 << 5,
|
|
Degenerate = 1 << 6,
|
|
Unknown = 1 << 30,
|
|
}
|
|
|
|
|
|
protected List<Point2D> mPoints = new List<Point2D>();
|
|
protected Rect2D mBoundingBox = new Rect2D();
|
|
protected WindingOrderType mWindingOrder = WindingOrderType.Unknown;
|
|
protected double mEpsilon = MathUtil.EPSILON;
|
|
// Epsilon is a function of the size of the bounds of the polygon
|
|
|
|
public Rect2D BoundingBox { get { return mBoundingBox; } }
|
|
|
|
public WindingOrderType WindingOrder {
|
|
get { return mWindingOrder; }
|
|
set {
|
|
if (mWindingOrder == WindingOrderType.Unknown) {
|
|
mWindingOrder = CalculateWindingOrder();
|
|
}
|
|
if (value != mWindingOrder) {
|
|
mPoints.Reverse();
|
|
mWindingOrder = value;
|
|
}
|
|
}
|
|
}
|
|
|
|
public double Epsilon { get { return mEpsilon; } }
|
|
|
|
public Point2D this[int index] {
|
|
get { return mPoints[index]; }
|
|
set { mPoints[index] = value; }
|
|
}
|
|
|
|
public int Count { get { return mPoints.Count; } }
|
|
|
|
public virtual bool IsReadOnly { get { return false; } }
|
|
|
|
public Point2DList() {
|
|
}
|
|
|
|
public Point2DList(int capacity) {
|
|
mPoints.Capacity = capacity;
|
|
}
|
|
|
|
public Point2DList(IList<Point2D> l) {
|
|
AddRange(l.GetEnumerator(), WindingOrderType.Unknown);
|
|
}
|
|
|
|
public Point2DList(Point2DList l) {
|
|
int numPoints = l.Count;
|
|
for (int i = 0; i < numPoints; ++i) {
|
|
mPoints.Add(l[i]);
|
|
}
|
|
mBoundingBox.Set(l.BoundingBox);
|
|
mEpsilon = l.Epsilon;
|
|
mWindingOrder = l.WindingOrder;
|
|
}
|
|
|
|
public override string ToString() {
|
|
StringBuilder builder = new StringBuilder();
|
|
for (int i = 0; i < Count; i++) {
|
|
builder.Append(this[i].ToString());
|
|
if (i < Count - 1) {
|
|
builder.Append(" ");
|
|
}
|
|
}
|
|
return builder.ToString();
|
|
}
|
|
|
|
IEnumerator IEnumerable.GetEnumerator() {
|
|
return mPoints.GetEnumerator();
|
|
}
|
|
|
|
IEnumerator<Point2D> IEnumerable<Point2D>.GetEnumerator() {
|
|
return new Point2DEnumerator(mPoints);
|
|
}
|
|
|
|
public void Clear() {
|
|
mPoints.Clear();
|
|
mBoundingBox.Clear();
|
|
mEpsilon = MathUtil.EPSILON;
|
|
mWindingOrder = WindingOrderType.Unknown;
|
|
}
|
|
|
|
public int IndexOf(Point2D p) {
|
|
return mPoints.IndexOf(p);
|
|
}
|
|
|
|
public virtual void Add(Point2D p) {
|
|
Add(p, -1, true);
|
|
}
|
|
|
|
protected virtual void Add(Point2D p, int idx, bool bCalcWindingOrderAndEpsilon) {
|
|
if (idx < 0) {
|
|
mPoints.Add(p);
|
|
} else {
|
|
mPoints.Insert(idx, p);
|
|
}
|
|
mBoundingBox.AddPoint(p);
|
|
if (bCalcWindingOrderAndEpsilon) {
|
|
if (mWindingOrder == WindingOrderType.Unknown) {
|
|
mWindingOrder = CalculateWindingOrder();
|
|
}
|
|
mEpsilon = CalculateEpsilon();
|
|
}
|
|
}
|
|
|
|
public virtual void AddRange(Point2DList l) {
|
|
AddRange(l.mPoints.GetEnumerator(), l.WindingOrder);
|
|
}
|
|
|
|
public virtual void AddRange(IEnumerator<Point2D> iter, WindingOrderType windingOrder) {
|
|
if (iter == null) {
|
|
return;
|
|
}
|
|
|
|
if (mWindingOrder == WindingOrderType.Unknown && Count == 0) {
|
|
mWindingOrder = windingOrder;
|
|
}
|
|
bool bReverseReadOrder = (WindingOrder != WindingOrderType.Unknown) && (windingOrder != WindingOrderType.Unknown) && (WindingOrder != windingOrder);
|
|
bool bAddedFirst = true;
|
|
int startCount = mPoints.Count;
|
|
iter.Reset();
|
|
while (iter.MoveNext()) {
|
|
if (!bAddedFirst) {
|
|
bAddedFirst = true;
|
|
mPoints.Add(iter.Current);
|
|
} else if (bReverseReadOrder) {
|
|
mPoints.Insert(startCount, iter.Current);
|
|
} else {
|
|
mPoints.Add(iter.Current);
|
|
}
|
|
mBoundingBox.AddPoint(iter.Current);
|
|
}
|
|
if (mWindingOrder == WindingOrderType.Unknown && windingOrder == WindingOrderType.Unknown) {
|
|
mWindingOrder = CalculateWindingOrder();
|
|
}
|
|
mEpsilon = CalculateEpsilon();
|
|
}
|
|
|
|
public virtual void Insert(int idx, Point2D item) {
|
|
Add(item, idx, true);
|
|
}
|
|
|
|
public virtual bool Remove(Point2D p) {
|
|
if (mPoints.Remove(p)) {
|
|
CalculateBounds();
|
|
mEpsilon = CalculateEpsilon();
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
public virtual void RemoveAt(int idx) {
|
|
if (idx < 0 || idx >= Count) {
|
|
return;
|
|
}
|
|
mPoints.RemoveAt(idx);
|
|
CalculateBounds();
|
|
mEpsilon = CalculateEpsilon();
|
|
}
|
|
|
|
public virtual void RemoveRange(int idxStart, int count) {
|
|
if (idxStart < 0 || idxStart >= Count) {
|
|
return;
|
|
}
|
|
if (count == 0) {
|
|
return;
|
|
}
|
|
|
|
mPoints.RemoveRange(idxStart, count);
|
|
CalculateBounds();
|
|
mEpsilon = CalculateEpsilon();
|
|
}
|
|
|
|
public bool Contains(Point2D p) {
|
|
return mPoints.Contains(p);
|
|
}
|
|
|
|
public void CopyTo(Point2D[] array, int arrayIndex) {
|
|
int numElementsToCopy = Math.Min(Count, array.Length - arrayIndex);
|
|
for (int i = 0; i < numElementsToCopy; ++i) {
|
|
array[arrayIndex + i] = mPoints[i];
|
|
}
|
|
}
|
|
|
|
public void CalculateBounds() {
|
|
mBoundingBox.Clear();
|
|
foreach (Point2D pt in mPoints) {
|
|
mBoundingBox.AddPoint(pt);
|
|
}
|
|
}
|
|
|
|
public double CalculateEpsilon() {
|
|
// return Point2D.PRECISION; // Changed by Kronnect Games Math.Max (Math.Min (mBoundingBox.Width, mBoundingBox.Height) * 0.001f, MathUtil.EPSILON);
|
|
return Math.Max(Math.Min(mBoundingBox.Width, mBoundingBox.Height) * 0.000001, MathUtil.EPSILON);
|
|
// return Math.Max (Math.Min (mBoundingBox.Width, mBoundingBox.Height) * 0.001f, MathUtil.EPSILON);
|
|
}
|
|
|
|
public WindingOrderType CalculateWindingOrder() {
|
|
// the sign of the 'area' of the polygon is all we are interested in.
|
|
double area = GetSignedArea();
|
|
if (area < 0.0) {
|
|
return WindingOrderType.CW;
|
|
} else if (area > 0.0) {
|
|
return WindingOrderType.CCW;
|
|
}
|
|
|
|
// error condition - not even verts to calculate, non-simple poly, etc.
|
|
return WindingOrderType.Unknown;
|
|
}
|
|
|
|
public int NextIndex(int index) {
|
|
if (index == Count - 1) {
|
|
return 0;
|
|
}
|
|
return index + 1;
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Gets the previous index.
|
|
/// </summary>
|
|
/// <param name="index">The index.</param>
|
|
/// <returns></returns>
|
|
public int PreviousIndex(int index) {
|
|
if (index == 0) {
|
|
return Count - 1;
|
|
}
|
|
return index - 1;
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Gets the signed area.
|
|
/// </summary>
|
|
/// <returns></returns>
|
|
public double GetSignedArea() {
|
|
double area = 0.0;
|
|
for (int i = 0; i < Count; i++) {
|
|
int j = (i + 1) % Count;
|
|
area += this[i].X * this[j].Y;
|
|
area -= this[i].Y * this[j].X;
|
|
}
|
|
area /= 2.0f;
|
|
|
|
return area;
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Gets the area.
|
|
/// </summary>
|
|
/// <returns></returns>
|
|
public double GetArea() {
|
|
int i;
|
|
double area = 0;
|
|
|
|
for (i = 0; i < Count; i++) {
|
|
int j = (i + 1) % Count;
|
|
area += this[i].X * this[j].Y;
|
|
area -= this[i].Y * this[j].X;
|
|
}
|
|
area /= 2.0f;
|
|
return (area < 0 ? -area : area);
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Gets the centroid.
|
|
/// </summary>
|
|
/// <returns></returns>
|
|
public Point2D GetCentroid() {
|
|
// Same algorithm is used by Box2D
|
|
|
|
Point2D c = new Point2D();
|
|
double area = 0.0f;
|
|
|
|
const double inv3 = 1.0 / 3.0;
|
|
Point2D pRef = new Point2D();
|
|
for (int i = 0; i < Count; ++i) {
|
|
// Triangle vertices.
|
|
Point2D p1 = pRef;
|
|
Point2D p2 = this[i];
|
|
Point2D p3 = i + 1 < Count ? this[i + 1] : this[0];
|
|
|
|
Point2D e1 = p2 - p1;
|
|
Point2D e2 = p3 - p1;
|
|
|
|
double D = Point2D.Cross(e1, e2);
|
|
|
|
double triangleArea = 0.5f * D;
|
|
area += triangleArea;
|
|
|
|
// Area weighted centroid
|
|
c += triangleArea * inv3 * (p1 + p2 + p3);
|
|
}
|
|
|
|
// Centroid
|
|
c *= 1.0f / area;
|
|
return c;
|
|
}
|
|
|
|
|
|
// /// <summary>
|
|
/// Translates the vertices with the specified vector.
|
|
/// </summary>
|
|
/// <param name="vector">The vector.</param>
|
|
public void Translate(Point2D vector) {
|
|
for (int i = 0; i < Count; i++) {
|
|
this[i] += vector;
|
|
}
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Scales the vertices with the specified vector.
|
|
/// </summary>
|
|
/// <param name="value">The Value.</param>
|
|
public void Scale(Point2D value) {
|
|
for (int i = 0; i < Count; i++) {
|
|
this[i] *= value;
|
|
}
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Rotate the vertices with the defined value in radians.
|
|
/// </summary>
|
|
/// <param name="value">The amount to rotate by in radians.</param>
|
|
public void Rotate(double radians) {
|
|
// kickin' it old-skool since I don't want to create a Matrix class for now.
|
|
double cosr = Math.Cos(radians);
|
|
double sinr = Math.Sin(radians);
|
|
foreach (Point2D p in mPoints) {
|
|
double xold = p.X;
|
|
p.X = xold * cosr - p.Y * sinr;
|
|
p.Y = xold * sinr + p.Y * cosr;
|
|
}
|
|
}
|
|
|
|
// A degenerate polygon is one in which some vertex lies on an edge joining two other vertices.
|
|
// This can happen in one of two ways: either the vertices V(i-1), V(i), and V(i+1) can be collinear or
|
|
// the vertices V(i) and V(i+1) can overlap (fail to be distinct). In either of these cases, our polygon of
|
|
// n vertices will appear to have n - 1 or fewer -- it will have "degenerated" from an n-gon to an (n-1)-gon.
|
|
// (In the case of triangles, this will result in either a line segment or a point.)
|
|
public bool IsDegenerate() {
|
|
if (Count < 3) {
|
|
return false;
|
|
}
|
|
if (Count < 3) {
|
|
return false;
|
|
}
|
|
for (int k = 0; k < Count; ++k) {
|
|
int j = PreviousIndex(k);
|
|
if (mPoints[j].Equals(mPoints[k], Epsilon)) {
|
|
return true;
|
|
}
|
|
int i = PreviousIndex(j);
|
|
Orientation orientation = TriangulationUtil.Orient2d(mPoints[i], mPoints[j], mPoints[k]);
|
|
if (orientation == Orientation.Collinear) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Assuming the polygon is simple; determines whether the polygon is convex.
|
|
/// </summary>
|
|
/// <returns>
|
|
/// <c>true</c> if it is convex; otherwise, <c>false</c>.
|
|
/// </returns>
|
|
public bool IsConvex() {
|
|
bool isPositive = false;
|
|
|
|
for (int i = 0; i < Count; ++i) {
|
|
int lower = (i == 0) ? (Count - 1) : (i - 1);
|
|
int middle = i;
|
|
int upper = (i == Count - 1) ? (0) : (i + 1);
|
|
|
|
double dx0 = this[middle].X - this[lower].X;
|
|
double dy0 = this[middle].Y - this[lower].Y;
|
|
double dx1 = this[upper].X - this[middle].X;
|
|
double dy1 = this[upper].Y - this[middle].Y;
|
|
|
|
double cross = dx0 * dy1 - dx1 * dy0;
|
|
|
|
// Cross product should have same sign
|
|
// for each vertex if poly is convex.
|
|
bool newIsP = (cross >= 0) ? true : false;
|
|
if (i == 0) {
|
|
isPositive = newIsP;
|
|
} else if (isPositive != newIsP) {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Check for edge crossings
|
|
/// </summary>
|
|
/// <returns></returns>
|
|
public bool IsSimple() {
|
|
for (int i = 0; i < Count; ++i) {
|
|
int iplus = NextIndex(i);
|
|
for (int j = i + 1; j < Count; ++j) {
|
|
int jplus = NextIndex(j);
|
|
Point2D temp = null;
|
|
if (TriangulationUtil.LinesIntersect2D(mPoints[i], mPoints[iplus], mPoints[j], mPoints[jplus], ref temp, mEpsilon)) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Checks if polygon is valid for use in Box2d engine.
|
|
/// Last ditch effort to ensure no invalid polygons are
|
|
/// added to world geometry.
|
|
///
|
|
/// Performs a full check, for simplicity, convexity,
|
|
/// orientation, minimum angle, and volume. This won't
|
|
/// be very efficient, and a lot of it is redundant when
|
|
/// other tools in this section are used.
|
|
///
|
|
/// From Eric Jordan's convex decomposition library
|
|
/// </summary>
|
|
/// <param name="printErrors"></param>
|
|
/// <returns></returns>
|
|
public PolygonError CheckPolygon() {
|
|
PolygonError error = PolygonError.None;
|
|
if (Count < 3 || Count > Point2DList.kMaxPolygonVertices) {
|
|
error |= PolygonError.NotEnoughVertices;
|
|
// no other tests will be valid at this point, so just return
|
|
return error;
|
|
}
|
|
if (IsDegenerate()) {
|
|
error |= PolygonError.Degenerate;
|
|
}
|
|
//bool bIsConvex = IsConvex();
|
|
//if (!IsConvex())
|
|
//{
|
|
// error |= PolygonError.NotConvex;
|
|
//}
|
|
if (!IsSimple()) {
|
|
error |= PolygonError.NotSimple;
|
|
}
|
|
if (GetArea() < MathUtil.EPSILON) {
|
|
error |= PolygonError.AreaTooSmall;
|
|
}
|
|
|
|
// the following tests don't make sense if the polygon is not simple
|
|
if ((error & PolygonError.NotSimple) != PolygonError.NotSimple) {
|
|
bool bReversed = false;
|
|
WindingOrderType expectedWindingOrder = WindingOrderType.CCW;
|
|
WindingOrderType reverseWindingOrder = WindingOrderType.CW;
|
|
if (WindingOrder == reverseWindingOrder) {
|
|
WindingOrder = expectedWindingOrder;
|
|
bReversed = true;
|
|
}
|
|
|
|
//Compute normals
|
|
Point2D[] normals = new Point2D[Count];
|
|
Point2DList vertices = new Point2DList(Count);
|
|
for (int i = 0; i < Count; ++i) {
|
|
vertices.Add(new Point2D(this[i].X, this[i].Y));
|
|
int i1 = i;
|
|
int i2 = NextIndex(i);
|
|
Point2D edge = new Point2D(this[i2].X - this[i1].X, this[i2].Y - this[i1].Y);
|
|
normals[i] = Point2D.Perpendicular(edge, 1.0);
|
|
normals[i].Normalize();
|
|
}
|
|
|
|
//Required side checks
|
|
for (int i = 0; i < Count; ++i) {
|
|
int iminus = PreviousIndex(i);
|
|
|
|
//Parallel sides check
|
|
double cross = Point2D.Cross(normals[iminus], normals[i]);
|
|
cross = MathUtil.Clamp(cross, -1.0f, 1.0f);
|
|
float angle = (float)Math.Asin(cross);
|
|
if (Math.Abs(angle) <= Point2DList.kAngularSlop) {
|
|
error |= PolygonError.SidesTooCloseToParallel;
|
|
break;
|
|
}
|
|
|
|
// For some reason, the following checks do not seem to work
|
|
// correctly in all cases - they return false positives.
|
|
// //Too skinny check - only valid for convex polygons
|
|
// if (bIsConvex)
|
|
// {
|
|
// for (int j = 0; j < Count; ++j)
|
|
// {
|
|
// if (j == i || j == NextIndex(i))
|
|
// {
|
|
// continue;
|
|
// }
|
|
// Point2D testVector = vertices[j] - vertices[i];
|
|
// testVector.Normalize();
|
|
// double s = Point2D.Dot(testVector, normals[i]);
|
|
// if (s >= -Point2DList.kLinearSlop)
|
|
// {
|
|
// error |= PolygonError.TooThin;
|
|
// }
|
|
// }
|
|
|
|
// Point2D centroid = vertices.GetCentroid();
|
|
// Point2D n1 = normals[iminus];
|
|
// Point2D n2 = normals[i];
|
|
// Point2D v = vertices[i] - centroid;
|
|
|
|
// Point2D d = new Point2D();
|
|
// d.X = Point2D.Dot(n1, v); // - toiSlop;
|
|
// d.Y = Point2D.Dot(n2, v); // - toiSlop;
|
|
|
|
// // Shifting the edge inward by toiSlop should
|
|
// // not cause the plane to pass the centroid.
|
|
// if ((d.X < 0.0f) || (d.Y < 0.0f))
|
|
// {
|
|
// error |= PolygonError.TooThin;
|
|
// }
|
|
// }
|
|
}
|
|
|
|
if (bReversed) {
|
|
WindingOrder = reverseWindingOrder;
|
|
}
|
|
}
|
|
|
|
//if (error != PolygonError.None)
|
|
//{
|
|
// Console.WriteLine("Found invalid polygon: {0} {1}\n", Point2DList.GetErrorString(error), this.ToString());
|
|
//}
|
|
|
|
return error;
|
|
}
|
|
|
|
public static string GetErrorString(PolygonError error) {
|
|
StringBuilder sb = new StringBuilder(256);
|
|
if (error == PolygonError.None) {
|
|
sb.AppendFormat("No errors.\n");
|
|
} else {
|
|
if ((error & PolygonError.NotEnoughVertices) == PolygonError.NotEnoughVertices) {
|
|
sb.AppendFormat("NotEnoughVertices: must have between 3 and {0} vertices.\n", kMaxPolygonVertices);
|
|
}
|
|
if ((error & PolygonError.NotConvex) == PolygonError.NotConvex) {
|
|
sb.AppendFormat("NotConvex: Polygon is not convex.\n");
|
|
}
|
|
if ((error & PolygonError.NotSimple) == PolygonError.NotSimple) {
|
|
sb.AppendFormat("NotSimple: Polygon is not simple (i.e. it intersects itself).\n");
|
|
}
|
|
if ((error & PolygonError.AreaTooSmall) == PolygonError.AreaTooSmall) {
|
|
sb.AppendFormat("AreaTooSmall: Polygon's area is too small.\n");
|
|
}
|
|
if ((error & PolygonError.SidesTooCloseToParallel) == PolygonError.SidesTooCloseToParallel) {
|
|
sb.AppendFormat("SidesTooCloseToParallel: Polygon's sides are too close to parallel.\n");
|
|
}
|
|
if ((error & PolygonError.TooThin) == PolygonError.TooThin) {
|
|
sb.AppendFormat("TooThin: Polygon is too thin or core shape generation would move edge past centroid.\n");
|
|
}
|
|
if ((error & PolygonError.Degenerate) == PolygonError.Degenerate) {
|
|
sb.AppendFormat("Degenerate: Polygon is degenerate (contains collinear points or duplicate coincident points).\n");
|
|
}
|
|
if ((error & PolygonError.Unknown) == PolygonError.Unknown) {
|
|
sb.AppendFormat("Unknown: Unknown Polygon error!.\n");
|
|
}
|
|
}
|
|
|
|
return sb.ToString();
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Removes duplicate points that lie next to each other in the list
|
|
/// </summary>
|
|
public void RemoveDuplicateNeighborPoints() {
|
|
int numPoints = Count;
|
|
int i = numPoints - 1;
|
|
int j = 0;
|
|
while (numPoints > 1 && j < numPoints) {
|
|
if (mPoints[i].Equals(mPoints[j])) {
|
|
int idxToRemove = Math.Max(i, j);
|
|
mPoints.RemoveAt(idxToRemove);
|
|
--numPoints;
|
|
if (i >= numPoints) {
|
|
// can happen if first element in list is deleted...
|
|
i = numPoints - 1;
|
|
}
|
|
// don't increment i, j in this case because we want to check i against the new value at j
|
|
} else {
|
|
i = NextIndex(i);
|
|
++j; // intentionally not wrapping value of j so we have a valid end-point for the loop
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Removes all collinear points on the polygon.
|
|
/// Has a default bias of 0
|
|
/// </summary>
|
|
/// <param name="polygon">The polygon that needs simplification.</param>
|
|
/// <returns>A simplified polygon.</returns>
|
|
public void Simplify() {
|
|
Simplify(0.0);
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Removes all collinear points on the polygon. Note that this is NOT safe to run on a complex
|
|
/// polygon as it will remove points that it should not. For example, consider this polygon:
|
|
///
|
|
/// 2
|
|
/// +
|
|
/// / \
|
|
/// / \
|
|
/// / \
|
|
/// 0 +---+-------+
|
|
/// 3 1
|
|
///
|
|
/// This algorithm would delete point 3, leaving you with the polygon 0,1,2 - definitely NOT the correct
|
|
/// polygon. Caveat Emptor!
|
|
///
|
|
/// </summary>
|
|
/// <param name="polygon">The polygon that needs simplification.</param>
|
|
/// <param name="bias">The distance bias between points. Points closer than this will be 'joined'.</param>
|
|
/// <returns>A simplified polygon.</returns>
|
|
public void Simplify(double bias) {
|
|
//We can't simplify polygons under 3 vertices
|
|
if (Count < 3) {
|
|
return;
|
|
}
|
|
|
|
//#if DEBUG
|
|
// if (!IsSimple())
|
|
// {
|
|
// throw new Exception("Do not run Simplify on a non-simple polygon!");
|
|
// }
|
|
//#endif
|
|
|
|
int curr = 0;
|
|
int numVerts = Count;
|
|
double biasSquared = bias * bias;
|
|
while (curr < numVerts && numVerts >= 3) {
|
|
int prevId = PreviousIndex(curr);
|
|
int nextId = NextIndex(curr);
|
|
|
|
Point2D prev = this[prevId];
|
|
Point2D current = this[curr];
|
|
Point2D next = this[nextId];
|
|
|
|
//If they are closer than the bias, continue
|
|
if ((prev - current).MagnitudeSquared() <= biasSquared) {
|
|
RemoveAt(curr);
|
|
--numVerts;
|
|
continue;
|
|
}
|
|
|
|
//If they collinear, continue
|
|
Orientation orientation = TriangulationUtil.Orient2d(prev, current, next);
|
|
if (orientation == Orientation.Collinear) {
|
|
RemoveAt(curr);
|
|
--numVerts;
|
|
continue;
|
|
}
|
|
|
|
++curr;
|
|
}
|
|
}
|
|
|
|
|
|
// From Eric Jordan's convex decomposition library
|
|
/// <summary>
|
|
/// Merges all parallel edges in the list of vertices
|
|
/// </summary>
|
|
/// <param name="tolerance"></param>
|
|
public void MergeParallelEdges(double tolerance) {
|
|
if (Count <= 3) {
|
|
// Can't do anything useful here to a triangle
|
|
return;
|
|
}
|
|
|
|
bool[] mergeMe = new bool[Count];
|
|
int newNVertices = Count;
|
|
|
|
//Gather points to process
|
|
for (int i = 0; i < Count; ++i) {
|
|
int lower = (i == 0) ? (Count - 1) : (i - 1);
|
|
int middle = i;
|
|
int upper = (i == Count - 1) ? (0) : (i + 1);
|
|
|
|
double dx0 = this[middle].X - this[lower].X;
|
|
double dy0 = this[middle].Y - this[lower].Y;
|
|
double dx1 = this[upper].Y - this[middle].X;
|
|
double dy1 = this[upper].Y - this[middle].Y;
|
|
double norm0 = Math.Sqrt(dx0 * dx0 + dy0 * dy0);
|
|
double norm1 = Math.Sqrt(dx1 * dx1 + dy1 * dy1);
|
|
|
|
if (!(norm0 > 0.0 && norm1 > 0.0) && newNVertices > 3) {
|
|
//Merge identical points
|
|
mergeMe[i] = true;
|
|
--newNVertices;
|
|
}
|
|
|
|
dx0 /= norm0;
|
|
dy0 /= norm0;
|
|
dx1 /= norm1;
|
|
dy1 /= norm1;
|
|
double cross = dx0 * dy1 - dx1 * dy0;
|
|
double dot = dx0 * dx1 + dy0 * dy1;
|
|
|
|
if (Math.Abs(cross) < tolerance && dot > 0 && newNVertices > 3) {
|
|
mergeMe[i] = true;
|
|
--newNVertices;
|
|
} else {
|
|
mergeMe[i] = false;
|
|
}
|
|
}
|
|
|
|
if (newNVertices == Count || newNVertices == 0) {
|
|
return;
|
|
}
|
|
|
|
int currIndex = 0;
|
|
|
|
// Copy the vertices to a new list and clear the old
|
|
Point2DList oldVertices = new Point2DList(this);
|
|
Clear();
|
|
|
|
for (int i = 0; i < oldVertices.Count; ++i) {
|
|
if (mergeMe[i] || newNVertices == 0 || currIndex == newNVertices) {
|
|
continue;
|
|
}
|
|
|
|
if (currIndex >= newNVertices) {
|
|
throw new Exception("Point2DList::MergeParallelEdges - currIndex[ " + currIndex.ToString() + "] >= newNVertices[" + newNVertices + "]");
|
|
}
|
|
|
|
mPoints.Add(oldVertices[i]);
|
|
mBoundingBox.AddPoint(oldVertices[i]);
|
|
++currIndex;
|
|
}
|
|
mWindingOrder = CalculateWindingOrder();
|
|
mEpsilon = CalculateEpsilon();
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Projects to axis.
|
|
/// </summary>
|
|
/// <param name="axis">The axis.</param>
|
|
/// <param name="min">The min.</param>
|
|
/// <param name="max">The max.</param>
|
|
public void ProjectToAxis(Point2D axis, out double min, out double max) {
|
|
// To project a point on an axis use the dot product
|
|
double dotProduct = Point2D.Dot(axis, this[0]);
|
|
min = dotProduct;
|
|
max = dotProduct;
|
|
|
|
for (int i = 0; i < Count; i++) {
|
|
dotProduct = Point2D.Dot(this[i], axis);
|
|
if (dotProduct < min) {
|
|
min = dotProduct;
|
|
} else {
|
|
if (dotProduct > max) {
|
|
max = dotProduct;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|