4
$\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?

$\endgroup$
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.

$\endgroup$
  • $\begingroup$ Yes all the points are already on the hull boundary. I've corrected the question. $\endgroup$ – tmaric Jul 11 '12 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 Jul 11 '12 at 14:49
  • $\begingroup$ @tomislav-maric: And I corrected my answer; one can indeed take advantage of the given assumption. $\endgroup$ – Arnold Neumaier Jul 11 '12 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.

$\endgroup$
  • $\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 Jul 11 '12 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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