File Exchange

## Accurate polygon extension

version 1.5.0.0 (8.03 KB) by
Enlarges polygon by a specified range. Also generates internal polygons caused by intersections.

Updated 27 Jan 2009

View Version History

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.

### Cite As

Krispijn Scholte (2021). Accurate polygon extension (https://www.mathworks.com/matlabcentral/fileexchange/21925-accurate-polygon-extension), MATLAB Central File Exchange. Retrieved .

Michael Spencer

The function sometimes returns incorrect results as shown by this script:

% Define a simple polygon:
%originalPolygon = [2.70,0.84; 0.81,-1.65; -2.24,-1.21; -0.35,2.02]; % this works
%originalPolygon = [1.77,0.84; 0.81,-1.65; -2.24,-1.21; -0.35,2.02]; % this fails with resolution = pi/24
originalPolygon = [1.70,0.84; 0.81,-1.65; -2.24,-1.21; -0.35,2.02]; % this fails with resolution = pi/24

%resolution = pi/25; % works
resolution = pi/24; % fails

range = 0.5;
originalPolygon(end+1,:)=originalPolygon(1,:); % close the polygon.
extendedPolygon = extendPoly(originalPolygon, range, resolution);
xpoly = extendedPolygon{1}(:,1)';
ypoly = extendedPolygon{1}(:,2)';

figure
hold on
plot(originalPolygon(:,1), originalPolygon(:,2), 'r*')
%plot([xpoly xpoly(1)], [ypoly ypoly(1)], 'b.-');
plot(xpoly, ypoly, 'b.-');
axis equal
hold off

Wang Jack

How handle polygon with hole?

Kim

Great submission, thanks for this, saved me a heap of time. Had self-intersection issues with the following polygon though:

[5950,4900;5950,4960;5970,4960;5990,4960;6010,4960;6010,4940;6030,4940;6050,4940;6050,4920;6030,4920;6010,4920;6010,4900;5990,4900;5990,4920;5970,4920;5970,4900;5950,4900;]

I would like the two intersecting 'blocks' on the lower part of the polygon to 'merge' where they intersect. I realize this is likely to be a difficult task, but any ideas?

Christoph

Can anyone comment on the performance limits experienced with the program?

I find the program very useful, but on my not so powerful laptop it refuses to extend (basic, almost rectangle-shaped) polygons of about 1000 points ('busy' until ML crashes).

Thanks to the author for the program anyway!

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!

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

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.

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!!

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.

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

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.

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.

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

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.

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.

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.

"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

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.

##### MATLAB Release Compatibility
Created with R2008a
Compatible with any release
##### Platform Compatibility
Windows macOS Linux