How to identify the polygone is triangle in wpf

Question

I have 'n' number of polygons as like below.

    <Polygon Points="544,245,544,175,568,175,568,175" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="2,223,96,223,96,153,96,153" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="350,315,350,333,306,333,306,395,306,395" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="164,53,160,53,160,51,160,55,160,55" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="264,63,264,58,264,68,264,63,267,63,267,60,267,66,267,63,270,63,270,58,270,68,270,68" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="8,63,444,63,444,168,444,168" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="212,169,212,93,285,93,285,63,285,63" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="26,93,127,93,127,148,29,148,29,148" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="152,116,152,132,212,132,212,132" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="121,316,121,333,70,333,70,366,70,366" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="464,395,488,395,488,284,527,284,527,284" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="168,63,168,67,180,59,180,67,168,59,168,59" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="173,62,173,56,165,56,165,51,175,51,175,61,175,61" Stroke="Black" StrokeThickness="1" />
    <Polygon Points="3,285,121,285,121,316,211,316,211,304,211,304" Stroke="Black" StrokeThickness="1" />

Please help me to identify what are the triangles in these polygons

I have tried to identify the vertices like below..

        Polygon polygon = new Polygon();
        polygon.Points = new System.Windows.Media.PointCollection()
        {
            new Point(446,134),
            new Point(442,134),
            new Point(444,140),
            new Point(444,140),
        }; 

        List<double> verticesPoints = new List<double>();
        for (int i = 0; i < polygon.Points.Count - 1; i++)
        {
            var point1 = polygon.Points[i];
            var point2 = polygon.Points[i + 1];

            //calculate delta x and delta y between the two points
            var deltaX = Math.Pow((point2.X - point1.X), 2);
            var deltaY = Math.Pow((point2.Y - point1.Y), 2);

            //pythagras theorem for distance
            var distance = Math.Sqrt(deltaY + deltaX);

            //distance is zero..then same point
            if (distance != 0)
            {
                verticesPoints.Add(distance);
            }
        }
       ///Here is the code to calculate angle and consider the triangle
       ///three vertices then it might be triangle.
        if (verticesPoints.Count == 3)
        {
            ///use The Law of Cosines
            ///cos(C) = a2 + b2 − c2 /2ab
            ///cos(A) = b2 + c2 − a2 /bc
            ///cos(B) = c2 + a2 − b2 /ca
            var a = ((Math.Pow(verticesPoints[1], 2)) + (Math.Pow(verticesPoints[2], 2)) - (Math.Pow(verticesPoints[0], 2)))
                      / (2 * verticesPoints[1] * verticesPoints[2]);

            var b = ((Math.Pow(verticesPoints[0], 2)) + (Math.Pow(verticesPoints[2], 2)) - (Math.Pow(verticesPoints[1], 2)))
                     / (2 * verticesPoints[0] * verticesPoints[2]);

            var c = ((Math.Pow(verticesPoints[0], 2)) + (Math.Pow(verticesPoints[1], 2)) - (Math.Pow(verticesPoints[2], 2)))
                     / (2 * verticesPoints[0] * verticesPoints[1]);

            ///Inverse of cos
            var radians1 = Math.Acos(a);
            ///Convert radian to degree
            double degrees1 = (radians1 * 180.0) / Math.PI;

            ///Inverse of cos
            var radians2 = Math.Acos(b);
            //Convert radian to degree
            double degrees2 = (radians2 * 180.0) / Math.PI;

            ///Inverse of cos
            var radians3 = Math.Acos(c);
            ///Convert radian to degree
            double degrees3 = (radians3 * 180.0) / Math.PI;

            var totalDegrees = degrees1 + degrees2 + degrees3;
            if (totalDegrees == 180)
            {
               // Consider triangle
            }
        }

But above code is not working for <Polygon Points="446,134,442,134,444,140,444,140" Stroke="Black" StrokeThickness="1" /> it is giving only two vertices but it is a triangle and some scenario getting 3 vertices but totalDegrees is not as 180

Just loop through and see if the polygon has 3 points? What have you tried so far, and what part are you having a problem with? — Diado, Aug 30 '18 at 08:49
@Diado It is a little bit more complicated than that (3 points on a line, for example), but it's a good start :) The code so far would help, of course. — ProgrammingLlama, Aug 30 '18 at 08:53
To extend on the comment from @John : checking if a point lies on line can be done as described in https://stackoverflow.com/questions/11907947/how-to-check-if-a-point-lies-on-a-line-between-2-other-points — ckuri, Aug 30 '18 at 09:03
On a further thought, I would not compare the distances but the angles, i.e. `var angle = Math.Atan2(deltaY, deltaX)` between each pair. If the angle stays the same (within some margin to cover for floating point arithmetic quirks) the current vertex is just an extension of the previous vertex and both form a single line. — ckuri, Aug 30 '18 at 09:11

Alfie · Answer 1 · 2018-08-30T11:32:19.450

This code here iterates through the points and calculates the gradient between each of them. If the gradient is the same for two sequential points they must be the same line, so the noOfPoints is not incremented otherwise it is incremented.

The first gradient is stored in firstGradient in order to check if the gradient connecting the last and first point is the same as the gradient between the first and second point.

        Polygon polygon = new Polygon();
        polygon.Points = new System.Windows.Media.PointCollection()
    {
        new Point(446,134),
        new Point(442,134),
        new Point(444,140),
        new Point(444,140),
    };

        List<double> verticesPoints = new List<double>();
        double? firstGradient = null;
        double? gradient = null;
        double? newGradient = null;
        int noOfSides = 1;

        for (int i = 0; i < polygon.Points.Count - 1; i++)
        {
            var point1 = polygon.Points[i];
            var point2 = polygon.Points[i + 1];

            if(point1 == point2) { continue;}

            //calculate delta x and delta y between the two points
            var deltaX = point2.X - point1.X;
            var deltaY = point2.Y - point1.Y;

            //calculate gradient
            newGradient = (deltaY / deltaX);

            if (i == 0)
            {
                firstGradient = newGradient;
            }

            if ((gradient != newGradient) && (i != polygon.Points.Count - 2))
            {
                noOfSides++;
            }
            else if (i == polygon.Points.Count - 2)
            {
                if ((gradient != newGradient) && (firstGradient != newGradient)) //This now checks the gradient between the last and first point.
                {

                    point1 = polygon.Points[i+1];
                    point2 = polygon.Points[0];

                    if (point1 == point2) { continue; }

                    //calculate delta x and delta y between the two points
                    deltaX = point2.X - point1.X;
                    deltaY = point2.Y - point1.Y;

                    //calculate gradient
                    newGradient = (deltaY / deltaX);

                    if(newGradient != firstGradient)
                    {
                        noOfSides++;
                    }

                }


            gradient = newGradient;
        }

code is not identifying triangles ...some of the polygons are rectangle... — Sharan RM, Aug 30 '18 at 12:45
@SharanRM the logic is identifying triangles as rectangles or is identifying rectangles as triangles? — Alfie, Aug 30 '18 at 12:49
@SharanRM could you send me a set of points where this code doesn't correctly identify a triangle please? — Alfie, Aug 30 '18 at 13:08
Thank you all ..using AForge.Math.Geometry library solved the problem.Reference http://aforgenet.com/articles/shape_checker/ — Sharan RM, Dec 04 '18 at 04:25

score 0 · Accepted Answer · answered Dec 04 '18 at 04:39

I have solved the above problem using "AForge.NET"

        Polygon polygon = new Polygon();
        polygon.Points = new PointCollection()
        {
             new Point(446,134),
             new Point(442,134),
             new Point(444,140),
             new Point(444,140),
        };

        SimpleShapeChecker shapeChecker = new  SimpleShapeChecker();
        List<IntPoint> edgePoints = new List<IntPoint>();
        List<IntPoint> corners;
        for (int i = 0; i <= polygon.Points.Count - 1; i++)
        {
            edgePoints.Add(new IntPoint((int)polygon.Points[i].X, (int)polygon.Points[i].Y));
        }

        shapeChecker.MinAcceptableDistortion = 0.2f;
        shapeChecker.LengthError = 0;
        shapeChecker.AngleError = 5;
        shapeChecker.RelativeDistortionLimit = 0;

        if (shapeChecker.IsTriangle(edgePoints, out corners))
        {
            //shape is triangle
        }

Need to add below namespace

using AForge;
using AForge.Math.Geometry;

Reference :http://aforgenet.com/articles/shape_checker/

How to identify the polygone is triangle in wpf

2 Answers2