Click here to Skip to main content
15,883,705 members
Please Sign up or sign in to vote.
5.00/5 (1 vote)
Suppose random points P1 to P20 scattered in a plane. Then is there any way to sort those points in clock-wise.
See image Here.
Here we can’t use degree because you can see from the image many points can have same degree. E.g, here P4,P5 and P13 acquire the same degree.
Posted
Updated 1-Feb-11 0:22am
v3

Hi,

The polygon you have shown in the picture is a concave polygon, which usually little difficult to sort, however the one you have shown is somewhat easy. Find the centroid of this polygon from the given points and from the centroid trace with increase in angle. From the centroid if two points are in same angle, better keep one point out of that is enough :) otherwise it will give more trouble than a good sort. One another thing to look at after sorting, the path should not intersect themselves.

However the polygon points not sortable without clues, because there many possible polygons from a set of points :(

If a convex polygon use the convex hull algorithm
 
Share this answer
 
v2
Comments
Sergey Alexandrovich Kryukov 14-Mar-11 16:08pm    
You're basically right. The problem is ill-posed. However, the picture suggests the ordering you're thinking about will not work. The assumed criterion is something like going to the closest point. The problem is very difficult. My 4 for your answer.
--SA
Strictly sort on degree, if equal on x, if equal on y (or radius instead of x,y but will be longer)
 
Share this answer
 
Comments
Pritesh Aryan 1-Feb-11 6:27am    
if equal on x, if equal on y Then?
jean Davy 1-Feb-11 6:58am    
Hey, you are a student ? And you want I do your exercise ! :mad:
Ok, I do it, this is THE C++ response:

<pre>
template<>
struct std::less< CPoint >
{ // functor for operator<
bool operator()(const CPoint& _Left, const CPoint& _Right) const
{ // apply operator< to operands
if( _Left.x < _Right.x )
return true;
if( _Left.y < _Right.y )
return true;
return false ;
}
};


....

CPoint Pts[]={
CPoint( 1, 2),
CPoint( 3, 4),
CPoint( 3, 4)
};
std::set< CPoint > Set( Pts, Pts + _countof( Pts ) );
</pre>
Easy to improve with angle before x,y...
Sergey Alexandrovich Kryukov 1-Feb-11 13:50pm    
I did not check up, probably your implementation works. I voted 5 anyway.

The problem may way be less trivial than that (I don't think OP realized that, even less likely could formulate correctly).

Notice that chain structure in data? The more complex problem which really make sense is to link close points in a chain, detect if partial or complete order can be applied (it any) and then, if possible, all point should be referenced in certain order along the chain.

How about that?
--SA
jean Davy 1-Feb-11 14:17pm    
Yes, of course sorting point is like "put the finger in a gear", you know when it starts, not when it ends...
In fact I did that for pedagogy, as if he reads documentation on set container, a whole world will open before him ! Gloria, Gloria ...
So you want to sort clockwise, but in the event that some points have the same angle from the start point (Wherever 0 degrees points) then you want to sort by what? Closest point to the center?

Either way, they're just vectors so you can find the magnitude and angle and use both to sort the points however you like.

class Vector2
{
public:
  Vector2(double _X, double _Y)
  {
    X = _X; Y = _Y;
  }

  double LengthSquared()
  {
    return (X*X + Y*Y);
  }

  double Length()
  {
    return sqrt(X*X + Y*Y);
  }

  double AngleWith(const Vector2& other)
  {
    double val = (X*other.X + Y*other.Y)/(GetLength()*other.GetLength());
    return acos(val);
  }

  double X;
  double Y
}


A very simple vector class for you there, bear in mind that when you get the angle between two vectors that the result will always be 180 degrees or less because it will always return the smallest angle so you will need to take that into consideration.

EDIT: Gosh darn it, replying to a question from over two weeks ago. [Note to self: Check date of question before answering, even if its at the top of QA]
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900