Sorting list of points clockwise

Question

I have encountered problem and don't know how to solve it.

I am trying to sort List of points so that all points are in order to form a Path. What I have done so far is I calculated center point of all points in the list and then I have used code from this post based on which the sorting is done. Here is borrowed code snippet:

public int Compare(Point3D pointA, Point3D pointB)
{
    if (pointA.X - CenterPoint.X >= 0 && pointB.X - CenterPoint.X < 0)
        return 1;
    if (pointA.X - CenterPoint.X < 0 && pointB.X - CenterPoint.X >= 0)
        return -1;

    if (pointA.X - CenterPoint.X == 0 && pointB.X - CenterPoint.X == 0)
    {
        if (pointA.Y - CenterPoint.Y >= 0 || pointB.Y - CenterPoint.Y >= 0)
           if (pointA.Y > pointB.Y)
               return 1;
            else return -1;
        if (pointB.Y > pointA.Y)
            return 1;
        else return -1;
    }

    // compute the cross product of vectors (CenterPoint -> a) x (CenterPoint -> b)
    double det = (pointA.X - CenterPoint.X)*(pointB.Y - CenterPoint.Y) -
                     (pointB.X - CenterPoint.X)*(pointA.Y - CenterPoint.Y);
    if (det < 0)
        return 1;
    if (det > 0)
        return -1;

    // points a and b are on the same line from the CenterPoint
    // check which point is closer to the CenterPoint
    double d1 = (pointA.X - CenterPoint.X)*(pointA.X - CenterPoint.X) +
                    (pointA.Y - CenterPoint.Y)*(pointA.Y - CenterPoint.Y);
    double d2 = (pointB.X - CenterPoint.X)*(pointB.X - CenterPoint.X) +
                    (pointB.Y - CenterPoint.Y)*(pointB.Y - CenterPoint.Y);
    if (d1 > d2)
        return 1;
    else return -1;
}

In some instances it works fine but sometimes it works out wonders, please see attached pictures, black point is calculated center point:

In picture A everything is ok, but if I decide to move up points forming two horizontal lines, the I run into this:

The green line is how it should look like, the black line is how it really looks and I can't figure out why i is like that. I also tried atan() solutions but with same results. Any help would be really appreciated.

i think it would be interesting to add to your pictures the location of the calculated center point — pm100, Mar 31 '16 at 15:05
I have a list of points and would like to draw path through these points. Unfortunately they are not sorted and give incorrect results. Therefore I am trying to sort them myself. @gabba — niks, Mar 31 '16 at 15:21
In general case you can not draw a correct path if you didn't know order of points. On your second picture, the order of points in path is clockwise around central point. — gabba, Mar 31 '16 at 15:48
Once you have your center point, then you could just calculate the angle between your point and the center point and use that for your sort. — ManoDestra, Mar 31 '16 at 16:42
It depends on the points in question. You're not going to be able to reverse engineer a correctly sorted path for every given set of points. Imagine a set of 100 points on a 10 x 10 grid from (0, 0) through to (9, 9). What would be the path through those points? You see what I mean? It only works for a valid center point. And the calculation of that center point is going to be fluid. And even then you can't guarantee derivation of a path through the given points. All you can do here is an approximation given a "reasonable" unsorted set of points. — ManoDestra, Mar 31 '16 at 18:18

gabba · Answer 1 · 2016-03-31T18:10:40.373

2

The points sorted by clockwise well in both your examples. But for second example it's method not suitable. Clockwise algorithm will work only on convex figures.

Here is the sample of not supported figure, with no available central point.

So if you have some set of points, and don't know how to link them, and don't know anything about figure you can't restore original figure.

edited Mar 31 '16 at 18:10

answered Mar 31 '16 at 15:04

gabba

2,815
2
27
48

So you say that if I have concave polygon, it is impossible to sort points to draw correct path? – niks Mar 31 '16 at 16:10
1

@niks: The first polygon is also concave. The algorithm works on [star-shaped polygons](https://en.wikipedia.org/wiki/Star-shaped_polygon) when the centre point is in the kernel. Convex polygons are star shaped and their kernel is the whole polygon, so clockwise sorting is guanateed to work for them. You can use clockwise sorting for the second polygon, too, if you find a way to move the centre to the part where the bars of the T cross. – M Oehm Mar 31 '16 at 17:44
1

@MOehm, There is no way to make algorithm to work with all cases. – gabba Mar 31 '16 at 18:05
@niks, if you have some set of points, and don't know how to link them, and don't know anything about figure you can't restore original figure. But probably you know some rule about figure or points? – gabba Mar 31 '16 at 18:10
@MOehm Unfortunately, polygons will be in different shapes and sizes, therefore it will not be possible to adjust center of each polygon. Looks like I have to think another way of solving my problems. – niks Mar 31 '16 at 18:13
@gabba Thank you, I understand that at this moment it in not possible to accomplish what I have imagined. I'll try to make another solution! – niks Mar 31 '16 at 18:16
@gabba: Yes, but I haven't said that. My comment was meant as a clarification that there are some concave polygons for which you can use the sorting strategy. As you said, if you have no other information on the points, you can only guess. – M Oehm Mar 31 '16 at 20:04

Sorting list of points clockwise

1 Answers1