1## Copyright (C) 2011-2020, José Luis García Pallero, <jgpallero@gmail.com> 2## 3## This file is part of OctCLIP. 4## 5## OctCLIP is free software; you can redistribute it and/or modify it 6## under the terms of the GNU General Public License as published by 7## the Free Software Foundation; either version 3 of the License, or (at 8## your option) any later version. 9## 10## This program is distributed in the hope that it will be useful, but 11## WITHOUT ANY WARRANTY; without even the implied warranty of 12## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13## General Public License for more details. 14## 15## You should have received a copy of the GNU General Public License 16## along with Octave; see the file COPYING. If not, see 17## <http://www.gnu.org/licenses/>. 18 19## -*- texinfo -*- 20## @deftypefn {}{[@var{p},@var{details}] =}_oc_polybool(@var{sub},@var{clip}) 21## @deftypefnx {}{[@var{p},@var{details}] =}_oc_polybool(@var{sub},@var{clip},@var{op}) 22## @deftypefnx {}{[@var{p},@var{details}] =}_oc_polybool(@var{sub},@var{clip},@var{op},@var{hor}) 23## 24## @cindex Performs boolean operations between two polygons. 25## 26## This function performs boolean operations between two polygons using the 27## Greiner-Hormann algorithm as it is presented in 28## http://davis.wpi.edu/~matt/courses/clipping/ 29## 30## @var{sub} is a two column matrix containing the X and Y coordinates of the 31## vertices for the subject polygon (it must be unique, although 32## self-intersections are permitted). 33## 34## @var{clip} is a two column matrix containing the X and Y coordinates of the 35## vertices for the clipper polygon(it must be unique, although 36## self-intersections are permitted). 37## 38## @var{op} is a text string containing the operation to perform between 39## @var{sub} and @var{clip}. Possible values are: 40## 41## @itemize @bullet 42## @item @var{'AND'} 43## Intersection of @var{sub} and @var{clip}. This value is set by default. 44## @item @var{'OR'} 45## Union of @var{sub} and @var{clip}. 46## @item @var{'AB'} 47## Operation @var{sub} - @var{clip}. 48## @item @var{'BA'} 49## Operation of @var{clip} - @var{sub}. 50## @item @var{'XOR'} 51## Exclusive disjunction between @var{clip} and @var{sub}. This operation is 52## performed as the joining of 'AB' and 'BA' consecutively applied 53## @end itemize 54## 55## @var{hor} is an identifier for performing (value 1, by default) or not 56## (value 0) the searching for holes in the result of the operation OR. When OR 57## is applied with non convex entities some of the resulting polygons can be 58## actually holes. Activating this argument the possible holes are identified. 59## If the operation is other than OR the value of this argument is irrelevant 60## 61## For the matrices @var{sub} and @var{clip}, the first point is not needed to 62## be repeated at the end (but is permitted). Pairs of (NaN,NaN) coordinates in 63## @var{sub} and/or @var{clip} are omitted, so they are treated as if each one 64## stored a single polygon, i.e., this function does not admit boolean 65## operations between multiple polygons of between polygons with holes, although 66## polygons containing self-intersections are permitted 67## 68## @var{p} is a two column matrix containing the X and Y coordinates of the 69## vertices of the resultant polygon(s). If the result consist of multiple 70## polygons they are separated by rows os (NaN,NaN) values. 71## 72## @var{details} is a struct containing details of the computation. Its fields 73## (IN LOWERCASE!) are: 74## 75## @itemize @bullet 76## @item @var{poly} 77## Three-column matrix with a number of rows equal to the number of polygons 78## stored in the matrix @var{p}. The first column stores the row of @var{p} 79## where the corresponding polygon starts, the second column the row of @var{p} 80## where the polygon end, and the third colum is a mark identifying if the 81## polygon is a hole (value 0) or not (value 1). The values of the third column 82## are relevant only in the case of the OR operation 83## @item @var{nint} 84## Number of intersections between @var{sub} and @var{clip}. 85## @item @var{npert} 86## Number of perturbed points of the @var{clip} polygon if any particular case 87## (points in the border of the other polygon) occurs see 88## http://davis.wpi.edu/~matt/courses/clipping/ for details. 89## @end itemize 90## 91## This function does not check if the dimensions of @var{sub} and @var{clip} 92## are correct. 93## 94## @end deftypefn 95 96function [p,details] = oc_polybool(sub,clip,op,hor) 97 98try 99 functionName = 'oc_polybool'; 100 minArg = 2; 101 maxArg = 4; 102 103%******************************************************************************* 104%NUMBER OF INPUT ARGUMENTS CHECKING 105%******************************************************************************* 106 107 %number of input arguments checking 108 if (nargin<minArg)||(nargin>maxArg) 109 error(['Incorrect number of input arguments (%d)\n\t ',... 110 'Correct number of input arguments = %d or %d'],... 111 nargin,minArg,maxArg); 112 end 113 %values by default 114 opDef = 'AND'; 115 horDef = 1; 116 %check if we omit some input arguments 117 if nargin<maxArg 118 %hor by default 119 hor = horDef; 120 %check for op 121 if nargin==minArg 122 %op by default 123 op = opDef; 124 end 125 end 126 127%******************************************************************************* 128%INPUT ARGUMENTS CHECKING 129%******************************************************************************* 130 131 %checking input arguments 132 [op] = checkInputArguments(sub,clip,op); 133catch 134 %error message 135 error('\n\tIn function %s:\n\t -%s ',functionName,lasterr); 136end 137 138%******************************************************************************* 139%COMPUTATION 140%******************************************************************************* 141 142try 143 %calling oct function 144 [p,pp,nInt,nPert] = _oc_polybool(sub,clip,op,hor); 145 %creation of the output struct 146 details.poly = pp; 147 details.nint = nInt; 148 details.npert = nPert; 149catch 150 %error message 151 error('\n\tIn function %s:\n\tIn function %s ',functionName,lasterr); 152end 153 154 155 156 157%******************************************************************************* 158%AUXILIARY FUNCTION 159%******************************************************************************* 160 161 162 163 164function [outOp] = checkInputArguments(sub,clip,inOp) 165 166%sub must be matrix type 167if isnumeric(sub) 168 %a dimensions 169 [rowSub,colSub] = size(sub); 170else 171 error('The first input argument is not numeric'); 172end 173%clip must be matrix type 174if isnumeric(clip) 175 %b dimensions 176 [rowClip,colClip] = size(clip); 177else 178 error('The second input argument is not numeric'); 179end 180%checking dimensions 181if (colSub~=2)||(colClip~=2) 182 error('The columns of input arguments must be 2'); 183end 184%operation must be a text string 185if ~ischar(inOp) 186 error('The third input argument is not a text string'); 187else 188 %upper case 189 outOp = upper(inOp); 190 %check values 191 if (~strcmp(outOp,'AND'))&&(~strcmp(outOp,'OR'))&& ... 192 (~strcmp(outOp,'AB'))&&(~strcmp(outOp,'BA'))&&(~strcmp(outOp,'XOR')) 193 error('The third input argument is not correct'); 194 end 195end 196 197 198 199 200%*****END OF FUNCIONS***** 201 202 203 204 205%*****FUNCTION TESTS***** 206 207 208 209 210%tests for input arguments 211%!error(oc_polybool) 212%!error(oc_polybool(1)) 213%!error(oc_polybool(1,2,3,4,5)) 214%!error(oc_polybool('string',2,3)) 215%!error(oc_polybool(1,'string',3)) 216%!error(oc_polybool(1,2,3)) 217%demo program 218%!demo 219%! %subject polygon 220%! clSub = [9.0 7.5 221%! 9.0 3.0 222%! 2.0 3.0 223%! 2.0 4.0 224%! 8.0 4.0 225%! 8.0 5.0 226%! 2.0 5.0 227%! 2.0 6.0 228%! 8.0 6.0 229%! 8.0 7.0 230%! 2.0 7.0 231%! 2.0 7.5 232%! 9.0 7.5]; 233%! %clipper polygon 234%! clClip = [2.5 1.0 235%! 7.0 1.0 236%! 7.0 8.0 237%! 6.0 8.0 238%! 6.0 2.0 239%! 5.0 2.0 240%! 5.0 8.0 241%! 4.0 8.0 242%! 4.0 2.0 243%! 3.0 2.0 244%! 3.0 8.0 245%! 2.5 8.0 246%! 2.5 1.0]; 247%! %limits for the plots 248%! clXLim = [1.5 11.75]; 249%! clYLim = [0.5 8.50]; 250%! %compute intersection 251%! [pI,detI] = oc_polybool(clSub,clClip,'and'); 252%! %compute union 253%! [pU,detU] = oc_polybool(clSub,clClip,'or',1); 254%! %compute A-B 255%! [pA,detA] = oc_polybool(clSub,clClip,'ab'); 256%! %compute B-A 257%! [pB,detB] = oc_polybool(clSub,clClip,'ba'); 258%! %compute XOR 259%! [pX,detX] = oc_polybool(clSub,clClip,'xor'); 260%! %plotting 261%! figure(1); 262%! %plot window for original data 263%! subplot(3,2,1); 264%! plot(clSub(:,1),clSub(:,2),clClip(:,1),clClip(:,2)); 265%! axis('equal'); 266%! xlim(clXLim); 267%! ylim(clYLim); 268%! title('Original polygons'); 269%! legend('Subject polygon','Clipper polygon','location','southeast'); 270%! %plot window for intersection 271%! subplot(3,2,2); 272%! hold('on'); 273%! for i=1:size(detI.poly,1) 274%! pS = detI.poly(i,1); 275%! pE = detI.poly(i,2); 276%! fill(pI(pS:pE,1),pI(pS:pE,2),'r'); 277%! end 278%! hold('off'); 279%! axis('equal'); 280%! xlim(clXLim); 281%! ylim(clYLim); 282%! title('OctCLIP intersection'); 283%! %plot window for union 284%! subplot(3,2,3); 285%! hold('on'); 286%! for i=1:size(detU.poly,1) 287%! pS = detU.poly(i,1); 288%! pE = detU.poly(i,2); 289%! if detU.poly(i,3)~=0 290%! fill(pU(pS:pE,1),pU(pS:pE,2),'r'); 291%! else 292%! hax = fill(pU(pS:pE,1),pU(pS:pE,2),'b'); 293%! legend(hax,'Holes'); 294%! end 295%! end 296%! hold('off'); 297%! axis('equal'); 298%! xlim(clXLim); 299%! ylim(clYLim); 300%! title('OctCLIP union'); 301%! %plot window for A-B 302%! subplot(3,2,4); 303%! hold('on'); 304%! for i=1:size(detA.poly,1) 305%! pS = detA.poly(i,1); 306%! pE = detA.poly(i,2); 307%! fill(pA(pS:pE,1),pA(pS:pE,2),'r'); 308%! end 309%! hold('off'); 310%! axis('equal'); 311%! xlim(clXLim); 312%! ylim(clYLim); 313%! title('OctCLIP A-B'); 314%! %plot window for B-A 315%! subplot(3,2,5); 316%! hold('on'); 317%! for i=1:size(detB.poly,1) 318%! pS = detB.poly(i,1); 319%! pE = detB.poly(i,2); 320%! fill(pB(pS:pE,1),pB(pS:pE,2),'r'); 321%! end 322%! hold('off'); 323%! axis('equal'); 324%! xlim(clXLim); 325%! ylim(clYLim); 326%! title('OctCLIP B-A'); 327%! %plot window for XOR 328%! subplot(3,2,6); 329%! hold('on'); 330%! for i=1:size(detX.poly,1) 331%! pS = detX.poly(i,1); 332%! pE = detX.poly(i,2); 333%! fill(pX(pS:pE,1),pX(pS:pE,2),'r'); 334%! end 335%! hold('off'); 336%! axis('equal'); 337%! xlim(clXLim); 338%! ylim(clYLim); 339%! title('OctCLIP XOR'); 340%! %input message 341%! disp('Press ENTER to continue ...'); 342%! pause(); 343%! 344%! %subject polygon 345%! clSub = [1000.0 1000.0 346%! 2000.0 1000.0 347%! 2000.0 2800.0 348%! 800.0 2800.0 349%! 2400.0 1900.0 350%! 1000.0 1000.0]; 351%! %clipper polygon 352%! clClip = [ 300.0 2500.0 353%! 2500.0 2600.0 354%! 1600.0 600.0 355%! 1300.0 3100.0 356%! 500.0 900.0 357%! 300.0 2500.0]; 358%! %limits for the plots 359%! auxLim = [clSub;clClip]; 360%! clXLim = [min(auxLim(:,1)) max(auxLim(:,1))]; 361%! clYLim = [min(auxLim(:,2)) max(auxLim(:,2))]; 362%! %compute intersection 363%! [pI,detI] = oc_polybool(clSub,clClip,'and'); 364%! %compute union 365%! [pU,detU] = oc_polybool(clSub,clClip,'or',1); 366%! %compute A-B 367%! [pA,detA] = oc_polybool(clSub,clClip,'ab'); 368%! %compute B-A 369%! [pB,detB] = oc_polybool(clSub,clClip,'ba'); 370%! %compute XOR 371%! [pX,detX] = oc_polybool(clSub,clClip,'xor'); 372%! %plotting 373%! figure(2); 374%! %plot window for original data 375%! subplot(3,2,1); 376%! plot(clSub(:,1),clSub(:,2),clClip(:,1),clClip(:,2)); 377%! axis('equal'); 378%! xlim(clXLim); 379%! ylim(clYLim); 380%! title('Original polygons'); 381%! legend('Subject polygon','Clipper polygon','location','southeast'); 382%! %plot window for intersection 383%! subplot(3,2,2); 384%! hold('on'); 385%! for i=1:size(detI.poly,1) 386%! pS = detI.poly(i,1); 387%! pE = detI.poly(i,2); 388%! fill(pI(pS:pE,1),pI(pS:pE,2),'r'); 389%! end 390%! hold('off'); 391%! axis('equal'); 392%! xlim(clXLim); 393%! ylim(clYLim); 394%! title('OctCLIP intersection'); 395%! %plot window for union 396%! subplot(3,2,3); 397%! hold('on'); 398%! for i=1:size(detU.poly,1) 399%! pS = detU.poly(i,1); 400%! pE = detU.poly(i,2); 401%! if detU.poly(i,3)~=0 402%! fill(pU(pS:pE,1),pU(pS:pE,2),'r'); 403%! else 404%! hax = fill(pU(pS:pE,1),pU(pS:pE,2),'b'); 405%! legend(hax,'Holes'); 406%! end 407%! end 408%! hold('off'); 409%! axis('equal'); 410%! xlim(clXLim); 411%! ylim(clYLim); 412%! title('OctCLIP union'); 413%! %plot window for A-B 414%! subplot(3,2,4); 415%! hold('on'); 416%! for i=1:size(detA.poly,1) 417%! pS = detA.poly(i,1); 418%! pE = detA.poly(i,2); 419%! fill(pA(pS:pE,1),pA(pS:pE,2),'r'); 420%! end 421%! hold('off'); 422%! axis('equal'); 423%! xlim(clXLim); 424%! ylim(clYLim); 425%! title('OctCLIP A-B'); 426%! %plot window for B-A 427%! subplot(3,2,5); 428%! hold('on'); 429%! for i=1:size(detB.poly,1) 430%! pS = detB.poly(i,1); 431%! pE = detB.poly(i,2); 432%! fill(pB(pS:pE,1),pB(pS:pE,2),'r'); 433%! end 434%! hold('off'); 435%! axis('equal'); 436%! xlim(clXLim); 437%! ylim(clYLim); 438%! title('OctCLIP B-A'); 439%! %plot window for XOR 440%! subplot(3,2,6); 441%! hold('on'); 442%! for i=1:size(detX.poly,1) 443%! pS = detX.poly(i,1); 444%! pE = detX.poly(i,2); 445%! fill(pX(pS:pE,1),pX(pS:pE,2),'r'); 446%! end 447%! hold('off'); 448%! axis('equal'); 449%! xlim(clXLim); 450%! ylim(clYLim); 451%! title('OctCLIP XOR'); 452 453 454 455 456%*****END OF TESTS***** 457