MATLAB Central Newsreader - Polygon from Unordered set of points

Polygon from Unordered set of points

Balwinder Singh — Mon, 01 Jun 2009 02:57:01 -0400

Hi All,
I have an unordered set of points (x,y). I want to form a polygon from these vertices which should arrange the points in either clockwise or anticlockwise sense. Is it possible to do in MATLAB?

Thanks.

Re: Polygon from Unordered set of points

Bruno Luong — Mon, 01 Jun 2009 11:34:02 -0400

"Balwinder Singh" <balwindersingh@gmail.com> wrote in message <gvvg1t$p64$1@fred.mathworks.com>...
> Hi All,
> I have an unordered set of points (x,y). I want to form a polygon from these vertices which should arrange the points in either clockwise or anticlockwise sense. Is it possible to do in MATLAB?
>

Posed generally like that, the answer is no, because there is many way to connect the points to form a polygon. You need to specify something else. For example:

- Whereas your polygon is convex
- If you look for a polygone that minimizes the circumference.

The first problem is easy, the second problem is called "Travelling Saleman problem", and it is one hardest problem in algorithmic http://en.wikipedia.org/wiki/Travelling_salesman_problem

Now the question is where you place your problem in between?

Bruno

Re: Polygon from Unordered set of points

ImageAnalyst — Mon, 01 Jun 2009 11:53:14 -0400

On May 31, 10:57 pm, "Balwinder Singh" <balwindersi...@gmail.com>
wrote:
> Hi All,
> I have an unordered set of points (x,y). I want to form a polygon from these vertices which should arrange the points in either clockwise or anticlockwise sense. Is it possible to do in MATLAB?
>
> Thanks.

--------------------------
Can't you just find the centroid, then find the angle from the
centroid to each of the points, then sort based on angle? You'd get a
multi-pointed star-like object I would think.

Re: Polygon from Unordered set of points

Luigi Giaccari — Mon, 01 Jun 2009 16:50:19 -0400

"Balwinder Singh" <balwindersingh@gmail.com> wrote in message <gvvg1t$p64$1@fred.mathworks.com>...
> Hi All,
> I have an unordered set of points (x,y). I want to form a polygon from these vertices which should arrange the points in either clockwise or anticlockwise sense. Is it possible to do in MATLAB?
>
> Thanks.

The solution to this problem heavly depends on the shape of your dataset.
ONe solution may be the traveling salesman. For convex shape is the convex hull.

I thing in the general case you have to find delaunay edges.

For more see:

   doc
         demos
                  Mathematics
                                     Creating and editing delaunay triangulation
                                          Example 7(Example Seven: Curve Reconstruction from a Point Cloud)

http://giaccariluigi.altervista.org/blog/