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();
}
}
}