Menu
▾
▴
[Octave-cvsupdate] SF.net SVN: octave:[9564] trunk/octave-forge/main/geometry
|
From: <jpi...@us...> - 2012-01-25 10:33:30
|
Revision: 9564
http://octave.svn.sourceforge.net/octave/?rev=9564&view=rev
Author: jpicarbajal
Date: 2012-01-25 10:33:20 +0000 (Wed, 25 Jan 2012)
Log Message:
-----------
geometry: Adding basic graph tools
Modified Paths:
--------------
trunk/octave-forge/main/geometry/DESCRIPTION
trunk/octave-forge/main/geometry/INDEX
trunk/octave-forge/main/geometry/NEWS
trunk/octave-forge/main/geometry/PKG_ADD
trunk/octave-forge/main/geometry/PKG_DEL
Added Paths:
-----------
trunk/octave-forge/main/geometry/inst/graphs/
trunk/octave-forge/main/geometry/inst/graphs/delaunayGraph.m
trunk/octave-forge/main/geometry/inst/graphs/drawGraph.m
trunk/octave-forge/main/geometry/inst/graphs/knnGraph.m
trunk/octave-forge/main/geometry/inst/graphs/voronoi2d.m
Modified: trunk/octave-forge/main/geometry/DESCRIPTION
===================================================================
--- trunk/octave-forge/main/geometry/DESCRIPTION 2012-01-24 21:37:54 UTC (rev 9563)
+++ trunk/octave-forge/main/geometry/DESCRIPTION 2012-01-25 10:33:20 UTC (rev 9564)
@@ -1,6 +1,6 @@
Name: Geometry
Version: 1.3.0
-Date: 2011-11-24
+Date: 2012-01-25
Author: David Legland <dav...@gr...>, José Luis García Pallero <jgp...@gm...>, Juan Pablo Carbajal <car...@if...>
Maintainer: Juan Pablo Carbajal <car...@if...>
Title: Computational Geometry
Modified: trunk/octave-forge/main/geometry/INDEX
===================================================================
--- trunk/octave-forge/main/geometry/INDEX 2012-01-24 21:37:54 UTC (rev 9563)
+++ trunk/octave-forge/main/geometry/INDEX 2012-01-25 10:33:20 UTC (rev 9564)
@@ -136,6 +136,8 @@
isCounterClockwise
squareGrid
triangleGrid
+Geometric graphs
+
Input
svgload
svgnormalize
Modified: trunk/octave-forge/main/geometry/NEWS
===================================================================
--- trunk/octave-forge/main/geometry/NEWS 2012-01-24 21:37:54 UTC (rev 9563)
+++ trunk/octave-forge/main/geometry/NEWS 2012-01-25 10:33:20 UTC (rev 9564)
@@ -1,6 +1,13 @@
Summary of important user-visible changes for releases of the geometry package
===============================================================================
+geometry-1.4.0 Release Date: 2012-01-25 Release Manager: Juan Pablo Carbajal
+===============================================================================
+
+* Added basic geometric graphs creation and manipulation.
+
+
+===============================================================================
geometry-1.3.0 Release Date: 2011-11-24 Release Manager: Juan Pablo Carbajal
===============================================================================
Modified: trunk/octave-forge/main/geometry/PKG_ADD
===================================================================
--- trunk/octave-forge/main/geometry/PKG_ADD 2012-01-24 21:37:54 UTC (rev 9563)
+++ trunk/octave-forge/main/geometry/PKG_ADD 2012-01-25 10:33:20 UTC (rev 9564)
@@ -1,5 +1,5 @@
%1
-dirlist = {"geom2d","io","polygons2d","shape2d","octclip"};
+dirlist = {"geom2d","io","polygons2d","shape2d","octclip", "graphs"};
dirname = fileparts (canonicalize_file_name (mfilename ("fullpath")));
%% If we are in Architecture dependent folder add from outside
Modified: trunk/octave-forge/main/geometry/PKG_DEL
===================================================================
--- trunk/octave-forge/main/geometry/PKG_DEL 2012-01-24 21:37:54 UTC (rev 9563)
+++ trunk/octave-forge/main/geometry/PKG_DEL 2012-01-25 10:33:20 UTC (rev 9564)
@@ -1,5 +1,5 @@
%1
-dirlist = {"geom2d","io","polygons2d","shape2d","octclip"};
+dirlist = {"geom2d","io","polygons2d","shape2d","octclip","graphs"};
dirname = fileparts (canonicalize_file_name (mfilename ("fullpath")));
%% If we are not in Architecture dependent folder
Added: trunk/octave-forge/main/geometry/inst/graphs/delaunayGraph.m
===================================================================
--- trunk/octave-forge/main/geometry/inst/graphs/delaunayGraph.m (rev 0)
+++ trunk/octave-forge/main/geometry/inst/graphs/delaunayGraph.m 2012-01-25 10:33:20 UTC (rev 9564)
@@ -0,0 +1,91 @@
+%% Copyright (C) 2011-2012 David Legland <dav...@gr...>
+%% All rights reserved.
+%%
+%% Redistribution and use in source and binary forms, with or without
+%% modification, are permitted provided that the following conditions are met:
+%%
+%% 1 Redistributions of source code must retain the above copyright notice,
+%% this list of conditions and the following disclaimer.
+%% 2 Redistributions in binary form must reproduce the above copyright
+%% notice, this list of conditions and the following disclaimer in the
+%% documentation and/or other materials provided with the distribution.
+%%
+%% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
+%% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+%% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+%% ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
+%% ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+%% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+%% SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+%% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+%% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+%% OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+%%
+%% 2012 Adapted to Octave by Juan Pablo Carbajal <car...@if...>
+
+%% -*- texinfo -*-
+%% @deftypefn {Function File} {[@var{points} @var{edges}]= } delaunayGraph (@var{points})
+%% Graph associated to Delaunay triangulation of input points
+%%
+%% Compute the Delaunay triangulation of the set of input points, and
+%% convert to a set of edges. The output NODES is the same as the input
+%% POINTS.
+%%
+%% Example
+%% @example
+%%
+%% % Draw a planar graph correpspionding to Delaunay triangulation
+%% points = rand(30, 2) * 100;
+%% [nodes edges] = delaunayGraph(points);
+%% figure;
+%% drawGraph(nodes, edges);
+%%
+%% % Draw a 3Dgraph corresponding to Delaunay tetrahedrisation
+%% points = rand(20, 3) * 100;
+%% [nodes edges] = delaunayGraph(points);
+%% figure;
+%% drawGraph(nodes, edges);
+%% view(3);
+%%
+%% @end example
+%%
+%% @seealso{delaunay, delaunayn}
+%% @end deftypefn
+
+function [points edges] = delaunayGraph(points, varargin)
+ % compute triangulation
+ tri = delaunayn(points, varargin{:});
+
+ % number of simplices (triangles), and of vertices by simplex (3 in 2D)
+ nt = size(tri, 1);
+ nv = size(tri, 2);
+
+ % allocate memory
+ edges = zeros(nt * nv, 2);
+
+ % compute edges of each simplex
+ for i = 1:nv-1
+ edges((1:nt) + (i-1)*nt, :) = sort([tri(:, i) tri(:, i+1)], 2);
+ end
+ edges((1:nt) + (nv-1)*nt, :) = sort([tri(:, end) tri(:, 1)], 2);
+
+ % remove multiple edges
+ edges = unique(edges, 'rows');
+
+endfunction
+
+%!demo
+%! % Draw a planar graph correpspionding to Delaunay triangulation
+%! points = rand(30, 2) * 100;
+%! [nodes edges] = delaunayGraph(points);
+%! figure;
+%! drawGraph(nodes, edges);
+
+%!demo
+%! % WARNING 3d pltottig works correctly in Octave >= 3.6
+%! % Draw a 3Dgraph corresponding to Delaunay tetrahedrisation
+%! points = rand(20, 3) * 100;
+%! [nodes edges] = delaunayGraph(points);
+%! figure;
+%! drawGraph(nodes, edges);
+%! view(3);
Added: trunk/octave-forge/main/geometry/inst/graphs/drawGraph.m
===================================================================
--- trunk/octave-forge/main/geometry/inst/graphs/drawGraph.m (rev 0)
+++ trunk/octave-forge/main/geometry/inst/graphs/drawGraph.m 2012-01-25 10:33:20 UTC (rev 9564)
@@ -0,0 +1,290 @@
+%% Copyright (C) 2004-2012 David Legland <dav...@gr...>
+%% All rights reserved.
+%%
+%% Redistribution and use in source and binary forms, with or without
+%% modification, are permitted provided that the following conditions are met:
+%%
+%% 1 Redistributions of source code must retain the above copyright notice,
+%% this list of conditions and the following disclaimer.
+%% 2 Redistributions in binary form must reproduce the above copyright
+%% notice, this list of conditions and the following disclaimer in the
+%% documentation and/or other materials provided with the distribution.
+%%
+%% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
+%% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+%% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+%% ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
+%% ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+%% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+%% SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+%% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+%% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+%% OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+%%
+%% 2012 Adapted to Octave by Juan Pablo Carbajal <car...@if...>
+
+%% -*- texinfo -*-
+%% @deftypefn {Function File} drawGraph (@var{nodes}, @var{edges})
+%% @deftypefnx {Function File} drawGraph (@var{nodes}, @var{edges}, @var{faces})
+%% @deftypefnx {Function File} drawGraph (@var{graph})
+%% @deftypefnx {Function File} drawGraph (@dots{}, @var{snodes})
+%% @deftypefnx {Function File} drawGraph (@dots{}, @var{snodes}, @var{sedges})
+%% @deftypefnx {Function File} drawGraph (@dots{}, @var{snodes}, @var{sedges}, @var{sfaces})
+%% @deftypefnx {Function File} {@var{h} = } drawGraph (@dots{})
+%% @deftypefnx {Function File} {[@var{h} @var{he}] = } drawGraph (@dots{})
+%% @deftypefnx {Function File} {[@var{h} @var{he} @var{hf}] = } drawGraph (@dots{})
+%% Draw a graph, given as a set of vertices and edges
+%%
+%% DRAWGRAPH(NODES, EDGES)
+%% draw a graph specified by a set of nodes (array N*2 or N*3,
+%% corresponding to coordinate of each node), and a set of edges (an array
+%% Ne*2, containing for each edge the first and the second node).
+%% Default drawing is a red circle for nodes and a blue line for edges.
+%%
+%% DRAWGRAPH(NODES, EDGES, FACES)
+%% also draw faces of the graph as patches.
+%%
+%% DRAWGRAPH(GRAPH)
+%% passes argument in a srtucture with at least 2 fields named 'nodes' and
+%% 'edges', and possibly one field 'faces', corresponding to previously
+%% described parameters.
+%% GRAPH can also be a cell array, whose first element is node array,
+%% second element is edges array, and third element, if present, is faces
+%% array.
+%%
+%%
+%% DRAWGRAPH(..., SNODES)
+%% DRAWGRAPH(..., SNODES, SEDGES)
+%% DRAWGRAPH(..., SNODES, SEDGES, SFACES)
+%% specify the draw mode for each element, as in the classical 'plot'
+%% function. To not display some elements, uses 'none'.
+%%
+%%
+%% H = DRAWGRAPH(...)
+%% return handle to the set of edges.
+%%
+%% [HN, HE] = DRAWGRAPH(...)
+%% return handle to the set of nodes and to the set of edges.
+%%
+%% [HN, HE, HF] = DRAWGRAPH(...)
+%% Also return handle to the set of faces.
+%%
+%% @end deftypefn
+function varargout = drawGraph(varargin)
+
+ %% initialisations
+
+ % uses empty arrays by default for edges and faces
+ e = [];
+ f = [];
+
+ % default styles for nodes, edges, and faces
+
+ % nodes are drawn as red circles
+ sn = {'linestyle', 'none', 'color', 'r', 'marker', 'o'};
+
+ % edges are drawn as blue lines
+ se = {'linestyle', '-', 'color', 'b'};
+
+ % faces are cyan, their edges are not drawn
+ sf = {'EdgeColor', 'none', 'Facecolor', 'c'};
+
+
+ %% Process input arguments
+
+ % case of a call without arguments
+ if nargin==0
+ help drawGraph;
+ return;
+ end
+
+ % ---------------------------------------------------------------
+ % First extract the graph structure
+
+ var = varargin{1};
+ if iscell(var)
+ % graph is stored as a cell array: first cell is nodes, second one is
+ % edges, and third is faces
+ n = var{1};
+ if length(var)>1
+ e = var{2};
+ end
+ if length(var)>2
+ f = var{3};
+ end
+ varargin(1) = [];
+ elseif isstruct(var)
+ % graph is stored as a structure, with fields 'nodes', 'edges', and
+ % eventually 'faces'.
+ n = var.nodes;
+ e = var.edges;
+ if isfield(var, 'faces')
+ f = var.faces;
+ end
+ varargin(1) = [];
+ else
+ % graph is stored as set of variables: nodes, edges, and eventually
+ % faces
+ n = varargin{1};
+ e = varargin{2};
+ varargin(1:2) = [];
+
+ if ~isempty(varargin)
+ var = varargin{1};
+ if isnumeric(var)
+ % faces are stored in a numeric array of indices
+ f = var;
+ varargin(1) = [];
+ elseif iscell(var)
+ if ~ischar(var{1})
+ % faces are stored in a cell array, each cell containing a
+ % row vector of indices
+ f = var;
+ varargin(1) = [];
+ end
+ end
+ end
+ end
+
+ % extract drawing style
+
+ if ~isempty(varargin)
+ sn = concatArguments(sn, varargin{1});
+ end
+
+ if length(varargin)>1
+ se = concatArguments(se, varargin{2});
+ end
+
+ if length(varargin)>2
+ sf = concatArguments(sf, varargin{3});
+ end
+
+
+
+ %% main drawing processing
+
+ hold on;
+
+ if size(n, 2)==2
+ % Draw a 2 dimensional graph ----------------------
+
+ % Draw faces of the graph ------------
+ if ~strcmp(sf{1}, 'none') && ~isempty(f)
+ if iscell(f)
+ % each face is contained in a cell.
+ hf = zeros(size(f));
+ for fi=1:length(f)
+ hf(fi) = patch('Faces', f{fi}, 'Vertices', n, sf{:});
+ end
+ else
+ % process faces as an Nf*N array. Nf is the number of faces,
+ % and all faces have the same number of vertices (nodes).
+ hf = patch('Faces', f, 'Vertices', n, sf{:});
+ end
+ end
+
+ % Draw 2D Edges ----------------------
+ if ~strcmp(se{1}, 'none') && size(e, 1)>0
+ he = plot([n(e(:,1),1) n(e(:,2),1)]', [n(e(:,1),2) n(e(:,2),2)]', se{:});
+ end
+
+ % Draw 2D nodes ----------------------
+ if ~strcmp(sn{1}, 'none')
+ hn = plot(n(:,1), n(:,2), sn{:});
+ end
+
+
+ elseif size(n, 2)==3
+ % Draw a 3 dimensional graph ----------------------
+
+ % use a zbuffer to avoid display pbms.
+ set(gcf, 'renderer', 'zbuffer');
+
+ % Draw 3D Faces ----------------------
+ if ~strcmp(sf{1}, 'none')
+ if iscell(f)
+ % each face is contained in a cell.
+ hf = zeros(size(f));
+ for fi=1:length(f)
+ hf(fi) = patch('Faces', f{fi}, 'Vertices', n, sf{:});
+ end
+ else
+ % process faces as an Nf*N array. Nf i the number of faces,
+ % and all faces have the same number of vertices (nodes).
+ hf = patch('Faces', f, 'Vertices', n, sf{:});
+ end
+ end
+
+ % Draw 3D edges ----------------------
+ if ~strcmp(se{1}, 'none') && size(e, 1)>0
+ % he = plot3(...
+ % [n(e(:,1),1) n(e(:,2),1)]', ...
+ % [n(e(:,1),2) n(e(:,2),2)]', ...
+ % [n(e(:,1),3) n(e(:,2),3)]', ...
+ % se{:});
+ he = line(...
+ [n(e(:,1),1) n(e(:,2),1)]', ...
+ [n(e(:,1),2) n(e(:,2),2)]', ...
+ [n(e(:,1),3) n(e(:,2),3)]', ...
+ se{:});
+ end
+
+ % Draw 3D nodes ----------------------
+ if ~strcmp(sn{1}, 'none');
+ hn = plot3(n(:,1), n(:,2), n(:,3), sn{:});
+ end
+
+ end
+
+
+ %% Format output arguments
+
+ % return handle to edges
+ if nargout==1
+ varargout{1} = he;
+ end
+
+ % return handle to nodes and edges
+ if nargout==2
+ varargout{1} = hn;
+ varargout{2} = he;
+ end
+
+ % return handle to nodes, edges and faces
+ if nargout==3
+ varargout{1} = hn;
+ varargout{2} = he;
+ varargout{3} = hf;
+ end
+
+
+
+endfunction
+
+function res = concatArguments(in1, in2)
+ % in1 is a cell array already initialized
+ % in2 is an argument that can be:
+ % - empty
+ % - the string 'none'
+ % - another cell array
+
+ if isempty(in2)
+ res = in1;
+ return;
+ end
+
+ if ischar(in2)
+ if strcmp('none', in2)
+ res = {'none'};
+ return;
+ end
+ end
+
+ if iscell(in1)
+ res = [in1(:)' in2(:)'];
+ else
+ res = [{in1} in2(:)];
+ end
+
+endfunction
Added: trunk/octave-forge/main/geometry/inst/graphs/knnGraph.m
===================================================================
--- trunk/octave-forge/main/geometry/inst/graphs/knnGraph.m (rev 0)
+++ trunk/octave-forge/main/geometry/inst/graphs/knnGraph.m 2012-01-25 10:33:20 UTC (rev 9564)
@@ -0,0 +1,73 @@
+%% Copyright (C) 2008-2012 David Legland <dav...@gr...>
+%% All rights reserved.
+%%
+%% Redistribution and use in source and binary forms, with or without
+%% modification, are permitted provided that the following conditions are met:
+%%
+%% 1 Redistributions of source code must retain the above copyright notice,
+%% this list of conditions and the following disclaimer.
+%% 2 Redistributions in binary form must reproduce the above copyright
+%% notice, this list of conditions and the following disclaimer in the
+%% documentation and/or other materials provided with the distribution.
+%%
+%% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
+%% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+%% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+%% ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
+%% ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+%% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+%% SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+%% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+%% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+%% OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+%%
+%% 2012 Adapted to Octave by Juan Pablo Carbajal <car...@if...>
+
+%% -*- texinfo -*-
+%% @deftypefn {Function File} {@var{edges} = } knnGrpah (@var{nodes})
+%% Create the k-nearest neighbors graph of a set of points
+%%
+%% EDGES = knnGraph(NODES)
+%%
+%% Example
+%% @example
+%%
+%% nodes = rand(10, 2);
+%% edges = knnGraph(nodes);
+%% drawGraph(nodes, edges);
+%%
+%% @end example
+%%
+%% @end deftypefn
+
+function edges = knnGraph(nodes, varargin)
+
+ % get number of neighbors for each node
+ k = 2;
+ if ~isempty(varargin)
+ k = varargin{1};
+ end
+
+ % init size of arrays
+ n = size(nodes, 1);
+ edges = zeros(k*n, 2);
+
+ % iterate on nodes
+ for i = 1:n
+ dists = distancePoints(nodes(i,:), nodes);
+ [dists inds] = sort(dists); %#ok<ASGLU>
+ for j = 1:k
+ edges(k*(i-1)+j, :) = [i inds(j+1)];
+ end
+ end
+
+ % remove double edges
+ edges = unique(sort(edges, 2), 'rows');
+
+endfunction
+
+%!demo
+%! nodes = rand(10, 2);
+%! edges = knnGraph(nodes);
+%! drawGraph(nodes, edges);
+
Added: trunk/octave-forge/main/geometry/inst/graphs/voronoi2d.m
===================================================================
--- trunk/octave-forge/main/geometry/inst/graphs/voronoi2d.m (rev 0)
+++ trunk/octave-forge/main/geometry/inst/graphs/voronoi2d.m 2012-01-25 10:33:20 UTC (rev 9564)
@@ -0,0 +1,68 @@
+%% Copyright (C) 2007-2012 David Legland <dav...@gr...>
+%% All rights reserved.
+%%
+%% Redistribution and use in source and binary forms, with or without
+%% modification, are permitted provided that the following conditions are met:
+%%
+%% 1 Redistributions of source code must retain the above copyright notice,
+%% this list of conditions and the following disclaimer.
+%% 2 Redistributions in binary form must reproduce the above copyright
+%% notice, this list of conditions and the following disclaimer in the
+%% documentation and/or other materials provided with the distribution.
+%%
+%% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
+%% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+%% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+%% ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
+%% ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+%% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+%% SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+%% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+%% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+%% OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+%%
+%% 2012 Adapted to Octave by Juan Pablo Carbajal <car...@if...>
+
+%% -*- texinfo -*-
+%% @deftypefn {Function File} {[@var{nodes} @var{edges} @var{faces}] = } voronoi2d (@var{germs})
+%% Compute a voronoi diagram as a graph structure
+%%
+%% [NODES EDGES FACES] = voronoi2d(GERMS)
+%% GERMS an array of points with dimension 2
+%% NODES, EDGES, FACES: usual graph representation, FACES as cell array
+%%
+%% Example
+%% @example
+%%
+%% [n e f] = voronoi2d(rand(100, 2)*100);
+%% drawGraph(n, e);
+%%
+%% @end example
+%%
+%% @end deftypefn
+
+function [nodes edges faces] = voronoi2d(germs)
+ [V C] = voronoin(germs);
+
+ nodes = V(2:end, :);
+ edges = zeros(0, 2);
+ faces = {};
+
+ for i=1:length(C)
+ cell = C{i};
+ if ismember(1, cell)
+ continue;
+ end
+
+ cell = cell-1;
+ edges = [edges; sort([cell' cell([2:end 1])'], 2)]; %#ok<AGROW>
+ faces{length(faces)+1} = cell; %#ok<AGROW>
+ end
+
+ edges = unique(edges, 'rows');
+
+endfunction
+
+%!demo
+%! [n e f] = voronoi2d(rand(100, 2)*100);
+%! drawGraph(n, e);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
