Accurate polygon extension

Enlarges polygon by a specified range. Also generates internal polygons caused by intersections.

Description

This function extends a polygon by a specified range. It also generates internal polygons caused by intersections.

The resulting polygon does not preserve the original shape of the input polygon (see screenshot above), but represents the range specified from the input polygon.

Example of usage is given in the m-file header (or type "help extendPoly").

Credit to NS for the self intersection algorithm.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Curve intersections

• MATLAB release: MATLAB 7.6 (R2008a)

[John D'Errico]

This looks reasonable. Decent help. But it fails to run properly. A simple test with a randomly generated triangle leaves either no polygon generated at all, or when it does return something, the extended polygon is completely wrong. Try this test out a few times.

P0 = rand(3,2);
P0 = P0([1 2 3 1],:);
P1 = extendPoly(rand(3,2) , .1 );
plot(P0(:,1),P0(:,2),'-o',P1{1}(:,1),P1{1}(:,2),'.r-')

With repairs to make this work, I'd be quite willing to raise my rating.

[Krispijn Scholte]

Thank you for your feedback John. Discovered and fixed a small bug in determining if the input polygon is defined CW or CCW.

Please note that your test code should read:
"P1 = extendPoly(rand(3,2) , .1 );" should read "P1 = extendPoly(P0 , .1 );" Because otherwise the extended polygon will always be different from the input.

[John D'Errico]

Doh. Yes. That will explain why I was seeing a different polygon when it did run. The issue I was chasing initially was in the empty results that were happening. I'll test that when the new version is up there and if it works, I'll raise my rating.

[John D'Errico]

Better now, as it now works on polygons in any orientation.

Further testing shows that despite the inclusion of code to apparently test for self intersecting polygons, there is no error generated when that happens.

P0 = [0 0;0 1;1 0;1 1;0 0];
P1 = extendPoly(P0,.1);
plot(P0(:,1),P0(:,2),'-o',P1{1}(:,1),P1{1}(:,2),'.r-')

Be nice to your users. Check for errors, and then give them some feedback when the inputs fails to satisfy the necessary constraints. I'd also suggest testing for the correct size inputs. For example, if they call extendPoly as

P1 = extendPoly(rand(5,3),.1);

good code should exit gracefully.

help error

I'm now up to 3.5 stars, but I'll round up to 4 stars, since the code is well documented, and the author fixed the last problem. I'd change the rating to 5 stars with friendly error handling.

[Krispijn Scholte]

Updated to v1.3: Added warning and error messages as well as automatic polygon closing (generates a warning).

Thanks for taking the time to review the code (first time contributing).

[John D'Errico]

This submission has improved nicely with each iteration. I thank the author for the fixes, as well as thinking of the additional improvement of testing for and closing unclosed polygons, something I should have thought to suggest.

There is now error checking. The code is friendly to its users.

Well done, and welcome to the File Exchange.

[Kelly Kearney]

This algorithm looks interesting, and I wanted to try to compare the computation time and results with Matlab's bufferm function (part of the Mapping Toolbox) and my own bufferm2 function (a modification on bufferm available on the FEX). I habitually use these functions to extend complex but non-self-intersecting polygons, usually the borders of various lakes, oceans, basins, etc. However, my tests (trying to buffer a simplified version of the Great Lakes) have so far failed to return a non-empty array. Stepping through the code, it seems the original polygon extension (lines 195-254) creates very interesting but unexpected modern-art scribble resembling the Lakes, which is then completely eliminated in the next step due self-intersection. Are there limitations to your algorithm that aren't mentioned here?

This function does seem a bit more limited than the functions I mentioned. It can only buffer outwards, not inwards. Also, it cannot handle NaNs in the polygon definition, which is the typical Matlab syntax to indicate a multi-segment polygon, both in plotting and the other polygon-related functions (mostly Mapping Toolbox functions). However, it doesn't rely on the Mapping Toolbox, which could be a nice advantage over bufferm and bufferm2. I'll withhold my rating until I determine the cause of my incorrect results.

[Krispijn Scholte]

The algorithm wasn't intended for use with negative ranges. I originally made for plotting weapon ranges from areas a threat is expected which entails only positive ranges.

I've allowed the code to run with negative ranges, as I have observed some results that seemed correct, but it generates a warning as I have not really tested it and it wasn't originally intended to do so.

The NaN scenario has not occured to me (I do not have the mapping toolbox) but I can imagine that it would be possible to modify it in order to run the code on each segment. The code is intended for a single segment.

A work around for this should probably look like something along these lines:
[mcode]
P0 = [rand(3,2);NaN,NaN;rand(3,2)];

%rewrite the segmented polygon to a cell array
segmentCounter = 1;
pointIndexCounter = 1;
for i=1:size(P0,1)
    if ~isnan(P0(i,1))
        P0cell{segmentCounter}(pointIndexCounter,:)=P0(i,:);
        pointIndexCounter = pointIndexCounter + 1;
    else
        segmentCounter = segmentCounter + 1;
        pointIndexCounter = 1;
    end
end

figure(1);hold on; axis equal;

for i=1:length(P0cell)
   
    P1 = extendPoly(P0cell{i}, .1 );
    figure(1); plot(P0cell{i}(:,1),P0cell{i}(:,2),'-o',P1{1}(:,1),P1{1}(:,2),'.r-');
    
end

hold off;
[/mcode]

Might be interesting to include in a next version.

[Kelly Kearney]

The Nov 10 update fixes the bug I was seeing that generated empty results; the extended polygons created for my test polygons look good now. This function is still slower than bufferm.m (by about a factor of 10), but has the very nice advantage of not requiring the Mapping Toolbox. Thanks to the author for the quick response to comments.

[Wilbert van Norden]

Function does exactly what I expected, in my case expending freely drawn areas (polygons) by a given weapon range or sensor range.
Although it first glance the problem seemed simple, it is somewhat complex so thanks for posting this!!

[Andres]

Thanks for sharing this! The polygon extension is a most desirable function - but I think there is some unexpected behaviour with your code. I've tested some polygons with your help code

extendedPolygon = extendPoly(Polygon,0.4);
figure(1); clf; patch(Polygon(:,1),Polygon(:,2),'r');
for i=1:length(extendedPolygon)
 toPlot=extendedPolygon{i};
 line(toPlot(:,1),toPlot(:,2),'Color','b');
end

1) The v-like polygon

Polygon = [0,0;1,1;1,2;0,1.00;-1,2;-1,1;0,0];

produces an self-intersection error, while the very similar

Polygon = [0,0;1,1;1,2;0,0.90;-1,2;-1,1;0,0];

does not.

2) Some banana-like (non-convex) polygons like

xt = (1:5).';
yt = log(xt);
Polygon = [[xt;flipud(xt) ;xt(1)],...
          [ yt;flipud(yt)-1;yt(1)]];

produce a self-intersecting extended polygon, see the detail

xlim([4,4.2])
ylim([-0.02,0.02])

Plus: It would be nice to have control over the resolution of the circular sections of the extended polygon.

[Krispijn Scholte]

Thank you for the feedback. As it turns out, there was a bug in the selfintersection algorithm that I used. This lead to the "V"-polygon being identified as having selfintersections. I have replaced it with a newer, vectorbased one that seems to yield better results.

I have also added the (optional) "resolution"-parameter you requested.

The self-intersecting extended polygon (from the "banana"-poly) still occurs as I have not found out why this happens. When I do, I'll update again.

[Andres]

I hope the self-intersecting extension issue can be fixed. Note that in the center of the V-poly extension there seem to be two identical points in the extended polygon (I just stepped through with a datatip + arrow keys).

But above all, thanks for your fast support!