How can I create a filled polygon from unordered edge data in MATLAB?

Question

I want to create a polygon using edge data (X,Y coordinates of each point of edge) that is unordered, and I want to fill that polygon with some color.

Any suggestions how I can accomplish this?

Answer 1

If your polygon is convex, you can just compute the convex hull from the vertices using the function CONVHULL and plot the polygon using the plotting function PATCH. For example:

x = [0 1 0 1];  %# Unordered x coordinates of vertices
y = [0 1 1 0];  %# Corresponding y coordinates of vertices
hullIndices = convhull(x,y);  %# Gives vertex indices running counterclockwise
                              %#   around the hull
patch(x(hullIndices),y(hullIndices),'r');  %# Plot the polygon in red

If your polygon is instead concave, that becomes trickier. You would have to reorder the edge lines yourself by comparing their end points and ordering them in either a clockwise or counterclockwise fashion.

...but if that sounds like too much work to code up, you can sidestep the issue by creating a constrained Delaunay triangulation of the vertex points, find the triangles on the inside of the constrained edges, then plot these individual triangles that form the polygon using PATCH. For example:

x = [0 1 0 1 0.5];    %# Unordered x coordinates of vertices
y = [0 1 1 0 0.5];    %# Corresponding y coordinates of vertices
edgeLines = [1 3;...  %# Point 1 connects to point 3
             1 4;...  %# Point 1 connects to point 4
             2 3;...  %# Point 2 connects to point 3
             2 5;...  %# Point 2 connects to point 5
             5 4];    %# Point 5 connects to point 4
dt = DelaunayTri(x(:),y(:),edgeLines);  %# Create a constrained triangulation
isInside = inOutStatus(dt);  %# Find the indices of inside triangles
faces = dt(isInside,:);      %# Get the face indices of the inside triangles
vertices = [x(:) y(:)];      %# Vertex data for polygon
hPolygon = patch('Faces',faces,...
                 'Vertices',vertices,...
                 'FaceColor','r');  %# Plot the triangular faces in red

The above will display the polygon with edge lines around each sub-triangle that forms it. If you just want an edge line shown around the outside of the entire polygon, you can add the following:

set(hPolygon,'EdgeColor','none');  %# Turn off the edge coloring
xEdge = x(edgeLines).';           %'# Create x coordinates for the edge
yEdge = y(edgeLines).';           %'# Create y coordinates for the edge
hold on;                           %# Add to the existing plot
line(xEdge,yEdge,'Color','k');     %# Plot the edge in black