C++

Forum

 
Sorting 2D points clockwise

game (28)

Dear all,

I badly seek your help, as i expect several hours to solve!

I have 2D points written in {x1, y1, x2, y2, x3, y3, .....}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {

	vector<double> vec;
	vector<double> vec_ordered;


	vec.push_back(1);
	vec.push_back(1);

	vec.push_back(2);
	vec.push_back(2);

	vec.push_back(3);
	vec.push_back(3);

	vec.push_back(4);
	vec.push_back(4);

	vec.push_back(5);
	vec.push_back(5);

	vec.push_back(6);
	vec.push_back(4);

	vec.push_back(6);
	vec.push_back(3);

	vec.push_back(6);
	vec.push_back(2);

	vec.push_back(6);
	vec.push_back(1);

	vec.push_back(4);
	vec.push_back(1);

	vec.push_back(3);
	vec.push_back(1);

	vec.push_back(2);
	vec.push_back(1);

	vec.push_back(5);
	vec.push_back(1);


	int num =vec.size();
	for (int i=0; i<num; i=i+2)
	{
		//cout<<vec[i]<<" "<<vec[i+1]<<endl;
	}

      // reordering based on x values
       for(int i=0; i<num; i=i+2)
          {
	 for (int i=0; i<num; i=i+2)
		{

			if (vec[i]<vec[i+2])
			{
				double t1=vec[i];
				double t2=vec[i+1];

				vec[i]=vec[i+2];
				vec[i+1]=vec[i+3];

				vec[i+2]=t1;
				vec[i+3]=t2;
			}
		}

}

//Determination of nearest point
double q1, q2;
double distance;
for (int i=0; i<num; i=i+2)
	{
	double temp = 999999999999999999999999990.0;


	for (int j=i; j<num-2; j=j+2)

	{

	distance = sqrt((vec[i]-vec[j+2])*(vec[i]-vec[j+2])+(vec[i+1]-vec[j+3])*(vec[i+1]-vec[j+3]));

	cout<<j<<" ("<<vec[i]<<", "<<vec[i+1]<<") ("<<vec[j+2]<<", "<<vec[j+3]<<")  -> "<<distance<<endl;

		if (distance<temp)
		{
			temp=distance;
			q1=vec[j+2];
			q2=vec[j+3];

		}
if ((vec[i]!=q1) || (vec[i+1]!=q2))
			{
			vec[i]=q1;
			vec[i+1]=q2;
			}

	vec_ordered.push_back(q1);
	vec_ordered.push_back(q2);
	cout<<"->"<<q1<<" "<<q2<<endl;
}
	}



Result.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
6 4
6 3
6 2
6 1
5 5
5 1
4 4
4 1
3 3
3 1
2 2
2 1
1 1


which wrong result

I wanted to make

1
2
3
4
5
6
7
8
9
10
11
12
 
6 3
6 2
6 1
5 1
4 1
3 1
2 1
1 1
2 2
3 3
4 4
5 5



Could you help me,, waiting your response........
mik2718 (347)
When working with vectors (e.g. 2D vectors) it is good to use a vector class.
Writing one is useful C++ practice but there are classes available

I have assumed you have such a class, Vec2

Here are some code fragments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// utility class storing vector and associated angle
class VecAndAngle
{
public:
  Vec2 v;
  double angle;
  VecAndAngle(const Vec2& setv,double seta)
    : v(setv) angle(seta) { }
  int operator<(const VecAndAngle& other)
    { return(angle < other.angle); }
};

// calculate median vector (centre of shape)
Vec2 median(0.0,0.0);
for(i=0;i<numvecs;++i)
  median += v[i];
median /= numvecs;

// create sortstore of vectors plus angles, sort
vector VecAndAngle sortstore;
for(i=0;i<numvecs;++i)
  sortstore.push_back(v[i],atan2((v[i]-median).y,(v[i]-median).x));
sort(sortstore.begin(),sortstore.end());

// decant into ordered vector store
vector<Vec2> ordered;
for(i=0;i<numvecs;++i)
  ordered.push_back(sortstore[i].v);




Duthomhas (13212)
I don't entirely agree with answer, but the basic point is close to correct.

You need a "point" class:

1
2
3
4
5
6
7
 
struct point
  {
  double x;
  double y;
  point(): x( 0.0 ), y( 0.0 ) { }
  point( double x, double y ): x( x ), y( y ) { }
  };

This lets you store your points as individual things:

1
2
3
4
5
6
 
  vector <point> points;

  points.push_back( point( 1, 1 ) );
  points.push_back( point( 2, 2 ) );
  ...
  points.push_back( point( 5, 1 ) );


Now for the sorting. You wish to "[sort] 2D points clockwise". If that means what I think it means, then I assume you have a list of points like the following:

          ^ y
          |
          |   *
          |
   *      |
          |    *
----------+----------> x
        * |
          |
          |
          |
          |

When sorted, they will be ordered like the following:

          ^ y = 12 o'clock
          |
          |   *p1
    p4    |
   *      |
          |    *p2
----------+----------> x
        * |
        p3|
          |
          |
          |

In order to do this, you must compare the angles that each point is from 12 o'clock:

          ^ y   /
          |    /
          |   *p1
    p4    |  /
   *      |a/
          |/   *p2
----------+----------> x
        * |
        p3|
          |
          |
          |

This requires some basic trigonometry, specifically, using the tangent formula:

           opposite = x
  tan a = --------------
           adjacent = y

Since you know x and y, you can rewrite using the arctangent. Amazingly enough, C and C++ have a two-argument arctangent function in <cmath>:
http://www.cplusplus.com/reference/cmath/atan2/

Remember, the angle is measured from 12:00, so we've switched the y and x.
Call atan() with atan( p.x, p.y ).

Remember also that atan() has limitations, so you must write your code to account for the quadrant of your point.

Again, the most difficult thing will be remembering that by requiring it to be "clockwise" you have changed from the standard cartesian system to a custom one -- meaning that you must convert between the custom and standard when using the standard math functions.

When you compile, you will also have to link in the standard C math library.

I recommend you write yourself a function that takes a point and returns the clockwise angle from 12:

1
2
3
4
5
6
7
 
double clockwise_angle_of( const point& p )
  {
  // (1) figure out point's quadrant
  // (2) call atan() properly for the quadrant to get the angle
  // (3) add the appropriate pi/2 value (one of 0, pi/2, pi, 3pi/2, depending on the quadrant) to the angle
  // (4) return the angle
  }


So when you finally figure that out (good luck!), then you can sort. As you don't have too many points, you might as well just calculate the angles in your sort function's comparison function.

1
2
3
4
 
bool clockwise_compare_points( const point& a, const point& b )
  {
  return clockwise_angle_of( a ) < clockwise_angle_of( b );
  }

Sorting the list of points then becomes simply:

 
 
  std::sort( points.begin(), points.end(), clockwise_compare_points );

And displaying the result:

1
2
 
  for (size_t n = 0; n < points.size(); n++)
    cout << "(" << points[n].x << "," << points[n].y << ")\n";

Hope this helps.
game (28)
Dear mik2718, and Duoas;

Thank you for your nice explanation and help

I tried the angle method before, it perfectly work for some examples. In my case i need to check my program with different examples. For instance the following 2D points ( the stars are my 2D points)

                 *  *  * * * *    *     *     *
                 *
                 * *  * * *
                              *                      *
                            *
                         *
                    *
                 *                                  *
              *
               *
                        *    *    *  *          *


Because of this limitation of angle methods. I try to implement shortest distance method which could find the minimum shortest distance and which ofcourse able to find the nearest point, and update the vector (remove the vector for the interation so that it will not be repeated. I couldn't put this idea to Code!!!!!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
  // num is size of vector
for (int i=0; i<num; i=i+2)
	{
	double temp = 999999999999999999999999990.0;


	for (int j=i; j<num-2; j=j+2)

	{

	distance = sqrt((vec[i]-vec[j+2])*(vec[i]-vec[j+2])+(vec[i+1]-vec[j+3])*(vec[i+1]-vec[j+3])); // searching minimum distance between point x1, y1 and (xj, yj)

		if (distance<temp)
		{
			temp=distance;
			q1=vec[j+2];
			q2=vec[j+3];
                   // I could find the nearest point to my starting point x1 and y1
		}


}

My difficulty here is to take q1 and q2 as the next point rather than i=1 (next loop) and to delete q1 and q2 from my vector list (from vec)


Hope you got my difficulty!!

Thank you in advance

Regards
Duthomhas (13212)
Are you trying to connect the dots or something?

If you can guarantee that the next point will always be the closest, then your idea is fine, but it will be a bit of work. I recommend a function to return an iterator to the closest element of a vector to an argument point.

And you really should put your points in a point class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
double distance( const point& a, const point& b )
  {
  return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) );
  }

template <typename Iterator>
Iterator closest_point( const point& p, Iterator begin, Iterator end )
  {
  double d = 0;
  Iterator result = begin;
  while (begin != end)
    {
    double d2 = distance( p, *begin );
    if (d2 < d)
      {
      d = d2;
      result = begin;
      }
    }
  return result;
  }

Now you can have code to pull out points by distance:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
  // Begin with the first point
  point p = points[ 0 ];
  points.erase( points.begin() );

  while (points.size())
    {
    // Find next point (the one closest to p)
    vector <point> ::iterator it = closest_point( p, points.begin(), points.end() );
    // Draw the line between p and the closest to it (or whatever you intend to do)
    draw( p, *it );
    // Our new p is the point we just found
    p = *it;
    // Remove the point we just found from the vector of points
    points.erase( it );
    }

You can easily adapt this code to work with your current list, but life would be so much cleaner and easier for you if you put your points in a list (vector) of points (some struct).

Hope this helps.
game (28)


Thank you very much this works !"!!!!!!!!!!!!!
Disch (13742)
FWIW... if you just need to compare relative distance... you can remove the sqrt() call as an optimization. (if a < b... then a*a will be < b*b)

Duoas's example slightly modified (3 changed lines marked):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
double distance_squared( const point& a, const point& b )  //<-
  {
  return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y); // <- 
  }

template <typename Iterator>
Iterator closest_point( const point& p, Iterator begin, Iterator end )
  {
  double d = 0;
  Iterator result = begin;
  while (begin != end)
    {
    double d2 = distance_squared( p, *begin );  //<- 
    if (d2 < d)
      {
      d = d2;
      result = begin;
      }
    }
  return result;
  }




Of course... this is unnecessary for what you're doing, as the performance cost of calling sqrt is inconsequential to you. I just felt like throwing this out there.
Topic archived. No new replies allowed.