8

I am getting a List of Points from the user clicking on the screen.

And I want to draw a polygon based on this points. The problem is that the user might not be clicking in the right order (no intersecting segments) to form a correct polygon, therefor I'm looking for a code snippet which would sort that List and arrange the points in the right order to form a good polygon...

Thanks!

picture = BAD POLY!

enter image description here

-

picture = GOOD POLY!

enter image description here

Roger
  • 6,443
  • 20
  • 61
  • 88
  • 3
    I think you'll need to define "the right order" for us to be able to answer this a little better. – Tim May 18 '11 at 19:36
  • 1
    @Tim, a "right order" seems to be one without intersecting line segments. – Anthony Pegram May 18 '11 at 19:37
  • you'll need to look at this similar question: http://stackoverflow.com/questions/5576017/polygon-drawing – John Gardner May 18 '11 at 19:38
  • What do you exactly mean with "good poly"? Is it a convex poly? If not - there are a lot of "right" polygons for the same set of points. – oxilumin May 18 '11 at 19:38
  • btw, that shape above is a perfectly reasonable polygon, its just a *complex* polygon, where i think you're thinking of a *simple* polygon. – John Gardner May 18 '11 at 19:39
  • @Anthony Pegram - I assumed so, but even at that point, is there a requirement for going around the circle clockwise or counter-clockwise? It's not clear. – Tim May 18 '11 at 19:40
  • 1
    Sorry for the misunderstanding, a GOOD POLY, as Anthony said, is one without intersecting line segments. – Roger May 18 '11 at 19:40
  • @Roger: If one of the points falls within, but not on, the convex hull of the overall set of points, it will be possible to connect that point "between" any two adjacent points on the convex hull without the polygon intersecting itself. If multiple points are within, but not on, the convex hull, there will be even more possible ways to draw the polygon. – supercat May 18 '11 at 20:13

4 Answers4

6

If you want to "wrap" the points in a polygon, you can use any number convex hull finding algorithms.

dlev
  • 48,024
  • 5
  • 125
  • 132
  • yes, i saw this on in AForge libraries, but still wouldn't it be easier to somehow sort the list? – Roger May 18 '11 at 19:44
  • 1
    exept that the list is two dimensional, so you'd have to "sort" doing some kind of clockwise or counter clockwise thing from a central point. which only works if you have a picture like above. what happens if the person clicks a point near the middle? That's why algorithms like convex/concave hull exist, this problem isn't as simple as you think it is. – John Gardner May 18 '11 at 19:46
  • Sorting is often(always?) involved in a convex hull algorithm. – Captain Giraffe May 18 '11 at 19:46
  • You could, as long as you could state what it meant for the points to be "sorted", not a trivial task. – dlev May 18 '11 at 19:48
  • yep, thanks, I'll use the convex hull algorithm from AForge then. ;) – Roger May 18 '11 at 19:51
  • 1
    @Roger Cool. Keep in mind that neither convex (nor concave, for that matter) hull is perfect. Some internal points may be discarded in either case. Make sure it's clear to users what will happen when they try to draw something "inappropriate". – dlev May 18 '11 at 19:53
3

Dude i had the same problem, but i found a code that helped me. I think this resolve your problem .

See this link: http://jsfiddle.net/9DHSf/3/

Vinicius
  • 31
  • 1
2

You could take the centroid of all the points, then taking the dot product of each point to the centre with a reference point (say the first in the list) to the centre, get the angle of each point in your list from an arbitrary reference vector. Then order that list on the angle. That'll give you the points in a (eg) clockwise winding order, so your line is just p1 -> p2, p2 -> p3 etc...

RichK
  • 11,318
  • 6
  • 35
  • 49
1

If you want to find the "concave" hull (i.e., counter-clockwise sort the points around a centroid), you might try:

import matplotlib.pyplot as plt
import numpy as np

# List of coords
coords = np.array([7,7, 5, 0, 0, 0, 5, 10, 10, 0, 0, 5, 10, 5, 0, 10, 10, 10]).reshape(-1, 2)
centroid = np.mean(coords, axis=0)
sorted_coords = coords[np.argsort(np.arctan2(coords[:, 1] - centroid[1], coords[:, 0] - centroid[0])), :]

plt.scatter(coords[:,0],coords[:,1])
plt.plot(coords[:,0],coords[:,1])
plt.plot(sorted_coords[:,0],sorted_coords[:,1])
plt.show()

enter image description here

Tahlor
  • 1,642
  • 1
  • 17
  • 21