Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# Determining if a polygon is symmetrical

By: a guest on Dec 28th, 2011  |  syntax: C#  |  size: 9.13 KB  |  views: 42  |  expires: Never
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));