namespace MIConvexHull
{
using System.Collections.Generic;
///
/// Wraps each IVertex to allow marking of nodes.
///
sealed class VertexWrap
{
///
/// Ref. to the original vertex.
///
public IVertex Vertex;
///
/// Direct reference to PositionData makes IsVertexOverFace faster.
///
public double[] PositionData;
///
/// Vertex index.
///
public int Index;
///
/// Used mostly to enumerate unique vertices.
///
public bool Marked;
}
///
/// Compare vertices based on their indices.
///
class VertexWrapComparer : IComparer
{
public static readonly VertexWrapComparer Instance = new VertexWrapComparer();
public int Compare(VertexWrap x, VertexWrap y)
{
return x.Index.CompareTo(y.Index);
}
}
///
/// For deferred face addition.
///
sealed class DeferredFace
{
///
/// The faces.
///
public ConvexFaceInternal Face, Pivot, OldFace;
///
/// The indices.
///
public int FaceIndex, PivotIndex;
}
///
/// A helper class used to connect faces.
///
sealed class FaceConnector
{
///
/// The face.
///
public ConvexFaceInternal Face;
///
/// The edge to be connected.
///
public int EdgeIndex;
///
/// The vertex indices.
///
public int[] Vertices;
///
/// The hash code computed from indices.
///
public uint HashCode;
///
/// Prev node in the list.
///
public FaceConnector Previous;
///
/// Next node in the list.
///
public FaceConnector Next;
///
/// Ctor.
///
///
public FaceConnector(int dimension)
{
Vertices = new int[dimension - 1];
}
///
/// Updates the connector.
///
///
///
///
public void Update(ConvexFaceInternal face, int edgeIndex, int dim)
{
this.Face = face;
this.EdgeIndex = edgeIndex;
uint hashCode = 31;
var vs = face.Vertices;
for (int i = 0, c = 0; i < dim; i++)
{
if (i != edgeIndex)
{
var v = vs[i].Index;
this.Vertices[c++] = v;
hashCode += unchecked(23 * hashCode + (uint)v);
}
}
this.HashCode = hashCode;
}
///
/// Can two faces be connected.
///
///
///
///
///
public static bool AreConnectable(FaceConnector a, FaceConnector b, int dim)
{
if (a.HashCode != b.HashCode) return false;
var n = dim - 1;
var av = a.Vertices;
var bv = b.Vertices;
for (int i = 0; i < n; i++)
{
if (av[i] != bv[i]) return false;
}
return true;
}
///
/// Connect two faces.
///
///
///
public static void Connect(FaceConnector a, FaceConnector b)
{
a.Face.AdjacentFaces[a.EdgeIndex] = b.Face;
b.Face.AdjacentFaces[b.EdgeIndex] = a.Face;
}
}
///
/// This internal class manages the faces of the convex hull. It is a
/// separate class from the desired user class.
///
sealed class ConvexFaceInternal
{
///
/// Initializes a new instance of the class.
///
public ConvexFaceInternal(int dimension, VertexBuffer beyondList)
{
AdjacentFaces = new ConvexFaceInternal[dimension];
VerticesBeyond = beyondList;
Normal = new double[dimension];
Vertices = new VertexWrap[dimension];
}
///
/// Gets or sets the adjacent face data.
///
public ConvexFaceInternal[] AdjacentFaces;
///
/// Gets or sets the vertices beyond.
///
public VertexBuffer VerticesBeyond;
///
/// The furthest vertex.
///
public VertexWrap FurthestVertex;
///////
/////// Distance to the furthest vertex.
///////
////public double FurthestDistance;
///
/// Gets or sets the vertices.
///
public VertexWrap[] Vertices;
///
/// Gets or sets the normal vector.
///
public double[] Normal;
///
/// Is the normal flipped?
///
public bool IsNormalFlipped;
///
/// Face plane constant element.
///
public double Offset;
///
/// Used to traverse affected faces and create the Delaunay representation.
///
public int Tag;
///
/// Prev node in the list.
///
public ConvexFaceInternal Previous;
///
/// Next node in the list.
///
public ConvexFaceInternal Next;
///
/// Is it present in the list.
///
public bool InList;
}
}