Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Polybool gives subtraction with wrong vertices
Replies: 3   Last Post: May 8, 2013 2:54 PM

 Messages: [ Previous | Next ]
 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^.5-6)/20;
ly = (10*3^.5-9)/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 2-3). So instead of being 1-2,2-3,3-4,4-5,5-6; the subtraction should be 1-3,3-4,4-5,5-6. (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+j-1;
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/polybool-gives-subtraction-with-wrong-vertices

Date Subject Author
5/1/13 Kenan
5/7/13 Kenan