topic Re: Sorting a list point of a polygon clockwise in .NET Forum

Sorting a list point of a polygon clockwise

hoainamtdt — Sat, 09 Sep 2017 03:09:18 GMT

I have a point array. I want to sort point of a polygon to calculate the area.

This is my list point:

- Point3d 1  X: 16.9739362797234 Y: 1.15620205549732 Z: 0
- Point3d 2  X: 16.671656969313 Y: 1.16417151545853 Z: 0
- Point3d 3  X: 16.0185770382255 Y: 1.18138967820743 Z: 0
- Point3d 4  X: 16.9739362797234 Y: 1.45620205549783 Z: 0
- Point3d 5  X: 15.7386856391879 Y: 1.48876889081456 Z: 0
- Point3d 6  X: 3.51984642951532 Y: 1.51091316764773 Z: 0
- Point3d 7  X: 3.51984642951532 Y: 1.81091316764773 Z: 0
- Point3d 8  X: -10.2845662421009 Y: 1.98207932732037 Z: 0
- Point3d 9  X: -10.6449687487931 Y: 1.9954460528974 Z: 0
- Point3d 10  X: -10.7612815869122 Y: 1.99064617997511 Z: 0
- Point3d 11  X: -10.8658975847679 Y: 1.99013890212357 Z: 0
- Point3d 12  X: -11.620742475742 Y: 1.98928295827633 Z: 0
- Point3d 13  X: -10.2845662417003 Y: 1.68207932730779 Z: 0
- Point3d 14  X: -10.6449687486466 Y: 1.69544605290257 Z: 0
- Point3d 15  X: -10.761281586839 Y: 1.69064617997781 Z: 0
- Point3d 16  X: -10.865897584949 Y: 1.69013890212357 Z: 0
- Point3d 17  X: -11.6207424763237 Y: 1.68928295827587 Z: 0
- Point3d 18  X: -15.6175840485863 Y: 1.99120797569964 Z: 0
- Point3d 19  X: -16.1629232880395 Y: 1.99147062997825 Z: 0
- Point3d 20  X: -15.6175840485863 Y: 1.69120797569966 Z: 0
- Point3d 20  X: -15.6175840485863 Y: 1.69120797569966 Z: 0
- Point3d 21  X: -16.1629232880395 Y: 1.69147062997776 Z: 0

My code:

 var sortList = ltsPoint.OrderBy(x => Math.Atan2(x.Y, x.X)).ToList();

But not successful. Hope everybody help please, Thanks!

Re: Sorting a list point of a polygon clockwise

_gile — Sat, 09 Sep 2017 12:50:19 GMT

Hi,

You have to clarify what you mean with: "sort point of a polygon".

Are the point list you provided the polygon vertices?

If so, you cannot change their order (except reversing them) without modifiing the polygon shape (and its area).

If not, you have to explain further the relation between this point list and the polygon you expect.

Re: Sorting a list point of a polygon clockwise

hoainamtdt — Sat, 09 Sep 2017 13:14:36 GMT

Thanks for the reply _gile ;

I have a xy point list, I want to arrange the point into the top of the polygon to get its area.

Re: Sorting a list point of a polygon clockwise

_gile — Sat, 09 Sep 2017 13:15:35 GMT

If your point list describe the polygon vertices, you can get the signed polygon area (positive if points are CCW negative if they're CW) with the following code.

        public double PolygonSignedArea(Point2d[] points)
        {
            Point2d p0 = points[0];
            double area = 0.0;

            double triangleSignedArea(Point2d p1, Point2d p2) =>
                (p1.X - p0.X) * (p2.Y - p0.Y) - (p2.X - p0.X) * (p1.Y - p0.Y);

            for (int i = 0; i < points.Length - 1; i++)
            {
                area += triangleSignedArea(points[i], points[i + 1]);
            }
            return area / 2.0;
        }

Re: Sorting a list point of a polygon clockwise

hoainamtdt — Sat, 09 Sep 2017 13:22:53 GMT

Re: Sorting a list point of a polygon clockwise

hoainamtdt — Sat, 09 Sep 2017 13:54:12 GMT

Thanks _gile!

The code returns the correct area with the point aligned clockwise, and the list point is not sorted returns the wrong area.

Re: Sorting a list point of a polygon clockwise

_gile — Sat, 09 Sep 2017 14:22:38 GMT

I do not understand what objective criteria allow you to retain certain points and to exclude others.
For example, a 2D convex hull would have followed the green line (here's a code code to get the convex hull from a point list).

Re: Sorting a list point of a polygon clockwise

hoainamtdt — Sat, 09 Sep 2017 15:09:51 GMT

Thanks , very grateful you have enthusiastically helped me,

I am using civil3d, i get the promiscuous point list from materialsection, I am looking to take the area of this point list

Re: Sorting a list point of a polygon clockwise

_gile — Sun, 10 Sep 2017 08:50:44 GMT

Ok,

To get the "boundary point list", you can use the following ConvexHull() method passing it the "point list from section".

You ca then get the "area" using the PolygonSignedArea() method passing it the point list returned by ConvexHull().

double area = PolygonSignedArea(ConvexHull(pointListFromSection));

        public List<Point2d> ConvexHull(IEnumerable<Point2d> source)
        {
            var p0 = source.OrderBy(p => p.Y).ThenBy(p => p.X).First();

            bool Clockwise(Point2d p1, Point2d p2, Point2d p3) =>
                DoubleSignedArea(p1, p2, p3) < 1e-9;

            double Cosine(Point2d pt)
            {
                double d = p0.GetDistanceTo(pt);
                return d == 0.0 ? 1.0 : Math.Round((pt.X - p0.X) / d, 9);
            }

            var pts = source.OrderByDescending(p => Cosine(p)).ThenBy(p => p0.GetDistanceTo(p)).ToList();
            for (int i = 1; i < pts.Count - 1; i++)
            {
                while (i > 0 && Clockwise(pts[i - 1], pts[i], pts[i + 1]))
                {
                    pts.RemoveAt(i);
                    i--;
                }
            }
            return pts;
        }

        public double PolygonSignedArea(IEnumerable<Point2d> source)
        {
            var points = source.ToArray();
            Point2d p0 = points[0];
            double area = 0.0;

            for (int i = 0; i < points.Length - 1; i++)
            {
                area += DoubleSignedArea(p0, points[i], points[i + 1]);
            }
            return area / 2.0;
        }

        private double DoubleSignedArea(Point2d p1, Point2d p2, Point2d p3) =>
            (p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X);

Re: Sorting a list point of a polygon clockwise

mohamed_adel_ghazaly — Wed, 22 Sep 2021 14:36:57 GMT

Hello,

I need to order points clock wise without excluding any even the inside points, i tried to remove the for loop where removing happens but it did not work very well. any suggestion

Re: Sorting a list point of a polygon clockwise

_gile — Wed, 22 Sep 2021 15:22:02 GMT

Hi,

@mohamed_adel_ghazaly a écrit :

order points clock wise without excluding any even the inside points

This doesn't mean much if you don't specify a reference point. For example, depending on which point you start from (the lowest, the highest, the leftmost), the results are different.

Re: Sorting a list point of a polygon clockwise

mohamed_adel_ghazaly — Wed, 22 Sep 2021 16:00:03 GMT

Ok, let’s say by the highest point.

Re: Sorting a list point of a polygon clockwise

_gile — Wed, 22 Sep 2021 17:57:05 GMT

@mohamed_adel_ghazaly this should work:

static Point3dCollection SortPointsClockwise(Point3dCollection points) { var result = new Point3dCollection(); var topMost = points.Cast<Point3d>().Aggregate((p1, p2) => p1.Y < p2.Y ? p2 : p1); points.Remove(topMost); result.Add(topMost); foreach (var pt in points .Cast<Point3d>() .OrderBy(p => Vector3d.XAxis.GetAngleTo(topMost.GetVectorTo(p)))) { result.Add(pt); } return result; }