Sample Code

This is a (somewhat modified) piece of code I created at Jagaco. It is used for connecting rooms in a dungeon generator. It triangulates given points so that the triangles are Delaunay. When adding a point the following algorithm is followed:

It starts with finding out on which triangle the point lies.
3 new triangles are created inside the found triangle. The ‘old’ triangle is removed.
Find the opposite triangles, and calculate the angles highlighted in red.
If the angle is greater than Pi, perform an edge flip.
And repeat for the other points!

 

 

The code


using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace CodeSample
{
internal class Triangulator
{
/// <summary>
/// The triangles. Every 3 values in the collection make a triangle of verts, pointing towards the Verts List.
/// </summary>
public List<int> Tris { get; private set; }

/// <summary>
/// The list of vertices.
/// </summary>
public List<Point> Verts { get; private set; }

/// <summary>
/// Default Constructor
/// </summary>
public Triangulator(int minimalPosition, int maximumPosition)
{
// Create new triangle & vertices lists.
Tris = new List<int>();
Verts = new List<Point>();

// Add the bounds to triangulate in.

// The triangles.
Tris.AddRange(new int[] { 0, 1, 2, 1, 2, 3 });

// The vertecies.
Verts.AddRange(new Point[]
{
new Point(minimalPosition, minimalPosition),
new Point(minimalPosition, maximumPosition),
new Point(maximumPosition, minimalPosition),
new Point(maximumPosition, maximumPosition)
});
}

/// <summary>
/// Triangulate a collection of points.
/// </summary>
/// <param name=”points”>The colletion of points to triangulate.</param>
public void Triangulate(IEnumerable<Point> points)
{
// Add all points.
foreach (Point p in points)
{
// Add vert, and triangulate.
AddVert(p);
}
}

/// <summary>
/// Throw in a new vert.
/// </summary>
/// <param name=”point”>The vert (Point) to add.</param>
private void AddVert(Point point)
{
// For every triangle we have, check if the given point is on it.
for (int i = 0; i < Tris.Count; i += 3)
{
// When point is on the triangle.
if (PointOnTriangle(point, Verts[Tris[i]], Verts[Tris[i + 1]], Verts[Tris[i + 2]]))
{
// Add the new vert to the vert collection.
Verts.Add(point);

// Create the 3 new triangles.
// First triangle.
Tris.Add(Tris[i]);
Tris.Add(Tris[i + 1]);
Tris.Add(Verts.Count 1);

// Second triangle.
Tris.Add(Tris[i + 1]);
Tris.Add(Tris[i + 2]);
Tris.Add(Verts.Count 1);

// Thrid triangle.
Tris.Add(Tris[i]);
Tris.Add(Tris[i + 2]);
Tris.Add(Verts.Count 1);

// Remove old triangle.
Tris.RemoveRange(i, 3);

// Index of the new vert.
int index = Tris.Count 1;

// Check if the new triangles need to be flipped.
Flip(index 6, index 7, index 8);
Flip(index 3, index 4, index 5);
Flip(index, index 1, index 2);

return;
}
}
}

/// <summary>
/// If the new triangle, and the opposite triangle have a angle bigger than 180 degrees, flip the triangles.
/// </summary>
/// <param name=”newVert”>The vert that is not shared</param>
/// <param name=”sharedVert0″>One of the shared triangle verts</param>
/// <param name=”sharedVert1″>One of the shared triangle verts</param>
private void Flip(int newVert, int sharedVert0, int sharedVert1)
{
// The index of the opposite triangle.
int oppTriangle = 1;
int[] triangle = null;

// Go through all triangles, and find the opposite.
for (int i = 0; i < Tris.Count; i += 3)
{
// Array is faster accessable than a list.
triangle = Tris.GetRange(i, 3).ToArray();

if (!triangle.Contains(Tris[newVert]) && triangle.Contains(Tris[sharedVert0]) && triangle.Contains(Tris[sharedVert1]))
{
oppTriangle = i;

// Found the opposite triangle, no need to look further.
break;
}
}

// No second triangle found, no need to flip.
if (oppTriangle == 1)
return;

// The index of the opposite vert.
int oppisiteVert = Array.IndexOf(triangle, triangle.Where(x => x != Tris[sharedVert0] && x != Tris[sharedVert1]).First());
int shared0 = Enumerable.Range(0, 3).Where(x => x != oppisiteVert && Tris[sharedVert0] == Tris[x + oppTriangle]).First();
int shared1 = Enumerable.Range(0, 3).Where(x => x != oppisiteVert && x != shared0).First();

// If there is a second triangle found, calculate the angles using the law of cosinus.
float newTriAngle = CalcAngle(Verts[Tris[newVert]], Verts[Tris[sharedVert0]], Verts[Tris[sharedVert1]]);
float oldTriAngle = CalcAngle(Verts[Tris[oppisiteVert + oppTriangle]], Verts[Tris[sharedVert0]], Verts[Tris[sharedVert1]]);

// If the angle is > Pi, perform an edge flip.
if (newTriAngle + oldTriAngle > Math.PI)
{
// Perform the edge flip.
Tris[shared0 + oppTriangle] = Tris[newVert];
Tris[sharedVert1] = Tris[oppisiteVert + oppTriangle];

// Flip newly created triangles. (if necessary).
Flip(newVert, sharedVert0, sharedVert1);
Flip(shared0 + oppTriangle, oppisiteVert + oppTriangle, shared1 + oppTriangle);
}
}

/// <summary>
/// Calculates the angle at point A using the law of cosinus.
/// </summary>
/// <param name=”A”>Point A</param>
/// <param name=”B”>Point B</param>
/// <param name=”C”>Point C</param>
/// <returns>The angle (rad)</returns>
private float CalcAngle(Point A, Point B, Point C)
{
// side a is opposite of A (BC), b of B, c of C

// The law of cosinus states:
// a^2 = b^2 + c^2 – 2bc * cos(A)
// So,
// A = cos^-1 ( (a^2 – b^2 – c^2) / (-2 * b * c))

float a = Distance(B, C);
float b = Distance(A, C);
float c = Distance(A, B);

float d = ((b * b) + (c * c) (a * a)) / (2 * b * c);

return (float)Math.Acos(d);
}

/// <summary>
/// Calculate the distance between two points.
/// </summary>
/// <param name=”p1″>Point 1</param>
/// <param name=”p2″>Point 2</param>
/// <returns>The distance between the 2 points</returns>
private float Distance(Point p1, Point p2)
{
int dx = p1.X p2.X;
int dy = p1.Y p2.Y;

// a = sqrt(b^2 + c^2)

return (float)Math.Sqrt((dx * dx) + (dy * dy));
}

/// <summary>
/// Is a given point on the given triangle?
/// </summary>
/// <param name=”point”>The point to check</param>
/// <param name=”v1″>triangle point 1</param>
/// <param name=”v2″>triangle point 2</param>
/// <param name=”v3″>triangle point 3</param>
/// <returns>true if on triangle, false if off</returns>
private bool PointOnTriangle(Point point, Point v1, Point v2, Point v3)
{
float s1 = Sign(point, v1, v2);
float s2 = Sign(point, v2, v3);
float si = Sign(point, v3, v1);

// The point is on the same side of all edges, it is inside the triangle.
if ((s1 >= 0.0f && s2 >= 0.0f && s3 >= 0.0f) ||
(s1 <= 0.0f && s2 <= 0.0f && s3 <= 0.0f))
return true;

// Point not inside the triangle.
return false;
}

/// <summary>
/// On what side is the point from the given edge?
/// </summary>
/// <param name=”p1″>The point to test</param>
/// <param name=”p2″>first vert for the edge</param>
/// <param name=”p3″>second vert for the edge</param>
/// <returns>0 if on line, positive if on the left, negative if on the right.</returns>
private float Sign(Point p1, Point p2, Point p3)
{
// Use the cross product.
return (p1.X p3.X) * (p2.Y p3.Y) (p2.X p3.X) * (p1.Y p3.Y);
}
}
}