9

I have the same problem as here: how to order vertices in a simple, non-convex polygon but there is no solutions I can use.

I have coordinates of points and need to find some polygon. Does not matter that there is more solutions for one list of dots. I need some algorithm to find one of them. Does not matter which one. I really don't know how to solve this.

(I have stored coordinates in array and I want to use some algorithm in Javascript)

Thanks a lot.

Community
  • 1
  • 1
1daemon1
  • 1,001
  • 3
  • 11
  • 29
  • 1
    Are you restricted to simple polygons? Otherwise you can connect the vertices as you wish. They will always form a polygon. – Nico Schertler Oct 31 '13 at 18:27
  • There is an O(n^2) algorithm: for every permutation of the points, construct a polygon and see if it's a simple non-convex polygon. Granted, this will take some time if you have a lot of points. How many points do you have? – Jim Mischel Oct 31 '13 at 18:37
  • 1
    Thanks for comments. Answer below is appropriate for me and it describes my situation so it is solved. – 1daemon1 Nov 01 '13 at 17:43

1 Answers1

18

First, find the center of the bounding box that contains all of your vertices. We'll call this point C.

Sort your list of vertices based on each point's angle with respect to C. You can use atan2(point.y - C.y, point.x - C.x) to find the angle. If two or more vertices have the same angle, the one closer to C should come first.

Then, draw your points in the order they appear in the list. You will end up with a starburst pattern that is non-intersecting and probably non-convex. Example:

100 points randomly placed on a 400x400 pixel square

Kevin
  • 74,910
  • 12
  • 133
  • 166
  • @Clay, forming a polyhedron in the shape of a spiky ball should be possible, although I don't know how you would decide which points should share an edge. The ordering idea works in two dimensions because each point has only two adjacent neighbors, one in either rotational direction; but in three dimensions, a point can have multiple neighbors. So just ordering your points no longer gives a complete list of line segments. – Kevin Apr 07 '14 at 12:12
  • @Kevin I see, well, I'd like to start at a simpler case. Say I am given 5 vertices in 3d space. Is it possible to order them in a consistent clockwise or anticlockwise direction so as it forms a polygon? – Ogen Apr 07 '14 at 12:21
  • Nope. Even if you give a definition of "clockwise" that makes sense in three dimensions, you won't get enough edges to form a full polygon. Even a simple tetrahedron needs six edges, and this method would only give four. It only gets worse as the number of vertices increases. – Kevin Apr 07 '14 at 12:48
  • @Kevin I don't get it. I have an assignment for a graphics course and its asking me to organise 5 vertices in 3d space in a clockwise direction in order to calculate the normal to the resulting polygon's surface. I have no idea how to do it. – Ogen Apr 07 '14 at 12:57
  • Oops, I thought you wanted a polyhedron, not a polygon. If all five of your points are [coplanar](http://en.wikipedia.org/wiki/Coplanar), then it's easy to find the polygon's normal. Choose three points A, B, and C from among your five that aren't [collinear](http://en.wikipedia.org/wiki/Collinear). Find vectors AB and BC, and their [cross-product](http://en.wikipedia.org/wiki/Cross_product) will be the polygon's normal vector. I don't know what the whole "clockwise direction" thing is about. – Kevin Apr 07 '14 at 13:11
  • This works well for convex shapes where the centroid is not also a point in the polygon. I ended up using this, which doesn't require trig: http://stackoverflow.com/a/6989383/549848 – Aram Kocharyan Sep 23 '14 at 02:32