moBmo's blog

Clockwise cordinates

By moBmo, 10 years ago, In English

Hello . Today I was thinking about a problem .I want your help.

We have number N and then N lines containing two numbers the cordinate of each point . The task is to print the cordinates of the points in clockwise order . I'm really interested to know what the algorithm is.

Tags cl, co
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
10 years ago, # |
  Vote: I like it -19 Vote: I do not like it

If your points form a "Convex Hull" , or your targets points are the ones form a Convex Hull, I have a solution.

Convex Hull points needs to be clockwise.

The Topcoder Algorithm Tutorials about Geometry Part2 have introduce an algorithm to find Convex Hull, It is O(N2) , Use This Link to figure out : Geometry — Section 2: Line Intersection and its Applications

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sorry, but "solving" well-known angle-sort with such kind of assumption, which we clearly won't have and stating that Convex Hull algorithms work in O(n2) just needs to be downvoted xD.

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What do you mean by clockwise order? Clockwise order according to what "center" of the clock. If you mean clockwise to point (0,0) then you could simply do "sorting by angle". Suppose you have a point A and the origin (0,0) is O. Then you just have to sort increasingly by the angle formed between the positive Y-axis and OA (of course, allowing angles to be larger than 180 degrees), then the points will be sorted "clockwise" to the origin. It takes O(NlogN) as you can compute the angles constantly per point with some maths and the sorting algorithm takes O(NlogN)

If you want to pick the "center" of the clock to be some other point, you could do the same but move the center of the coordinate system to that point.

I hope I understood your question correctly, excuse me and correct me if I didn't :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually calculating the angles is not the best idea. One should avoid double numbers and use binary predicate "left turn".

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well yes, that would be fine too, I used angles to explain the idea. You can use cross product for determining "left turns" and it will probably be more comfortable than calculating angles.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But maybe there are two points A and B such that tha angle that OA makes with Y axis is the same as OB . Then how should we know which quadrant are each of them in ?

    I think first we can do this and then calculate Cos(x) and Cos(y) the angles ......

    But in the case you said if we are allowed to use angles bigger than 180 degree how should we do this ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Well I'm not sure exactly what you mean. If you have a way of calculating only the smaller angle, then you could simply go like "if X of the point is negative, then the angle is 360-smaller_angle" and else, it's just the smaller angle. This way you allow calculation of angles larger than 180 degrees. Example:

      You could still use the "left turn" technique if you don't like angles.

      Note: We calculate the angles between OA and the positive Y axis

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Btw in algo it is much more natural to sort points in a counterclockwise order, not clockwise (because math tells to do so). Of course it is just an agreement, and if you really want to, you can sort them in a clockwise order, but it is better to have good habits.

→ Reply