Kenan
Posts:
7
Registered:
4/24/13


Polybool gives subtraction with wrong vertices
Posted:
May 1, 2013 6:57 PM


Hello all,
I am using the function polybool from the Mapping Toolbox and my version of Matlab is R2013a.
I have problems when I perform a simple subtraction of two polygonal regions (a rectangle described by [x1 y1] and a triangle described by [x0 y0]). See attached code and figures.
px = .7; py = .75; lx = (5*2^.56)/20; ly = (10*3^.59)/60;
[x1,y1] = poly2cw([px; px+lx; px+lx; px; px],[py; py; py+ly; py+ly; py]); % rectangle [x0,y0] = poly2cw([15;15;14;15]/19,[15;16;16;15]/19); % triangle [x2,y2] = polybool('intersection',x1,y1,x0,y0); % intersection
[x3,y3] = polybool('subtraction',x0,y0,x2,y2); % soustraction
figure; plot(x0,y0,'b',x1,y1,'k:',x3,y3,'r+'); hold on for i=1:length(x3) text(x3(i)*1.003,y3(i)*1.003,num2str(i)) end
As you can see, there is an extra vertex that should not be there (vertex 23). So instead of being 12,23,34,45,56; the subtraction should be 13,34,45,56. (6 being equal to 1).
This wouldn't be such a bad issue if it was all, but it causes the rest of the algorithm to behave abnormally (after performing a constrained Delaunay triangulation, the function isInterior gives an incorrect result)
First I check if the subtraction [x3 y3] is a connected polygon with ~isShapeMultipart(x3,y3): it is.
If I perform a non constrained Delaunay triangulation, the result contains triangles outside of [x3 y3] (in the general case) and there is no direct way of finding which ones. Hence it is easier to perform a constrained Delaunay triangulation. If I understand the word constrain correctly, Matlab performs the triangulation making sure the vertices in the constrain are vertices of the triangulation. However, it does not mean that these vertices will be the only vertices of the triangulation. I need someone to confirm this statement, or explain to me what is a constrain exactly. So I construct the constraint matrix for the Delaunay triangulation and perform the triangulation:
C3 = zeros(length(x3)1,2); for j=1:2 for i2=1:length(x3)1 C3(i2,j) = i2+j1; end end C3(end,end)=1; DT31 = delaunayTriangulation(x3,y3,C3);
Finally, the statement inside31 = isInterior(DT31) gives 0 0 0 meaning that all 3 triangles in DT31 are outside of the constraint C3.
The code for constructing the constrain matrix C3 could be adapted to the weird result of polybool but I would lose robustness in my code. Plus, I would rather correct the weird result the earliest possible (ie just after [x3,y3] = polybool('subtraction',x0,y0,x2,y2); % soustraction) rather than making corrections afterwards.
Thank you for your precious help and/or remarks.
See here for illustrations: http://stackoverflow.com/questions/16326810/polyboolgivessubtractionwithwrongvertices

