Concave Polygon Triangulation

[Melissa Stein]

Is there a way in Matlab to triangulate a concave polygon? Or split the concave polygon into many convex polygons? I have looked at Delaunay tessellation, but that's not really an option because it also connects points to form triangles that are outside of the polygon. I am trying to use the ear clipping method, but I don't even know where to begin to start with this.

[Damian Sheehy]

Hi Melissa,

This feature is supported in the latest release of MATLAB (R2009a)

Take a look at examples 5 and 6 in the following overview;
http://www.mathworks.com/products/matlab/demos.html?file=/products/demos/shipping/matlab/demoDelaunayTri.html

For more information check out these links.

Video highlighting new CG features (Mathematics heading)
http://www.mathworks.com/products/matlab/whatsnew.html

Function reference pages
http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/matlab.html&http://www.mathworks.com/access/helpdesk/help/helpdesk.html

Bottom of the left hand column
Release Notes->Version 7.8->Mathematics,MATLAB Version 7.8 (R2009a)->Upgrade
to Computational Geometry
TriRep, DelaunayTri, TriScatteredInterp

Best regards,

Damian

"Melissa Stein" <rikki...@gmail.com> wrote in message
news:h0u48p$24q$1...@fred.mathworks.com...

[Melissa]

Hi Damian,

Thanks for the quick response. The problem with the constrain edges method is that although it connects the specified points, it continues to connect outside of the polygon also. Is there a way to specify the order of connection and also constrain to only connecting within the boundaries or your specifications?

[Bruno Luong]

Melissa,

What about a "simple" meshing code:
http://www.mathworks.com/matlabcentral/fileexchange/10307

It would fulfill what you asked for.

Bruno

[Damian Sheehy]

Hi Melissa,

The constrained DelaunayTri will produce a triangulation that fills
the convex hull of your pointset. If you wish to compute the domain
triangulation that represents your polygon, you simply filter out the
triangles that are outside of the domain.

Example 6 shows how to do this;
http://www.mathworks.com/products/matlab/demos.html?file=/products/demos/shipping/matlab/demoDelaunayTri.html

You just compute the in/out status of each triangle as follows;
io = dt.inOutStatus();

This computation is based on Jordan curve parity where your constraints
define the curve.

The set of triangles inside your polygon are given by, dt(io,:)

If this does not address your usecase please let me know.

Thanks,

Damian

"Melissa " <rikki...@gmail.com> wrote in message
news:h0u612$ec$1...@fred.mathworks.com...

[Luigi Giaccari]

One way is to build a constrained triangulation of the polygon, run an inpolygon test with triangles cetroids, discard outside triangles.

You can find the inpolygon test fro Darren Engwirda (or similar)

http://giaccariluigi.altervista.org/blog/

[John Paden]

"Luigi Giaccari" <giacca...@msn.com> wrote in message <h3829a$elj$1...@fred.mathworks.com>...

> One way is to build a constrained triangulation of the polygon, run an inpolygon test with triangles cetroids, discard outside triangles.
>
> You can find the inpolygon test fro Darren Engwirda (or similar)
>
> http://giaccariluigi.altervista.org/blog/

If you know your concave hull, I have used two methods:

1) Use inpolygon test as indicated above (does not require a constrained triangulization, but it might be a good idea)... but this can be slow for large datasets

2) Another method is to build a constrained triangulization with DelaunayTri, use the inOutStatus command to find the triangles outside the concave hull, then use the pointLocation command on each of the points (rather than inpolygon), and remove points that land in the bad triangles. pointLocation/inOutStatus may be a lot faster than inpolygon.

For my case, pnts is a 3xNxM array where the concave hull was the outside of the NxM shape.

% Setting concave_hull will be specific to your particular problem, but the rest is
% pretty generic
concave_hull = [ [(1:size(pnts,2)-1).' (2:size(pnts,2)).'];
size(pnts,2)*[(1:size(pnts,3)-1).' (2:size(pnts,3)).'];
size(pnts,2)*(size(pnts,3)-1) + [(size(pnts,2):-1:2).' (size(pnts,2)-1:-1:1).'];
size(pnts,2)*[(size(pnts,3):-1:2).' (size(pnts,3)-1:-1:1).']-size(pnts,2)+1 ];
dt = DelaunayTri(pnts(1,:).',pnts(2,:).',concave_hull);

F = TriScatteredInterp(dt,pnts(3,:).');
meas{measInd}.DEM = F(eastMesh,northMesh);

if 0
% Slow method using inpolygon
boundary = [pnts(1:2,:,1) squeeze(pnts(1:2,end,:)) squeeze(pnts(1:2,end:-1:1,end)) squeeze(pnts(1:2,1,end:-1:1))];
good_mask = ~isnan(meas{measInd}.DEM);
good_mask_idx = find(good_mask);
in = inpolygon(eastMesh(good_mask),northMesh(good_mask),boundary(1,:),boundary(2,:));
good_mask(good_mask_idx(~in)) = 0;
meas{measInd}.DEM(~good_mask) = NaN;
else
% Faster method using inOutStatus/pointLocation with edge constraints
% Finds the triangles outside the concave hull (the bad ones)
bad_tri_mask = ~inOutStatus(dt);
% Selects just the points that were in the convex hull
good_mask = ~isnan(meas{measInd}.DEM);
good_mask_idx = find(good_mask);
% For each point in the convex hull, find the triangle enclosing it
tri_list = pointLocation(dt,eastMesh(good_mask),northMesh(good_mask));
% Use the bad triangle list to find the bad points
bad_mask = bad_tri_mask(tri_list);
% Set all the points in bad triangles to NaN
good_mask(good_mask_idx(bad_mask)) = 0;
meas{measInd}.DEM(~good_mask) = NaN;
end

[carmen]

Dear John,
do you know if this method is also applicable to 3d-sets of points describing concave body surfaces? i ask because inOutStatus does only apply to 2d problems.
thanks.

"John Paden" wrote in message <jb7onh$e5o$1...@newscl01ah.mathworks.com>...