Prev: PWM Based on Duty
Next: matrix-vector vs. vector-matrix multiplication
From: Peter Simon on 10 Aug 2010 09:27
I'm seeking Matlab code (or even an algorithm) to generate a boundary
polygon whose vertices are a subset of a given set of points, randomly
located in the plane. My actual example is a set of locations sampled
fairly finely within the continental united states. I would like to
obtain a boundary curve from this set that resembles the outline of
the US. In particular, I do not want the convex hull of these points,
which is easy to generate but does not fit "tightly" to the area
enclosed by the points. The polygon will certainly be nonconvex.
Perhaps what I am looking for is the minimum area bounding polygon?
I'm not even sure such a thing is well defined. I can't use image
processing techniques for this because as I understand it, such
techniques require a regular grid covering a rectangular region with
either 1's or 0's defined on each point of the grid. I don't have a
regular grid and I don't have a set of surrounding points with zeros
defined on them. Thanks in advance for any pointers on this question.

--Peter
From: Steven_Lord on 10 Aug 2010 10:03


"Peter Simon" <psimon0420(a)gmail.com> wrote in message
news:9bd0385b-5d4c-417d-992f-1a504ca87d7f(a)l20g2000yqm.googlegroups.com...
> I'm seeking Matlab code (or even an algorithm) to generate a boundary
> polygon whose vertices are a subset of a given set of points, randomly
> located in the plane. My actual example is a set of locations sampled
> fairly finely within the continental united states. I would like to
> obtain a boundary curve from this set that resembles the outline of
> the US. In particular, I do not want the convex hull of these points,
> which is easy to generate but does not fit "tightly" to the area
> enclosed by the points. The polygon will certainly be nonconvex.
> Perhaps what I am looking for is the minimum area bounding polygon?
> I'm not even sure such a thing is well defined. I can't use image
> processing techniques for this because as I understand it, such
> techniques require a regular grid covering a rectangular region with
> either 1's or 0's defined on each point of the grid. I don't have a
> regular grid and I don't have a set of surrounding points with zeros
> defined on them. Thanks in advance for any pointers on this question.
>
> --Peter

You might want to take a look at this thread from about two and a half
months ago.

http://www.mathworks.com/matlabcentral/newsreader/view_thread/282771

Without additional constraints, I don't think your problem is well-posed.

--
Steve Lord
slord(a)mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

From: John D'Errico on 10 Aug 2010 10:43
Peter Simon <psimon0420(a)gmail.com> wrote in message <9bd0385b-5d4c-417d-992f-1a504ca87d7f(a)l20g2000yqm.googlegroups.com>...
> I'm seeking Matlab code (or even an algorithm) to generate a boundary
> polygon whose vertices are a subset of a given set of points, randomly
> located in the plane. My actual example is a set of locations sampled
> fairly finely within the continental united states. I would like to
> obtain a boundary curve from this set that resembles the outline of
> the US. In particular, I do not want the convex hull of these points,
> which is easy to generate but does not fit "tightly" to the area
> enclosed by the points. The polygon will certainly be nonconvex.
> Perhaps what I am looking for is the minimum area bounding polygon?
> I'm not even sure such a thing is well defined. I can't use image
> processing techniques for this because as I understand it, such
> techniques require a regular grid covering a rectangular region with
> either 1's or 0's defined on each point of the grid. I don't have a
> regular grid and I don't have a set of surrounding points with zeros
> defined on them. Thanks in advance for any pointers on this question.
>
> --Peter

An alpha shape is the usual solution, and a good one as long
as your points are reasonably finely sampled.

John
From: Matt J on 10 Aug 2010 10:45
Peter Simon <psimon0420(a)gmail.com> wrote in message <9bd0385b-5d4c-417d-992f-1a504ca87d7f(a)l20g2000yqm.googlegroups.com>...
> I'm seeking Matlab code (or even an algorithm) to generate a boundary
> polygon whose vertices are a subset of a given set of points, randomly
> located in the plane. My actual example is a set of locations sampled
> fairly finely within the continental united states. I would like to
> obtain a boundary curve from this set that resembles the outline of
> the US.
======================

In general, the problem you describe is ill-posed, however, you might be able to condition it by incorporating the a priori information that the boundary points are supposed to look like the US border. For example, you could make an edge map of the U.S. border (scaled the same as your samples) and find the nearest points in your sample set to the points in the edge map...
From: Peter Simon on 10 Aug 2010 13:47
On Aug 10, 7:43 am, "John D'Errico" <woodch...(a)rochester.rr.com>
wrote:
> Peter Simon <psimon0...(a)gmail.com> wrote in message <9bd0385b-5d4c-417d-992f-1a504ca87...(a)l20g2000yqm.googlegroups.com>...
> > I'm seeking Matlab code (or even an algorithm) to generate a boundary
> > polygon whose vertices are a subset of a given set of points, randomly
> > located in the plane.  My actual example is a set of locations sampled
> > fairly finely within the continental united states.  I would like to
> > obtain a boundary curve from this set that resembles the outline of
> > the US.  In particular, I do not want the convex hull of these points,
> > which is easy to generate but does not fit "tightly" to the area
> > enclosed by the points. The polygon will certainly be nonconvex.
> > Perhaps what I am looking for is the minimum area bounding polygon?
> > I'm not even sure such a thing is well defined.  I can't use image
> > processing techniques for this because as I understand it, such
> > techniques require a regular grid covering a rectangular region with
> > either 1's or 0's defined on each point of the grid.  I don't have a
> > regular grid and I don't have a set of surrounding points with zeros
> > defined on them.  Thanks in advance for any pointers on this question..
>
> > --Peter
>
> An alpha shape is the usual solution, and a good one as long
> as your points are reasonably finely sampled.
>
> John

Thanks to all who replied, and especially to John, who hit the nail on
the head. I had never heard of an "alpha shape" before, but it is
precisely what I was looking for. It was trivial to construct using
the terrific FEX package by us: http://www.mathworks.com/matlabcentral/fileexchange/6760

If anyone is interested in seeing my dataset along with the boundary
curve determined by us's routine ashape.m, I've posted the image at
http://users.vcnet.com/simonp/matlab/conus_alphashape.pdf

Thanks again.

--Peter
 |  Next  |  Last
Pages: 1 2
Prev: PWM Based on Duty
Next: matrix-vector vs. vector-matrix multiplication