Want more features on Pastebin? Sign Up, it's FREE!
Guest

Determining if a polygon is symmetrical

By: a guest on Dec 28th, 2011  |  syntax: C#  |  size: 9.13 KB  |  views: 40  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. using System.Drawing;
  7. using System.Drawing.Drawing2D;
  8.  
  9. namespace ProgrammingChallenges
  10. {
  11.    class Program
  12.    {
  13.       private const float RADIANS_TO_DEGREES = (float)(180 / Math.PI);
  14.  
  15.       public static bool PolygonIsSymmetrical(List<PointF> vertices)
  16.       {
  17.          // The algorithm:
  18.          // 1. Find potential lines of symmetry.  For odd-sided polygons, these lines go from each
  19.          //    vertex to the midpoint of the opposite line.  For even-sided polygons, these lines
  20.          //    go from each vertex to the opposite vertex, and from each line's midpoint to the
  21.          //    opposite line's midpoint.
  22.          //
  23.          // 2. For each potential line of symmetry, see if the vertices on one side of the line
  24.          //    mirror the vertices on the other side.  If this is the case for any line, the
  25.          //    polygon is symmetrical.  This algorithm tests this by rotating and translating the
  26.          //    polygon so that the potential line of symmetry is vertical and lies on the y axis.
  27.          //    Then two vertices are symmetric if they have the same Y value and opposite X value.
  28.  
  29.          if (vertices.Count % 2 == 1) // odd number of vertices
  30.          {
  31.             for (int i = 0; i < vertices.Count; i++)
  32.             {
  33.                int startIndex1 = i;
  34.                int startIndex2 = (i + 1) % vertices.Count;
  35.                PointF divideStart = Midpoint(vertices[startIndex1], vertices[startIndex2]);
  36.                PointF divideEnd = vertices[(startIndex2 + vertices.Count / 2) % vertices.Count];
  37.                if (IsLineOfSymmetry(divideStart, divideEnd, vertices, startIndex1, startIndex2,
  38.                    vertices.Count / 2))
  39.                {
  40.                   return true;
  41.                }
  42.             }
  43.             return false;
  44.          }
  45.          else // even number of vertices
  46.          {
  47.             for (int i = 0; i < vertices.Count / 2; i++)
  48.             {
  49.                int startIndex1 = Modulo(i - 1, vertices.Count);
  50.                int startIndex2 = i + 1;
  51.                PointF oppositeVertex1 = vertices[(i + vertices.Count / 2) % vertices.Count];
  52.                PointF oppositeVertex2 = vertices[(i + vertices.Count / 2 + 1) % vertices.Count];
  53.                // Look for lines of symmetry from vertex to opposite vertex
  54.                // and from midpoint to opposite midpoint
  55.                if (IsLineOfSymmetry(vertices[i], oppositeVertex1, vertices,
  56.                                    startIndex1, startIndex2, vertices.Count / 2 - 1) ||
  57.                    IsLineOfSymmetry(Midpoint(vertices[i], vertices[startIndex2]),
  58.                                     Midpoint(oppositeVertex1, oppositeVertex2),
  59.                                     vertices, i, startIndex2, vertices.Count / 2))
  60.                {
  61.                   return true;
  62.                }
  63.             }
  64.             return false;
  65.          }
  66.       }
  67.  
  68.       /// <summary>
  69.       /// Determines whethere a line going from divideStart to divideEnd is a line of symmetry for
  70.       /// a polygon with the given vertices. Compares the vertex at startIndex1 to the vertex at
  71.       /// startIndex2, then decrements startIndex1 and increments startIndex2, and returns false
  72.       /// if they aren't symmetrical.  This is done numComparisons times.
  73.       /// </summary>
  74.       /// <param name="divideStart">The start of the dividing line.</param>
  75.       /// <param name="divideEnd">The end of the dividing line.</param>
  76.       /// <param name="vertices">The vertices of the polygon that the line is dividing.</param>
  77.       /// <param name="startIndex1">The index of first vertex to compare.</param>
  78.       /// <param name="startIndex2">The index of the vertex to compare to the first vertex.</param>
  79.       /// <param name="numComparisons">The number of pairs of vertices to compare.</param>
  80.       /// <returns>True if the line is a line of symmetry, false otherwise.</returns>
  81.       private static bool IsLineOfSymmetry(PointF divideStart, PointF divideEnd, List<PointF> vertices,
  82.                                        int startIndex1, int startIndex2, int numComparisons)
  83.       {
  84.          // Translate and rotate the polygon so divideStart is at the origin
  85.          // and the dividing line is vertical.        
  86.          Matrix transform = new Matrix();
  87.          double rotateAmount = Angle(divideStart, divideEnd) * -1 + 90;
  88.          PointF[] vertexArray = vertices.ToArray();
  89.          transform.Translate(-divideStart.X, -divideStart.Y);
  90.          transform.Rotate(Angle(divideStart, divideEnd) * -1 + 90);
  91.          transform.TransformPoints(vertexArray);
  92.  
  93.          for (int i = 0; i < numComparisons; i++)
  94.          {
  95.             // If any compared point doesn't have a corresponding point with the opposite
  96.             // X value and same Y value, the line is not a line of symmetry.
  97.             PointF vertex1 = vertexArray[Modulo(startIndex1 - i, vertexArray.Count())];
  98.             PointF vertex2 = vertexArray[Modulo(startIndex2 + i, vertexArray.Count())];
  99.             if (vertex1.X != -vertex2.X || vertex1.Y != vertex2.Y)
  100.             {
  101.                return false;
  102.             }
  103.          }
  104.          return true;
  105.       }
  106.  
  107.       /// <summary>
  108.       /// Calculates angle in degrees between line defined with two points and the x axis.
  109.       /// </summary>
  110.       private static float Angle(PointF start, PointF end)
  111.       {
  112.          return (float)(Math.Atan2(end.Y - start.Y, end.X - start.X) * RADIANS_TO_DEGREES);
  113.       }
  114.  
  115.       /// <summary>
  116.       /// A modulo function that works with negative values of x.
  117.       /// </summary>
  118.       private static int Modulo(int x, int modBy)
  119.       {
  120.          return (x % modBy + modBy) % modBy;
  121.       }
  122.  
  123.       private static PointF Midpoint(PointF point1, PointF point2)
  124.       {
  125.          return new PointF((point1.X + point2.X) / 2, (point1.Y + point2.Y) / 2);
  126.       }
  127.  
  128.       public static void TestPolygonIsSymmetrical(string name, bool expectedResult,
  129.                                                   params PointF [] vertices)
  130.       {
  131.          Console.WriteLine( string.Format("Running test {0}" + Environment.NewLine
  132.                                           + "  Expected result: {1}", name, expectedResult));
  133.          bool actualResult = PolygonIsSymmetrical(vertices.ToList());
  134.          Console.WriteLine(expectedResult == actualResult ? "  Success!" : "  Failure!");
  135.       }
  136.  
  137.       static void Main(string[] args)
  138.       {
  139.          // Output:
  140.          // Running test Square
  141.          //   Expected result: true
  142.          //   Success!
  143.          // Running test Rectangle
  144.          //   Expected result: true
  145.          //   Success!
  146.          // Running test Rhombus
  147.          //   Expected result: true
  148.          //   Success!
  149.          // Running test Pentagon
  150.          //   Expected result: true
  151.          //   Success!
  152.          // Running test Asymmetrical Pentagon
  153.          //   Expected result: false
  154.          //   Success!
  155.          // Running test Asymmetrical Hexagon
  156.          //   Expected result: false
  157.          //   Success!
  158.  
  159.          TestPolygonIsSymmetrical("Square",
  160.                                   true,
  161.                                   new PointF(-3, -3),
  162.                                   new PointF(3, -3),
  163.                                   new PointF(3, 3),
  164.                                   new PointF(-3, 3));
  165.          TestPolygonIsSymmetrical("Rectangle",
  166.                                   true,
  167.                                   new PointF(2, 2),
  168.                                   new PointF(8, 2),
  169.                                   new PointF(8, 7),
  170.                                   new PointF(2, 7));
  171.          TestPolygonIsSymmetrical("Rhombus",
  172.                                   true,
  173.                                   new PointF(-4, 0),
  174.                                   new PointF(0, 3),
  175.                                   new PointF(4, 0),
  176.                                   new PointF(0, -3));
  177.          TestPolygonIsSymmetrical("Pentagon",
  178.                                   true,
  179.                                   new PointF(0, 2),
  180.                                   new PointF(5, 2),
  181.                                   new PointF(6, 6),
  182.                                   new PointF(2.5f, 10),
  183.                                   new PointF(-1, 6));
  184.          TestPolygonIsSymmetrical("Asymmetrical Pentagon",
  185.                                   false,
  186.                                   new PointF(0, 2),
  187.                                   new PointF(6, 2),
  188.                                   new PointF(6, 6),
  189.                                   new PointF(2.5f, 10),
  190.                                   new PointF(-1, 6));
  191.          TestPolygonIsSymmetrical("Asymmetrical Hexagon",
  192.                                   false,
  193.                                   new PointF(0, 2),
  194.                                   new PointF(6, 2),
  195.                                   new PointF(6, 6),
  196.                                   new PointF(5, 9),
  197.                                   new PointF(2.5f, 10),
  198.                                   new PointF(-1, 6));
  199.          Console.Read();
  200.       }
  201.    }
  202. }
clone this paste RAW Paste Data