Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/MIConvexHull/Triangulation/DelaunayTriangulation.cs @ 11301

Last change on this file since 11301 was 9730, checked in by ascheibe, 11 years ago

#1886 added a library that calculates convex hulls

File size: 4.4 KB
RevLine 
[9730]1namespace MIConvexHull
2{
3    using System.Collections.Generic;
4    using System.Linq;
5    using System;
6
7    /// <summary>
8    /// Calculation and representation of Delaunay triangulation.
9    /// </summary>
10    /// <typeparam name="TVertex"></typeparam>
11    /// <typeparam name="TCell"></typeparam>
12    public class DelaunayTriangulation<TVertex, TCell> : ITriangulation<TVertex, TCell>
13        where TCell : TriangulationCell<TVertex, TCell>, new()
14        where TVertex : IVertex
15    {
16        /// <summary>
17        /// Cells of the triangulation.
18        /// </summary>
19        public IEnumerable<TCell> Cells { get; private set; }
20
21        /// <summary>
22        /// Creates the Delaunay triangulation of the input data.
23        /// Be careful with concurrency, because during the computation, the vertex position arrays get resized.
24        /// </summary>
25        /// <param name="data"></param>
26        /// <returns></returns>
27        public static DelaunayTriangulation<TVertex, TCell> Create(IEnumerable<TVertex> data)
28        {
29            if (data == null) throw new ArgumentException("data can't be null.");
30            if (!(data is IList<TVertex>)) data = data.ToArray();
31            if (data.Count() == 0) return new DelaunayTriangulation<TVertex, TCell> { Cells = Enumerable.Empty<TCell>() };
32
33            int dimension = data.First().Position.Length;
34
35            // Resize the arrays and lift the data.
36            foreach (var p in data)
37            {
38                double lenSq = StarMath.norm2(p.Position, dimension, true);
39                var v = p.Position;
40                Array.Resize(ref v, dimension + 1);
41                p.Position = v;
42                p.Position[dimension] = lenSq;
43            }
44
45            // Find the convex hull
46            var delaunayFaces = ConvexHullInternal.GetConvexFacesInternal<TVertex, TCell>(data);
47
48            // Resize the data back
49            foreach (var p in data)
50            {
51                var v = p.Position;
52                Array.Resize(ref v, dimension);
53                p.Position = v;
54            }
55            // Remove the "upper" faces
56            for (var i = delaunayFaces.Count - 1; i >= 0; i--)
57            {
58                var candidate = delaunayFaces[i];
59                if (candidate.Normal[dimension] >= 0)
60                {
61                    for (int fi = 0; fi < candidate.AdjacentFaces.Length; fi++)
62                    {
63                        var f = candidate.AdjacentFaces[fi];
64                        if (f != null)
65                        {
66                            for (int j = 0; j < f.AdjacentFaces.Length; j++)
67                            {
68                                if (object.ReferenceEquals(f.AdjacentFaces[j], candidate))
69                                {
70                                    f.AdjacentFaces[j] = null;
71                                }
72                            }
73                        }
74                    }
75                    var li = delaunayFaces.Count - 1;
76                    delaunayFaces[i] = delaunayFaces[li];
77                    delaunayFaces.RemoveAt(li);
78                }
79            }
80
81            // Create the "TCell" representation.
82            int cellCount = delaunayFaces.Count;
83            var cells = new TCell[cellCount];
84
85            for (int i = 0; i < cellCount; i++)
86            {
87                var face = delaunayFaces[i];
88                var vertices = new TVertex[dimension + 1];
89                for (int j = 0; j <= dimension; j++) vertices[j] = (TVertex)face.Vertices[j].Vertex;
90                cells[i] = new TCell
91                {
92                    Vertices = vertices,
93                    Adjacency = new TCell[dimension + 1]
94                };
95                face.Tag = i;
96            }
97
98            for (int i = 0; i < cellCount; i++)
99            {
100                var face = delaunayFaces[i];
101                var cell = cells[i];
102                for (int j = 0; j <= dimension; j++)
103                {
104                    if (face.AdjacentFaces[j] == null) continue;
105                    cell.Adjacency[j] = cells[face.AdjacentFaces[j].Tag];
106                }
107            }
108
109            return new DelaunayTriangulation<TVertex, TCell> { Cells = cells };
110        }
111
112        /// <summary>
113        /// Can only be created using a factory method.
114        /// </summary>
115        private DelaunayTriangulation()
116        {
117
118        }
119    }
120}
Note: See TracBrowser for help on using the repository browser.