1## Copyright (C) 2021 David Legland 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## The views and conclusions contained in the software and documentation are 25## those of the authors and should not be interpreted as representing official 26## policies, either expressed or implied, of the copyright holders. 27 28function varargout = clipGraph(nodes, edges, varargin) 29%CLIPGRAPH Clip a graph with a rectangular area. 30% 31% [N2, E2] = clipGraph(N, E, BOX); 32% [N2, E2, F2] = clipGraph(N, E, F, BOX); 33% N is an array ov vertices, E an array of edges, containing indices of 34% first ans second vertices, and F (optional) is either a matrice or a 35% cell array containing indices of vertices for each face. 36% BOX is either a box given as a matrix: [XMIN XMAX;YMIN YMAX], or a row 37% vector following matlab axis format: [XMIN XMAX YMIN YMAX]. 38% 39% Example 40% % create a simple graph structure 41% n = [0 60; 40 100; 40 60; 60 40; 100 40; 60 0]; 42% e = [1 3; 2 3; 3 4; 4 5; 4 6; 5 6]; 43% figure(1); clf; hold on; 44% drawGraph(n, e); 45% axis equal; axis([-10 110 -10 110]); 46% % clip with a box 47% box = [10 90 10 90]; 48% drawBox(box, 'k'); 49% [n2, e2] = clipGraph(n, e, box); 50% drawGraphEdges(n2, e2, 'color', 'b', 'linewidth', 2); 51% 52% See also 53% graphs, drawGraph, clipGraphPolygon 54% 55 56% ------ 57% Author: David Legland 58% e-mail: david.legland@inra.fr 59% Created: 2007-01-18 60% Copyright 2007 INRA - BIA PV Nantes - MIAJ Jouy-en-Josas. 61 62 63%% Format inputs 64 65% extract input arguments 66faces = []; 67if length(varargin)==1 68 box = varargin{1}; 69elseif length(varargin)==2 70 faces = varargin{1}; 71 box = varargin{2}; 72else 73 error('Wrong number of arguments in clipGraph'); 74end 75 76% uniformization of input for box. 77box = box'; 78box = box(:); 79 80% accuracy of numeric computations 81ACC = 1e-14; 82 83 84%% Get bounding lines 85 86% get bounds of the box 87xmin = box(1); 88xmax = box(2); 89ymin = box(3); 90ymax = box(4); 91 92% create box corners 93corners = [ ... 94 xmin ymin; ... 95 xmin ymax; ... 96 xmax ymin; ... 97 xmax ymax]; ... 98 99%% Clip the nodes 100 101% find nodes inside clipping window 102insideNodes = ... 103 nodes(:,1)-xmin>ACC & nodes(:,1)-xmax<ACC & ... 104 nodes(:,2)-ymin>ACC & nodes(:,2)-ymax<ACC; 105 106% convert to indices 107indNodes = find(insideNodes); 108 109% create correspondance between original nodes and inside nodes 110hashNodes = zeros(size(nodes, 1), 1); 111for i = 1:length(indNodes) 112 hashNodes(indNodes(i)) = i; 113end 114 115% select clipped nodes 116nodes2 = nodes(indNodes, :); 117 118 119%% Clip edges 120 121% initialize empty array 122edges2 = zeros([0 2]); 123 124% create correspondance map between old edges and clipped edges. 125hashEdges = zeros(size(edges, 1), 1); 126 127 128% iterate over each edge 129for e = 1:size(edges, 1) 130 % current edge 131 edge = [nodes(edges(e, 1), :) nodes(edges(e, 2), :)]; 132 133 % flags to indicate whether nodes are inside box or not 134 in1 = ismember(edges(e, 1), indNodes); 135 in2 = ismember(edges(e, 2), indNodes); 136 137 % check if edge is totally inside window -> no clip 138 if in1 && in2 139 edges2 = [edges2; hashNodes(edges(e, :))']; %#ok<AGROW> 140 hashEdges(e) = size(edges2, 1); 141 continue; 142 end 143 144 % check that edge is not totally clipped -> no edge 145 if edge(1)-xmin<ACC && edge(3)-xmin<ACC, continue; end 146 if edge(1)-xmax>ACC && edge(3)-xmax>ACC, continue; end 147 if edge(2)-ymin<ACC && edge(4)-ymin<ACC, continue; end 148 if edge(2)-ymax>ACC && edge(4)-ymax>ACC, continue; end 149 150 % otherwise, we have to clip the edge ! 151 edge = clipEdge(edge, [box(1) box(2); box(3) box(4)]); 152 153 % display debug info 154 % disp(sprintf('clip edge n°%2d, from %2d to %2d', e, edges(e,1), edges(e,2))); 155 156 % Node for first vertex 157 if ~in1 158 nodes2 = [nodes2; edge([1 2])]; %#ok<AGROW> 159 indN1 = size(nodes2, 1); 160 else 161 indN1 = hashNodes(edges(e, 1)); 162 end 163 164 % Node for second vertex 165 if ~in2 166 nodes2 = [nodes2; edge([3 4])]; %#ok<AGROW> 167 indN2 = size(nodes2, 1); 168 else 169 indN2 = hashNodes(edges(e, 2)); 170 end 171 172 % add clipped edge to the list 173 edges2 = [edges2; indN1 indN2]; %#ok<AGROW> 174 hashEdges(e) = size(edges2, 1); 175end 176 177 178%% Clip the faces 179faces2 = {}; 180for f = 1:length(faces) 181 % indices of vertices of current face 182 face = faces{f}; 183 184 % if the face is not clipped, use directly new indices of nodes 185 face2 = hashNodes(face)'; 186 if ~ismember(0, face2) 187 faces2 = [faces2, {face2}]; %#ok<AGROW> 188 continue; 189 end 190 191 % At least one vertex is clipped. Here is some more special processing 192 193 % edges of current face 194 faceEdges = sort([face' face([2:end 1])'], 2); 195 196 % indices of face edges in edges array 197 indEdges = ismember(edges, faceEdges, 'rows'); 198 199 % convert to indices of edges in clipped edges array. indEdges with 200 % value=0 correspond to totally clipped edges, and can be removed. 201 indEdges = hashEdges(indEdges); 202 indEdges = indEdges(indEdges~=0); 203 204 % case of face totally clipped: break and continuue with next face 205 if isempty(indEdges) 206 continue; 207 end 208 209 % extract indices of vertices of the clipped face 210 face2 = edges2(indEdges, :); 211 face2 = unique(face2(:)); 212 213 % Test whether one should add one of the corner of the box. 214 poly = [nodes(face, 1) nodes(face, 2)]; 215 ind = inpolygon(corners(:,1), corners(:,2), poly(:,1), poly(:,2)); 216 if sum(ind)>0 217 nodes2 = [nodes2; corners(ind, :)]; %#ok<AGROW> 218 face2 = [face2; size(nodes2, 1)]; %#ok<AGROW> 219 end 220 221 % vertices of the face, as points 222 faceNodes = nodes2(face2, :); 223 224 % sort vertices according to their angle around the centroid 225 [faceNodes, I] = angleSort(faceNodes, centroid(faceNodes)); %#ok<ASGLU> 226 227 % add current face to list of faces 228 faces2 = [faces2, {face2(I)'}]; %#ok<AGROW> 229end 230 231 232%% Format output arguments 233 234% clean up nodes to ensure coord correspond to clipping box. 235nodes2(:,1) = min(max(nodes2(:,1), box(1)), box(2)); 236nodes2(:,2) = min(max(nodes2(:,2), box(3)), box(4)); 237 238if nargout==2 239 varargout{1} = nodes2; 240 varargout{2} = edges2; 241elseif nargout==3 242 varargout{1} = nodes2; 243 varargout{2} = edges2; 244 varargout{3} = faces2; 245end 246 247