Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Software » comp.soft-sys.matlab

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Kenan

Posts: 7
Registered: 4/24/13
Polybool gives subtraction with wrong vertices
Posted: May 1, 2013 6:57 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.