Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Drawing;
- using System.Drawing.Drawing2D;
- namespace ProgrammingChallenges
- {
- class Program
- {
- private const float RADIANS_TO_DEGREES = (float)(180 / Math.PI);
- public static bool PolygonIsSymmetrical(List<PointF> vertices)
- {
- // The algorithm:
- // 1. Find potential lines of symmetry. For odd-sided polygons, these lines go from each
- // vertex to the midpoint of the opposite line. For even-sided polygons, these lines
- // go from each vertex to the opposite vertex, and from each line's midpoint to the
- // opposite line's midpoint.
- //
- // 2. For each potential line of symmetry, see if the vertices on one side of the line
- // mirror the vertices on the other side. If this is the case for any line, the
- // polygon is symmetrical. This algorithm tests this by rotating and translating the
- // polygon so that the potential line of symmetry is vertical and lies on the y axis.
- // Then two vertices are symmetric if they have the same Y value and opposite X value.
- if (vertices.Count % 2 == 1) // odd number of vertices
- {
- for (int i = 0; i < vertices.Count; i++)
- {
- int startIndex1 = i;
- int startIndex2 = (i + 1) % vertices.Count;
- PointF divideStart = Midpoint(vertices[startIndex1], vertices[startIndex2]);
- PointF divideEnd = vertices[(startIndex2 + vertices.Count / 2) % vertices.Count];
- if (IsLineOfSymmetry(divideStart, divideEnd, vertices, startIndex1, startIndex2,
- vertices.Count / 2))
- {
- return true;
- }
- }
- return false;
- }
- else // even number of vertices
- {
- for (int i = 0; i < vertices.Count / 2; i++)
- {
- int startIndex1 = Modulo(i - 1, vertices.Count);
- int startIndex2 = i + 1;
- PointF oppositeVertex1 = vertices[(i + vertices.Count / 2) % vertices.Count];
- PointF oppositeVertex2 = vertices[(i + vertices.Count / 2 + 1) % vertices.Count];
- // Look for lines of symmetry from vertex to opposite vertex
- // and from midpoint to opposite midpoint
- if (IsLineOfSymmetry(vertices[i], oppositeVertex1, vertices,
- startIndex1, startIndex2, vertices.Count / 2 - 1) ||
- IsLineOfSymmetry(Midpoint(vertices[i], vertices[startIndex2]),
- Midpoint(oppositeVertex1, oppositeVertex2),
- vertices, i, startIndex2, vertices.Count / 2))
- {
- return true;
- }
- }
- return false;
- }
- }
- /// <summary>
- /// Determines whethere a line going from divideStart to divideEnd is a line of symmetry for
- /// a polygon with the given vertices. Compares the vertex at startIndex1 to the vertex at
- /// startIndex2, then decrements startIndex1 and increments startIndex2, and returns false
- /// if they aren't symmetrical. This is done numComparisons times.
- /// </summary>
- /// <param name="divideStart">The start of the dividing line.</param>
- /// <param name="divideEnd">The end of the dividing line.</param>
- /// <param name="vertices">The vertices of the polygon that the line is dividing.</param>
- /// <param name="startIndex1">The index of first vertex to compare.</param>
- /// <param name="startIndex2">The index of the vertex to compare to the first vertex.</param>
- /// <param name="numComparisons">The number of pairs of vertices to compare.</param>
- /// <returns>True if the line is a line of symmetry, false otherwise.</returns>
- private static bool IsLineOfSymmetry(PointF divideStart, PointF divideEnd, List<PointF> vertices,
- int startIndex1, int startIndex2, int numComparisons)
- {
- // Translate and rotate the polygon so divideStart is at the origin
- // and the dividing line is vertical.
- Matrix transform = new Matrix();
- double rotateAmount = Angle(divideStart, divideEnd) * -1 + 90;
- PointF[] vertexArray = vertices.ToArray();
- transform.Translate(-divideStart.X, -divideStart.Y);
- transform.Rotate(Angle(divideStart, divideEnd) * -1 + 90);
- transform.TransformPoints(vertexArray);
- for (int i = 0; i < numComparisons; i++)
- {
- // If any compared point doesn't have a corresponding point with the opposite
- // X value and same Y value, the line is not a line of symmetry.
- PointF vertex1 = vertexArray[Modulo(startIndex1 - i, vertexArray.Count())];
- PointF vertex2 = vertexArray[Modulo(startIndex2 + i, vertexArray.Count())];
- if (vertex1.X != -vertex2.X || vertex1.Y != vertex2.Y)
- {
- return false;
- }
- }
- return true;
- }
- /// <summary>
- /// Calculates angle in degrees between line defined with two points and the x axis.
- /// </summary>
- private static float Angle(PointF start, PointF end)
- {
- return (float)(Math.Atan2(end.Y - start.Y, end.X - start.X) * RADIANS_TO_DEGREES);
- }
- /// <summary>
- /// A modulo function that works with negative values of x.
- /// </summary>
- private static int Modulo(int x, int modBy)
- {
- return (x % modBy + modBy) % modBy;
- }
- private static PointF Midpoint(PointF point1, PointF point2)
- {
- return new PointF((point1.X + point2.X) / 2, (point1.Y + point2.Y) / 2);
- }
- public static void TestPolygonIsSymmetrical(string name, bool expectedResult,
- params PointF [] vertices)
- {
- Console.WriteLine( string.Format("Running test {0}" + Environment.NewLine
- + " Expected result: {1}", name, expectedResult));
- bool actualResult = PolygonIsSymmetrical(vertices.ToList());
- Console.WriteLine(expectedResult == actualResult ? " Success!" : " Failure!");
- }
- static void Main(string[] args)
- {
- // Output:
- // Running test Square
- // Expected result: true
- // Success!
- // Running test Rectangle
- // Expected result: true
- // Success!
- // Running test Rhombus
- // Expected result: true
- // Success!
- // Running test Pentagon
- // Expected result: true
- // Success!
- // Running test Asymmetrical Pentagon
- // Expected result: false
- // Success!
- // Running test Asymmetrical Hexagon
- // Expected result: false
- // Success!
- TestPolygonIsSymmetrical("Square",
- true,
- new PointF(-3, -3),
- new PointF(3, -3),
- new PointF(3, 3),
- new PointF(-3, 3));
- TestPolygonIsSymmetrical("Rectangle",
- true,
- new PointF(2, 2),
- new PointF(8, 2),
- new PointF(8, 7),
- new PointF(2, 7));
- TestPolygonIsSymmetrical("Rhombus",
- true,
- new PointF(-4, 0),
- new PointF(0, 3),
- new PointF(4, 0),
- new PointF(0, -3));
- TestPolygonIsSymmetrical("Pentagon",
- true,
- new PointF(0, 2),
- new PointF(5, 2),
- new PointF(6, 6),
- new PointF(2.5f, 10),
- new PointF(-1, 6));
- TestPolygonIsSymmetrical("Asymmetrical Pentagon",
- false,
- new PointF(0, 2),
- new PointF(6, 2),
- new PointF(6, 6),
- new PointF(2.5f, 10),
- new PointF(-1, 6));
- TestPolygonIsSymmetrical("Asymmetrical Hexagon",
- false,
- new PointF(0, 2),
- new PointF(6, 2),
- new PointF(6, 6),
- new PointF(5, 9),
- new PointF(2.5f, 10),
- new PointF(-1, 6));
- Console.Read();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement