octave_packages/geometry-1.5.0/graphs/delaunayGraph.m

   1 %% Copyright (C) 2011-2012 David Legland <david.legland@grignon.inra.fr>
   2 %% All rights reserved.
   3 %%
   4 %% Redistribution and use in source and binary forms, with or without
   5 %% modification, are permitted provided that the following conditions are met:
   6 %%
   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.
  12 %%
  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.
  23 %%
  24 %% 2012 Adapted to Octave by Juan Pablo Carbajal <carbajal@ifi.uzh.ch>
  25
  26 %% -*- texinfo -*-
  27 %% @deftypefn {Function File} {[@var{points} @var{edges}]= } delaunayGraph (@var{points})
  28 %% Graph associated to Delaunay triangulation of input points
  29 %%
  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
  32 %% POINTS.
  33 %%
  34 %% Example
  35 %% @example
  36 %%
  37 %% % Draw a planar graph correpspionding to Delaunay triangulation
  38 %% points = rand(30, 2) * 100;
  39 %% [nodes edges] = delaunayGraph(points);
  40 %% figure;
  41 %% drawGraph(nodes, edges);
  42 %%
  43 %% % Draw a 3Dgraph corresponding to Delaunay tetrahedrisation
  44 %% points = rand(20, 3) * 100;
  45 %% [nodes edges] = delaunayGraph(points);
  46 %% figure;
  47 %% drawGraph(nodes, edges);
  48 %% view(3);
  49 %%
  50 %% @end example
  51 %%
  52 %% @seealso{delaunay, delaunayn}
  53 %% @end deftypefn
  54
  55 function [points edges] = delaunayGraph(points, varargin)
  56   % compute triangulation
  57   tri = delaunayn(points, varargin{:});
  58
  59   % number of simplices (triangles), and of vertices by simplex (3 in 2D)
  60   nt = size(tri, 1);
  61   nv = size(tri, 2);
  62
  63   % allocate memory
  64   edges = zeros(nt * nv, 2);
  65
  66   % compute edges of each simplex
  67   for i = 1:nv-1
  68     edges((1:nt) + (i-1)*nt, :) = sort([tri(:, i) tri(:, i+1)], 2);
  69   end
  70   edges((1:nt) + (nv-1)*nt, :) = sort([tri(:, end) tri(:, 1)], 2);
  71
  72   % remove multiple edges
  73   edges = unique(edges, 'rows');
  74
  75 endfunction
  76
  77 %!demo
  78 %! % Draw a planar graph correpspionding to Delaunay triangulation
  79 %! points = rand(30, 2) * 100;
  80 %! [nodes edges] = delaunayGraph(points);
  81 %! figure;
  82 %! drawGraph(nodes, edges);
  83 %! axis tight
  84
  85 %!demo
  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);
  90 %! figure;
  91 %! drawGraph(nodes, edges);
  92 %! view(3);
  93 %! axis tight