0

I would like to ask how to arrange points to plot a closed polygon.

In my application I will have a collection of points that describe a shape that might be convex or concave - and I would like to draw the polygon. The problem is that the order of the points is such that a straightforward plot command will not generate the polygon I want.

For example:

dtheta = pi/150;
theta  = (-pi:dtheta:(pi-dtheta))';
X1   = cos(theta); 
X2   = sin(theta);
[n1,In1]=sort(X1);  % sort is intentional here
n2=X2(In1);

Now, 

plot(n1,n2,'.')

gives me a circle shaped arrangement of points

However, using

plot(n1,n2)

the circle is not noticeable at all because of the order of how points are connected.

Is there a way of arranging (n1,n2) such that when plot(n1,n2) is called, a polygon can be plotted clearly, in this case a circle?

mikeP
  • 801
  • 2
  • 11
  • 20

2 Answers2

2

Just don't sort first. Instead, do

dtheta = pi/150;
theta  = (-pi:dtheta:(pi-dtheta))';
X1   = cos(theta); 
X2   = sin(theta);
plot(X1, X2);

Note this will not close the polygon, since your theta doesn't "go all the way around". If instead you define

theta = linspace(-pi, pi, 301); % 301 = 2 * 150 + 1 for repeated end point

You will have points spaced the same way, but now you will repeat the first point as the last point and close the polygon.

Floris
  • 45,857
  • 6
  • 70
  • 122
  • Thanks. The sort command was intentional to make my point. Just imagine you have (n1,n2), the goal is to arrange the points such that you will have a polygon. The polygon can be convex or concave. the application that I am looking at is for complex coastlines with multiple island. – mikeP Oct 04 '13 at 13:36
  • 1
    I see - you are saying "given a series of points that are not in the right order, how would I re-order them". That is a more tricky problem. The question really becomes - how do you know which two points you want to connect - are they always "point B is connected to A and C that are the two closest"? That doesn't cover unequally spaced points where both "closest" points are on the same side. "Two closest points that are at least 120 degrees apart"? Give it some thought and update your question to reflect what you are _really_ asking... this kind of back-and-forth is essential. – Floris Oct 04 '13 at 14:21
  • @mikeP, it would be good if you could update your question so to make clear the sort is intentional, just in order to generate points out of order. Or maybe a randperm would be even better. – A. Donda Oct 04 '13 at 14:35
1

You could use convhull. If the given points actually define the edges of a regular polygon, or another convex shape, then all of them should be contained in the convex hull. The function returns indices to the points in an order that is suitable for plotting.

Continuing your example,

k = convhull(n1, n2);
plot(n1(k), n2(k))

recovers your original circle.

A. Donda
  • 8,381
  • 2
  • 20
  • 49
  • 1
    Unfortunately "the polygon can be convex or concave", according to the comment @mikeP posted under my initial answer... but this is a great "first part of the answer", and I'm upvoting it as such. – Floris Oct 04 '13 at 14:49
  • Didn't notice that. I updated my answer to say "regular polygon". Well, I believe then the poster's question is not sufficiently well defined. There are many ways to make a polygon out of a set of points. – A. Donda Oct 04 '13 at 14:53
  • I agree - I made that point in a comment earlier. I edited the question to reflect my current understanding, but some additional information is needed. I think the fact that "these are points on the coastline" gives some sensible constraints - points that are connected are "close in distance and on a reasonable curve". But it cannot lead to a unique solution. – Floris Oct 04 '13 at 14:55
  • Thanks @Floris for updating the question. A. Donda's solution works well if you consider only one polygon (one island in my case). The complexity comes in when trying to find a generalized solution for multiple polygons close to each other. The arrangement of points are so messed up that one point in a polygon is listed next to another point in another polygon, and so on... A more suitable question at this point is probably hos to separate each polygon? Once the polygons are separated, I can apply A. Donda's solution, and just merge the "arranged" points later on. – mikeP Oct 04 '13 at 15:15
  • @mikeP - it sounds like you have another question here: how to "cluster" points that belong to different islands. I am guessing that the typical distance between points that "belong to the same group" is smaller than the distance "from one group to another". In that case there are techniques you can use to classify points. I think it should be subject to a separate question. Formulate it, post it, and give a link here. – Floris Oct 04 '13 at 15:19
  • 1
    If you start to search for "clustering algorithms" combined with key words like "distance", you will find many starting points. I suggest you study those, attempt their methods, post your attempt and results - the chances of getting help solving the underlying problem will then be quite good. – Floris Oct 04 '13 at 15:23
  • @mikeP: If the coastlines are finely sampled and the islands are well separated, my guess is that nearest-neighbor aka single-linkage clustering would be appropriate to find the islands. Then you could use the convhull approach outlined above to find the right ordering of points for each island separately – provided the islands have convex shapes. – A. Donda Oct 05 '13 at 13:37