CODEWITHSUNDEEP
c#algorithmsortinggeometrycomputational-geometry
niks
niks

Reputation: 659

Sorting list of points clockwise

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:

Picture A, black dot is a 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:

PictureB,black dot is a center Point

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.

Upvotes: 4

Views: 1992

Answers (1)

gabba
gabba

Reputation: 2880

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.

enter image description here

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.

Upvotes: 2

Related Questions