5
$\begingroup$

I'm dealing with a set of points which are already placed on the 2D hull boundary: a convex polygon. I know this for sure. However, the point set is not ordered, and I need the polygon points to be ordered counter-clockwise.

I'm aware of all the 2D algorithms for convex hull generation from the books/literature, but I'm interested if there is a faster, specialized, algorithm for this special case?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

Take the mean of all your points as origin and transform to polar coordinates. This gives the desired ordering in $O(n\log n)$ operations.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes all the points are already on the hull boundary. I've corrected the question. $\endgroup$
    – tmaric
    Commented Jul 11, 2012 at 14:45
  • $\begingroup$ If the points are on the hull, isn't the right way to go to skip all the processing pertained to interior point elimination from standard hull algorithms, and sort the points with respect to say angle defined by the centrepoint of the hull (e.g. incremental sort)? $\endgroup$
    – tmaric
    Commented Jul 11, 2012 at 14:49
  • $\begingroup$ @tomislav-maric: And I corrected my answer; one can indeed take advantage of the given assumption. $\endgroup$
    – Arnold Neumaier
    Commented Jul 11, 2012 at 14:53
2
$\begingroup$

Since the points are in 2D, you can use Graham's Scan to order the points instead of a sorting algorithm. This will also give you a $\Theta(nlog(n))$ complexity without the need for any transformations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Grahams scan involves searching for interior points, and sorting with respect to angle; the transformation to polar coordinates is basically the angle based search in 2D... $\endgroup$
    – tmaric
    Commented Jul 11, 2012 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.