C ++ - Sorting particular points of a rectangle in a vector?

4

I have a project in c ++ where I should map regions of an image using the mouse click. The issue is that I need to get the mapping points in a specific storage order, as in the image below:

My problem starts at the moment of storing this data, because I created the following vector to store such points: pfileira = {P1, P2, P3, P4}. The problem is that by clicking on the image and get the points, I can only store them in the click order, ie if I start mapping by the point P3 for example, the vector will be stored as: pfileira = {P3, P2, P1 , P4} or = {P3, P4, P1, P2}. Is there any theorem I can use to sort my storage vector in order to get the sequence of points in the order = {P1, P2, P3, P4} in my point vector being selected from any point? I tried varying shapes using up to a numeric value of the module of each point, but it does not work for all cases. Would anyone help me with this problem if there is a solution? Thanks in advance.

    
asked by anonymous 19.08.2016 / 06:27

1 answer

6

The solution to your problem is very simple. The basic algorithm is as follows:

  • Given the vertices of the polygon, calculate the midpoint (center of the polygon). For this, it is enough to make, for each component of coordinates (that is, for ox and then for oy) the sum of the values of the components in each vertex and divide by 4 (since they are only 4 vertices). >

  • Given the central point, calculate the vectors from that central point to Each vertex (see the referenced reference. They are not vectors in the sense of matrices in programming, but vectors in space, with direction, direction and magnitude). The vector is important to obtain the direction in which the vertex is "around the polygon".

  • For each vector, calculate the slope angle between that vector and the horizontal axis. To do this, use the arc-tangent of the value of y in relation to the value of x (the idea is a simplification of the calculation of the angle between vectors; to find out more, see this reference ). Keep these angles.

  • Finally, sort the list of points based on the value of your angle. As in most computer systems the coordinates start in the upper left corner (that is, the 0,0 coordinate is at the top left, with x growing to the right and y growing down) this means that the angles of the vectors will vary as shown below:

  • Thus,theangles"grow" clockwise from the upper left corner, according to the order you want.

    Code Example

    Your question is tagged

    19.08.2016 / 21:30