Register or Login to browse without ads

Tue 2 Sep 2014 - 6:47 pm UTC

Home | Ask a Question | Browse Questions

CANCELLED

Question: For Mathtalk: Sort points in clockwise order

Please carefully read the Disclaimer and Terms & conditions.
Priced at $40.00

Actions: Add Comment

Fri 5 Aug 2011 - 9:40 am UTC

Question

j_philipp
Customer

Hi Mathtalk! I'm in need of some pseudocode again, preferably Lua-style, but it doesn't need to compile or be syntactically valid!

Function receives: An array of points
Function returns: An array with these points, but sorted in clockwise order around the points' approximate center
My goal: Pass the sorted points to a polygon drawing function so that they form a convex hull

E.g. take the following "nonsense code", just to give you a rough idea of the Lua syntax for stepping through an array etc.:

function getClockwiseSortedPoints(points)
    local pointsSorted = {}

    for i = 1, #points do
        local p = points[i]
        -- all nonsense
        if p.x == foo and p.y == foobar then
            pointsSorted[#pointsSorted + 1] = { x = barfoo, y = foobar }
        end
    end

    return pointsSorted
end

Visually speaking, probably first we'd need to find the center point of the clock, then probably the hand of the clock would start moving at e.g. 12:00 o' clock once around the clock, and whichever point it collides with, will be the next point of our sorted array. For what it's worth, we're dealing with 3 to 10 integers, with values in the range of 0 to 1024 maximum. Not sure if these links are relevant, they might describe a different issue, I haven't looked at it in-depth:
http://en.wikipedia.org/wiki/Graham_scan
http://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order

Thanks!!

 
 

Fri 5 Aug 2011 - 12:00 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

Yes, that is an interesting problem.  If the points are all on the convex hull, then the sort order is unambiguous.  What do you want if one or more points are inside the convex hull?  You may still be able to find a "center" from which the clockwise order is well-defined; this is a "star-shaped" rather than a strictly convex figure.

regards, mt

 

Fri 5 Aug 2011 - 12:25 pm UTC

Question clarification

j_philipp
Customer

Any shape is OK, as long as I can create a polygon out of it. Stars are fine too. Just no complete chaotic overlapping, if you know what I mean... Here's a little illustration: http://i.imgur.com/Cy5n1.png

 

Wed 10 Aug 2011 - 9:51 am UTC

Uclue Researcher Comment

Roger Browne
Researcher

I think Philipp's requirements are not too complicated. Given a list of points, we calculate an arbitrary center point by taking the mean of the x co-ordinates and the mean of the y co-ordinates.

We use this point as the new origin. After translating the co-ordinates of all points to be relative to this new origin, we convert each point from cartesian to polar co-ordinates, then sort them by theta. Any points that happen to be located at the new origin are arbitrarily placed at the end of the list.

 

Wed 10 Aug 2011 - 12:54 pm UTC

Question clarification

j_philipp
Customer

Just came here to say that I might have the answer now courtesy of Stackoverflow (http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order ). In fact one of the two answers are just what Roger just suggested. It might be best to not answer the question while I try this approach out, so I'd like to put a Pause on it (and likely Cancel if Stackoverflow's answer works). Thanks in any case, this one was a bit time-critical as it's for a current project!

 

Wed 10 Aug 2011 - 2:58 pm UTC

Question clarification

j_philipp
Customer

I wasn't able to get the polar approach to work at the moment but Ciamej's answer at Stackoverflow works perfect for now. Thanks all!

 

Wed 10 Aug 2011 - 2:58 pm UTC

Cancelled

j_philipp
Customer

(Thanks, but after some days I posted at Stackoverflow and got an answer there. Till next time)

 

Wed 10 Aug 2011 - 3:00 pm UTC

Uclue Admin Comment

We're glad your problem is solved, Philipp.

 

Wed 10 Aug 2011 - 5:32 pm UTC

Uclue Researcher Comment

mathtalk
Researcher

Indeed!  I saw a couple of quick responses to your post at Stackoverflow and waited to see if you'd find them satisfactory.

Here are some thoughts.  We will assume for simplicity that all the points are distinct, since that seems general enough.  Let's begin with the task of ordering the points once a center is chosen, and then back into the ways one might go about choosing a center.

ciamej points out that we can preserve the integerness of data and avoid introducing fractional values by comparing slopes with cross-multiplication. 

Given a "center" point (x0,y0), we would split the list into points to the left (X < x0) and points to the right (X > x0) of that center. 

If there are points which have the same x-coordinate as the center, those above the center (Y > y0) will be grouped at the end of those on the left, and those below the center (Y < y0) at the end of those on the right.

If there is a point with both coordinates the same as the center, that is a special case discussed in greater detail below.

Clockwise around the polygon means decreasing slopes (between the center and the "peripheral" points) for the points on the left, and increasing slopes for the points on the right.

To determine which of two points (A.x,A,y) and (B.x,B.y) has a greater slope with the center we can check this integer-only condition:

(A.y - y0)*(B.x - x0) > (B.y - y0)*(A.x - x0)

which says A makes a greater slope than B does.

For points with x-coordinate x0 (see above), those above the center should get sorted with the left hand points by putting them at the end in order of their y-coordinates (distance from the center), and those below the center should get sorted with the right hand points by putting them at the end also in order of their y-coordinates.

The final order of the vertices can be obtained by concatenating the sorted points on the left with the sorted points on the right.

As to a method of sorting, I would have suggested straight insertion sort because it's easy to code and have very respectable speed for the number of points being managed in this application (3 to 10 vertices).

Two issues can arise, neither fatal.  First, what if two or more vertices (on the same side of the center) give the same slope with the center?  It would not be a problem for just two points that give the same slope to place them in either order.  However if we have three or more points with equal slope on the same side of the center, they should be ordered consistently in respect of distance to the center (but it can be either nearest to farthest or vice versa).  Note this is consistent with how we proposed to treat points lying directly above or below the center.

Second, what if the center coincides with one of the peripheral points?  The "slope" is then undefined.  However this is not an insurmountable problem.  The polygon could be drawn with the center point inserted at any place in the (otherwise clockwise) ordering.  Since this reduces the number of points to sort by one, there's actually a bit of an advantage if it happens that way.

That gives us a framework to consider the initial task of choosing a center.  If the center is chosen to have a different x-coordinate than any of the vertices, then the special logic outlined above for treating those points can be omitted.

The simplest choice of a center, from a programming standpoint, is perhaps to call the bounding box method on the collection of points and use the center of the bounding box.

Another choice, as Roger and ciamej suggest, would be to take the average of all points, perhaps rounding to get integer coordinates for that as center.

Although the choice of center certainly can affect the ordering of points in the non-convex case, it doesn't seem to be a crucial choice in that nearby choices of center give the same ordering for all but those  peripheral points very close to the center.

Perhaps the most aesthetic choice is one which minimizes the length of the polyline, i.e. the shortest perimeter that can be formed.  Finding the exact shortest perimeter is probably hard and not worth the special effort.  But we might take it as a guide to handling one special case, the case when the "center" is one of our vertices. 

As noted above, the center doesn't have a slope with itself, but it could be inserted anywhere in the rotation/vertex ordering.  A linear search through the otherwise finalized ordering would determine where inserting this center point would increase the perimeter by a minimal amount.

Finally there's an approach that reduces the amount of work need to compare points in the sorting, eliminating the cross-multiplication needed for a strictly clockwise order, but doing a little more work in separating out the "lefthand" and "righthand" points.  The result is not necessarily a star-shaped region but still avoids any edge crossings.

Pick the two points with maximum and minimum y-coordinates, and consider the line L drawn between them.  This line separates the plane into two regions, and thus apart from other points that may fall on that line, separates the vertices into those to the left of L and those to the right of L.

Now order the points to the left of L by ascending y-coordinates, followed by those to the right of L by descending y-coordinates.  Hence the polyline will proceed upward from the point having minimum y-coordinate through the vertices on the left of L until the point with maximum y-coordinate is reached, then fall downward through the vertices on the right of L until returning to the point having minimum y-coordinate.

[A similar approach could be taken using a line between points having minimum and maximum x-coordinates.]

 

Actions: Add Comment

 

Frequently Asked Questions | Terms & Conditions | Disclaimer | Privacy Policy | Contact Us | Spread the word!

© 2014 Uclue Ltd