Code covered by the BSD License  

Highlights from
Accurate polygon extension

4.66667

4.7 | 9 ratings Rate this file 29 Downloads (last 30 days) File Size: 8.03 KB File ID: #21925
image thumbnail

Accurate polygon extension

by

 

28 Oct 2008 (Updated )

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

| Watch this File

File Information
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

Curve Intersections inspired this file.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (15)
06 Sep 2013 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?

31 Jan 2013 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!

28 Jan 2009 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!

28 Jan 2009 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.

26 Jan 2009 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.

13 Jan 2009 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!!

10 Nov 2008 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.

30 Oct 2008 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.

30 Oct 2008 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.

30 Oct 2008 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.

29 Oct 2008 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).

29 Oct 2008 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.

29 Oct 2008 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.

29 Oct 2008 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.

28 Oct 2008 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.

Updates
29 Oct 2008

Fixed bug in determining if input polygon is defined CW or CCW

29 Oct 2008

Added a bunch error and warning messages for badly formed input. Automatically closes input polygon if not closed (warning generated).

10 Nov 2008

New and faster CW/CCW detection method for the input polygon. Old method returned incorrect results when the polygon points have negative x-values only.

27 Jan 2009

v1.5: Replaced selfintersection algorithm because it yielded inaccurate results; added user definable resolution parameter for drawing the circle pieces of the resulting polygon.

27 Jan 2009

v1.5 Replaced selfintersection algorithm because it yielded inaccurate results; added user definable resolution parameter for drawing the circle pieces of the resulting polygon.

Contact us