1 %% Copyright (C) 2011-2012 David Legland <david.legland@grignon.inra.fr>
2 %% All rights reserved.
4 %% Redistribution and use in source and binary forms, with or without
5 %% modification, are permitted provided that the following conditions are met:
7 %% 1 Redistributions of source code must retain the above copyright notice,
8 %% this list of conditions and the following disclaimer.
9 %% 2 Redistributions in binary form must reproduce the above copyright
10 %% notice, this list of conditions and the following disclaimer in the
11 %% documentation and/or other materials provided with the distribution.
13 %% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
14 %% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 %% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
16 %% ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
17 %% ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
18 %% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
19 %% SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
20 %% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
21 %% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
22 %% OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 %% 2012 Adapted to Octave by Juan Pablo Carbajal <carbajal@ifi.uzh.ch>
27 %% @deftypefn {Function File} {[@var{points} @var{edges}]= } delaunayGraph (@var{points})
28 %% Graph associated to Delaunay triangulation of input points
30 %% Compute the Delaunay triangulation of the set of input points, and
31 %% convert to a set of edges. The output NODES is the same as the input
37 %% % Draw a planar graph correpspionding to Delaunay triangulation
38 %% points = rand(30, 2) * 100;
39 %% [nodes edges] = delaunayGraph(points);
41 %% drawGraph(nodes, edges);
43 %% % Draw a 3Dgraph corresponding to Delaunay tetrahedrisation
44 %% points = rand(20, 3) * 100;
45 %% [nodes edges] = delaunayGraph(points);
47 %% drawGraph(nodes, edges);
52 %% @seealso{delaunay, delaunayn}
55 function [points edges] = delaunayGraph(points, varargin)
56 % compute triangulation
57 tri = delaunayn(points, varargin{:});
59 % number of simplices (triangles), and of vertices by simplex (3 in 2D)
64 edges = zeros(nt * nv, 2);
66 % compute edges of each simplex
68 edges((1:nt) + (i-1)*nt, :) = sort([tri(:, i) tri(:, i+1)], 2);
70 edges((1:nt) + (nv-1)*nt, :) = sort([tri(:, end) tri(:, 1)], 2);
72 % remove multiple edges
73 edges = unique(edges, 'rows');
78 %! % Draw a planar graph correpspionding to Delaunay triangulation
79 %! points = rand(30, 2) * 100;
80 %! [nodes edges] = delaunayGraph(points);
82 %! drawGraph(nodes, edges);
86 %! % WARNING 3d pltottig works correctly in Octave >= 3.6
87 %! % Draw a 3Dgraph corresponding to Delaunay tetrahedrisation
88 %! points = rand(20, 3) * 100;
89 %! [nodes edges] = delaunayGraph(points);
91 %! drawGraph(nodes, edges);