Polygon

using System.Collections.Generic;
using UnityEngine;

namespace AdvancedUtilities.Geometry
{
    /// <summary>
    /// Represents a 2D polygon.
    ///
    /// See more Advanced Utilities @
    /// https://www.assetstore.unity3d.com/en/#!/search/page=1/sortby=popularity/query=publisher:18832
    /// </summary>
    public class Polygon
    {
        /// <summary>
        /// The vertices that represent the edges of the polygon.
        /// Each vertices forms a line with the next vertex, and the last one with the first.
        /// </summary>
        public IList<Vector2> Vertices { get; private set; }

        #region Constructors

        /// <summary>
        /// Constructs a polygon using the provied vertices.
        /// </summary>
        /// <param name="vertices">vertices in order. Each vertex forms a line with the next vertex.</param>
        public Polygon(IList<Vector2> vertices)
        {
            this.Vertices = vertices;
        }

        /// <summary>
        /// Constructs a polygon using the provied vertices.
        /// </summary>
        /// <param name="vertices">vertices in order. Each vertex forms a line with the next vertex.</param>
        public Polygon(IEnumerable<Vector2> vertices)
        {
            this.Vertices = new List<Vector2>();
            foreach (var vertex in vertices)
            {
                this.Vertices.Add(vertex);
            }
        }

        /// <summary>
        /// Constructs a polygon from a rect.
        /// </summary>
        /// <param name="rect">Rectangle that will be converted into a polygon object.</param>
        public Polygon(Rect rect)
        {
            this.Vertices = new List<Vector2>
            {
                new Vector2(rect.x, rect.y),
                new Vector2(rect.x + rect.width, rect.y),
                new Vector2(rect.x + rect.width, rect.y + rect.height),
                new Vector2(rect.x, rect.y + rect.height)
            };
        }

        /// <summary>
        /// Constructs a polygon given a box collider and a scale and rotation for that collider.
        /// </summary>
        /// <param name="boxCollider">The box collider defining the shape of the </param>
        public Polygon(BoxCollider2D boxCollider)
        {
            Vector3 right = (boxCollider.transform.right * (boxCollider.transform.lossyScale.x * boxCollider.size.x * 0.5f));
            Vector3 up = (boxCollider.transform.up * (boxCollider.transform.lossyScale.y * boxCollider.size.y * 0.5f));
            this.Vertices = new List<Vector2>()
            {
                boxCollider.transform.position + right + up,
                boxCollider.transform.position + right - up,
                boxCollider.transform.position - right - up,
                boxCollider.transform.position - right + up
            };
        }

        #endregion

        /// <summary>
        /// Uses Unity's Debug class to draw the polygon in 2d space.
        /// Defaults to color white for drawing.
        /// </summary>
        public void DebugDraw()
        {
            DebugDraw(Color.white);
        }

        /// <summary>
        /// Uses Unity's Debug class to draw the polygon in 2d space.
        /// </summary>
        /// <param name="color">The color of the drawn polygon.</param>
        public void DebugDraw(Color color)
        {
            Vector2 v1 = Vertices[Vertices.Count - 1];
            Vector2 v2 = Vertices[0];

            for (int i = 0; i < Vertices.Count; i++)
            {
                Debug.DrawLine(v1, v2, color);

                if (i == Vertices.Count - 1)
                {
                    break;
                }
                v1 = v2;
                v2 = Vertices[i + 1];
            }
        }

        /// <summary>
        /// Returns whether or not this polygon is actually convex.
        /// </summary>
        /// <returns>Is this polygon convex?</returns>
        public bool IsConvex()
        {
            if (Vertices.Count < 3)
            {
                Debug.LogError("This convex polygon only has 2 vertices...");
                return false;
            }

            // See "Gift Wrapping Algorithm". This isn't exactly that, but it is similar.
            // Basically going around the polygon and measuring that all outer angles are greater than or equal to 90 degrees.
            Vector2 first = (Vertices[Vertices.Count - 1] - Vertices[Vertices.Count - 2]).normalized;
            Vector2 second = (Vertices[0] - Vertices[Vertices.Count - 1]).normalized;
            for (int i = 0; i < Vertices.Count; i++)
            {
                // Clockwise angle
                float dot = first.x * second.x + first.y * second.y;
                float det = first.x * second.y - first.y * second.x;
                float angle = Mathf.Atan2(det, dot) * Mathf.Rad2Deg;
                // If there is a bad angle, it actually appears as a negative, but I'm saying "below 90" since that's really what it should be and it still works great.
                if (angle < 90)
                {
                    return false;
                }

                if (i == Vertices.Count - 1)
                {
                    break;
                }
                first = second;
                second = (Vertices[i + 1] - Vertices[i]).normalized;
            }

            return true;
        }

        /// <summary>
        /// Returns whether or not this convex polygon intersects another polygon.
        ///
        /// This method does not work properly if both this polygon and the other are not convex.
        /// This method does not check if they are convex.
        /// </summary>
        /// <param name="other">The other polygon that is being checked for intersection.</param>
        /// <returns>Whether the this and the other polygon intersect.</returns>
        public bool Intersects(Polygon other)
        {
            if (other == null)
            {
                return false;
            }

            // Try finding a seperating axis
            if (FindSeperatingAxis(this, other))
            {
                return false;
            }

            // And switch up the roles if you don't find one.
            if (FindSeperatingAxis(other, this))
            {
                return false;
            }

            return true;
        }

        /// <summary>
        /// Returns whether or not this convex polygon intersects a rectangle.
        ///
        /// This method does not work properly if this polygon is not convex.
        /// This method does not check if this polygon is convex.
        /// </summary>
        /// <param name="other">The rectangle to see if it intersects with.</param>
        /// <returns>Whether or not the rectangle intersects this polygon.</returns>
        public bool Intersects(Rect other)
        {
            Polygon rectPolygon = new Polygon(other);
            return Intersects(rectPolygon);
        }

        /// <summary>
        /// Returns whether or not this convex polygon intersects a rectangle.
        ///
        /// This method does not work properly if this polygon is not convex.
        /// This method does not check if this polygon is convex.
        /// </summary>
        /// <param name="other">The rectangle to see if it intersects with.</param>
        /// <param name="rectPolygon">A polygon created from the rect for intersecting purposes.</param>
        /// <returns>Whether or not the rectangle intersects this polygon.</returns>
        public bool Intersects(Rect other, out Polygon rectPolygon)
        {
            rectPolygon = new Polygon(other);
            return Intersects(rectPolygon);
        }

        /// <summary>
        /// Returns whether or not this convex polygon intersects a box collider.
        ///
        /// This method does not work properly if this polygon is not convex.
        /// This method does not check if this polygon is convex.
        /// </summary>
        /// <param name="boxCollider2D">Box colldier being checked.</param>
        /// <returns>Whether or not the box collider intersects this polygon.</returns>
        public bool Intersects(BoxCollider2D boxCollider2D)
        {
            Polygon rectPolygon = new Polygon(boxCollider2D);
            return Intersects(rectPolygon);
        }

        /// <summary>
        /// Returns whether or not this convex polygon intersects a box collider.
        ///
        /// This method does not work properly if this polygon is not convex.
        /// This method does not check if this polygon is convex.
        /// </summary>
        /// <param name="boxCollider2D">Box colldier being checked.</param>
        /// <param name="boxColliderPolygon">A polygon created for intersecting purposes.</param>
        /// <returns>Whether or not the box collider intersects this polygon.</returns>
        public bool Intersects(BoxCollider2D boxCollider2D, out Polygon boxColliderPolygon)
        {
            boxColliderPolygon = new Polygon(boxCollider2D);
            return Intersects(boxColliderPolygon);
        }

        /// <summary>
        /// Returns whether or not this polygon intersects a circle collider.
        /// </summary>
        /// <param name="circleCollider2D">The circle collider in question.</param>
        /// <returns>Whether or not this polygon intersects the circle collider.</returns>
        public bool Intersects(CircleCollider2D circleCollider2D)
        {
            float radius = circleCollider2D.radius * Mathf.Max(circleCollider2D.transform.lossyScale.x, circleCollider2D.transform.lossyScale.y);

            return WithinDistanceOf(circleCollider2D.transform.position, radius);
        }

        /// <summary>
        /// Returns whether the polygon is within a distance of the given point.
        /// </summary>
        /// <param name="point">Point to check.</param>
        /// <param name="distance">Distance to see if it's close enough.</param>
        /// <returns>Whether or not the point is within distance of the point.</returns>
        public bool WithinDistanceOf(Vector2 point, float distance)
        {
            return Distance(point) <= distance;
        }

        /// <summary>
        /// Returns the shortest distance from the given point to the polygon.
        /// </summary>
        /// <param name="point">The point to get the distance from.</param>
        /// <returns>The shortest </returns>
        public float Distance(Vector2 point)
        {
            if (Contains(point))
            {
                return 0f;
            }

            float distance = float.MaxValue;

            Vector2 v1 = Vertices[Vertices.Count - 1];
            Vector2 v2 = Vertices[0];
            for (int i = 0; i < Vertices.Count; i++)
            {
                float lineLength = Vector2.Distance(v1, v2);
                Vector2 line = v2 - v1;

                // Have to try 2 perpendicular vectors to get the one that lies on the line.
                Vector2 perp1 = new Vector2(line.y, -line.x).normalized;
                Vector2 perp2 = -perp1;

                // This is the actual distance from the infinite line.
                float distanceFromLine =
                    Mathf.Abs((v2.x - v1.x) * (v1.y - point.y) - (v1.x - point.x) * (v2.y - v1.y))
                    /
                    Mathf.Sqrt((v2.x - v1.x) * (v2.x - v1.x) + (v2.y - v1.y) * (v2.y - v1.y));

                // This represents the point if it were projected onto the line itself.
                Vector2 onLinePointTry1 = point + perp1 * distanceFromLine;
                Vector2 onLinePointTry2 = point + perp2 * distanceFromLine;
                Vector2 onLinePoint = Vector2.Distance(onLinePointTry1, v1) < Vector2.Distance(onLinePointTry2, v1) ? onLinePointTry1 : onLinePointTry2;

                float distFromPoint1 = Vector2.Distance(onLinePoint, v1);
                float distFromPoint2 = Vector2.Distance(onLinePoint, v2);

                // If one of the distances of our on line point is greater than the length of the line, that means it doesn't actually fall on the limited line.
                // So we know the distance is actually the distance to one of the points that make up the line since those are the furthest points off of the line.
                // If they are both shorter than line length, then we know that the distanceFromLine originally calculated is true.
                if (distFromPoint1 > lineLength || distFromPoint2 > lineLength)
                {
                    float actualDistanceFromPoint1 = Vector2.Distance(v1, point);
                    float actualDistanceFromPoint2 = Vector2.Distance(v2, point);
                    distanceFromLine = actualDistanceFromPoint1 < actualDistanceFromPoint2 ? actualDistanceFromPoint1 : actualDistanceFromPoint2;
                }

                if (distanceFromLine < distance)
                {
                    distance = distanceFromLine;
                }

                if (i == Vertices.Count - 1)
                {
                    break;
                }
                v1 = v2;
                v2 = Vertices[i + 1];
            }

            return distance;
        }

        /// <summary>
        /// Checks if the polygon contains the given point.
        /// This is not inclusive of greater values on both sides. A 1x1 square from (0,0) to (1,1) would not contain the value (1,1), (0,1), or (1,0), but would contain (0,0), (0.999f,0.999f), (0.999f,0), and (0,0.999f).
        /// </summary>
        /// <param name="point">Point to check.</param>
        /// <returns>Polygon contains the point.</returns>
        public bool Contains(Vector2 point)
        {
            int i;
            int j;
            bool result = false;
            for (i = 0, j = Vertices.Count - 1; i < Vertices.Count; j = i++)
            {
                if ((Vertices[i].y > point.y) != (Vertices[j].y > point.y) &&
                    (point.x < (Vertices[j].x - Vertices[i].x) * (point.y - Vertices[i].y) / (Vertices[j].y - Vertices[i].y) + Vertices[i].x))
                {
                    result = !result;
                }
            }
            return result;
        }

        /// <summary>
        /// Returns whether or not thw two polygons intersect each other.
        ///
        /// This method does not work properly if both polygons are not convex.
        /// This method does not check if they are convex.
        /// </summary>
        /// <param name="first">The first polygon to check.</param>
        /// <param name="second">The second polygon to check.</param>
        /// <returns>Whether the polygons intersect eachother.</returns>
        public static bool Intersects(Polygon first, Polygon second)
        {
            if (first == null || second == null)
            {
                return false;
            }

            return first.Intersects(second);
        }

        #region Helper methods

        /// <summary>
        /// Returns whether or not there is a seperating axis from p1 to p2.
        /// Order of polygons into the function matters.
        /// </summary>
        /// <param name="p1">First polygon.</param>
        /// <param name="p2">Second polygon.</param>
        /// <returns>p1 can be seperated from p2.</returns>
        private static bool FindSeperatingAxis(Polygon p1, Polygon p2)
        {
            // Iterate over all the edges
            int prev = p1.Vertices.Count - 1;
            for (int cur = 0; cur < p1.Vertices.Count; ++cur)
            {
                Vector2 edge = p1.Vertices[cur] - p1.Vertices[prev];

                // Rotate vector 90 degrees (doesn't matter which way) to get
                // candidate separating axis.
                Vector2 projectOnto = new Vector2(edge.y, -edge.x);

                // Gather extents of both polygons projected onto this axis
                float aMin, aMax, bMin, bMax;
                GatherPolygonProjectionExtents(p1.Vertices, projectOnto, out aMin, out aMax);
                GatherPolygonProjectionExtents(p2.Vertices, projectOnto, out bMin, out bMax);

                // Is this a separating axis?
                if (aMax < bMin) return true;
                if (bMax < aMin) return true;

                // Next edge, please
                prev = cur;
            }

            return false;
        }

        /// <summary>
        /// Gather up one-dimensional extents of the projection of the polygon onto this axis.
        /// </summary>
        /// <param name="vertices">The vertices of a polygon. It's vertices.</param>
        /// <param name="projectOnto">A vector to project onto.</param>
        /// <param name="outMin">Minimum projection value for the edge.</param>
        /// <param name="outMax">Maximum projection value for the edge.</param>
        private static void GatherPolygonProjectionExtents(IList<Vector2> vertices, Vector2 projectOnto, out float outMin, out float outMax)
        {
            outMin = outMax = Vector2.Dot(projectOnto, vertices[0]);

            // Now scan all the rest, growing extents to include them
            for (int i = 1; i < vertices.Count; ++i)
            {
                float d = Vector2.Dot(projectOnto, vertices[i]);
                if (d < outMin)
                {
                    outMin = d;
                }
                else if (d > outMax)
                {
                    outMax = d;
                }
            }
        }

        #endregion
    }
}