using System;
using System.Collections.Generic;


/// <summary>
/// <para>The 2D polygon.</para>
/// <para>author Roman Kushnarenko (sromku@gmail.com)</para>
/// <para>C# version https://github.com/BergWerkGIS</para>
/// </summary>
public class Polygon {

	private BoundingBox _boundingBox;
	private List<Line> _sides;

	private Polygon(List<Line> sides, BoundingBox boundingBox) {
		_sides = sides;
		_boundingBox = boundingBox;
	}


	/// <summary>
	/// Get the builder of the polygon
	/// </summary>
	public static Builder GetBuilder => new Builder();


	/// <summary>
	/// Builder of the polygon
	/// </summary>
	public class Builder {

		private List<Point> _vertexes = new List<Point>();
		private List<Line> _sides = new List<Line>();
		private BoundingBox _boundingBox = null;

		private bool _firstPoint = true;
		private bool _isClosed = false;


		/// <summary>
		/// <para>Add vertex points of the polygon.</para>
		/// <para>It is very important to add the vertexes by order, like you were drawing them one by one.</para>
		/// </summary>
		/// <param name="point">The vertex point.</param>
		/// <returns>The builder.</returns>
		public Builder addVertex(Point point) {
			if (_isClosed) {
				// each hole we start with the new array of vertex points
				_vertexes = new List<Point>();
				_isClosed = false;
			}

			updateBoundingBox(point);
			_vertexes.Add(point);

			// add line (edge) to the polygon
			if (_vertexes.Count > 1) {
				Line Line = new Line(_vertexes[_vertexes.Count - 2], point);
				_sides.Add(Line);
			}

			return this;
		}


		/// <summary>
		/// Close the polygon shape. This will create a new side (edge) from the <b>last</b> vertex point to the <b>first</b> vertex point.
		/// </summary>
		/// <returns>The builder.</returns>
		public Builder close() {
			validate();

			// add last Line
			_sides.Add(new Line(_vertexes[_vertexes.Count - 1], _vertexes[0]));
			_isClosed = true;

			return this;
		}


		/// <summary>
		/// Build the instance of the polygon shape.
		/// </summary>
		/// <returns>The polygon.</returns>
		public Polygon build() {
			validate();

			// in case you forgot to close
			if (!_isClosed) {
				// add last Line
				_sides.Add(new Line(_vertexes[_vertexes.Count - 1], _vertexes[0]));
			}

			Polygon polygon = new Polygon(_sides, _boundingBox);
			return polygon;
		}


		/// <summary>
		/// Update bounding box with a new point.
		/// </summary>
		/// <param name="point">New point.</param>
		private void updateBoundingBox(Point point) {
			if (_firstPoint) {
				_boundingBox = new BoundingBox();
				_boundingBox.xMax = point.x;
				_boundingBox.xMin = point.x;
				_boundingBox.yMax = point.y;
				_boundingBox.yMin = point.y;

				_firstPoint = false;
			} else {
				// set bounding box
				if (point.x > _boundingBox.xMax) {
					_boundingBox.xMax = point.x;
				} else if (point.x < _boundingBox.xMin) {
					_boundingBox.xMin = point.x;
				}
				if (point.y > _boundingBox.yMax) {
					_boundingBox.yMax = point.y;
				} else if (point.y < _boundingBox.yMin) {
					_boundingBox.yMin = point.y;
				}
			}
		}

		private void validate() {
			if (_vertexes.Count < 3) {
				throw new Exception("Polygon must have at least 3 points");
			}
		}
	}


	/// <summary>
	/// Check if the the given point is inside of the polygon.
	/// </summary>
	/// <param name="point">The point to check.</param>
	/// <returns><code>True</code> if the point is inside the polygon, otherwise return <code>False</code>.</returns>
	public bool contains(Point point) {
		if (inBoundingBox(point)) {
			Line ray = createRay(point);
			int intersection = 0;
			foreach (Line side in _sides) {
				if (intersect(ray, side)) {
					// System.out.println("intersection++");
					intersection++;
				}
			}

			/*
             * If the number of intersections is odd, then the point is inside the polygon
			 */
			if (intersection % 2 != 0) {
				return true;
			}
		}
		return false;
	}

	public List<Line> getSides() {
		return _sides;
	}


	/// <summary>
	/// By given ray and one side of the polygon, check if both lines intersect.
	/// </summary>
	/// <param name="ray"></param>
	/// <param name="side"></param>
	/// <returns><code>True</code> if both lines intersect, otherwise return <code>False</code>.</returns>
	private bool intersect(Line ray, Line side) {
		Point intersectPoint = null;

		// if both vectors aren't from the kind of x=1 lines then go into
		if (!ray.isVertical() && !side.isVertical()) {
			// check if both vectors are parallel. If they are parallel then no intersection point will exist
			if (ray.getA() - side.getA() == 0) {
				return false;
			}

			double x = ((side.getB() - ray.getB()) / (ray.getA() - side.getA())); // x = (b2-b1)/(a1-a2)
			double y = side.getA() * x + side.getB(); // y = a2*x+b2
			intersectPoint = new Point(x, y);
		} else if (ray.isVertical() && !side.isVertical()) {
			double x = ray.getStart().x;
			double y = side.getA() * x + side.getB();
			intersectPoint = new Point(x, y);
		} else if (!ray.isVertical() && side.isVertical()) {
			double x = side.getStart().x;
			double y = ray.getA() * x + ray.getB();
			intersectPoint = new Point(x, y);
		} else {
			return false;
		}

		// System.out.println("Ray: " + ray.toString() + " ,Side: " + side);
		// System.out.println("Intersect point: " + intersectPoint.toString());

		if (side.isInside(intersectPoint) && ray.isInside(intersectPoint)) {
			return true;
		}

		return false;
	}


	/// <summary>
	/// <para>Create a ray. The ray will be created by given point and on point outside of the polygon.</para>
	/// <para>he outside point is calculated automatically.</para>
	/// </summary>
	/// <param name="point"></param>
	/// <returns></returns>
	private Line createRay(Point point) {
		// create outside point
		double epsilon = (_boundingBox.xMax - _boundingBox.xMin) / 10e6;
		Point outsidePoint = new Point(_boundingBox.xMin - epsilon, _boundingBox.yMin);

		Line vector = new Line(outsidePoint, point);
		return vector;
	}


	/// <summary>
	/// Check if the given point is in bounding box.
	/// </summary>
	/// <param name="point"></param>
	/// <returns><code>True</code> if the point in bounding box, otherwise return <code>False</code></returns>
	private bool inBoundingBox(Point point) {
		if (point.x < _boundingBox.xMin || point.x > _boundingBox.xMax || point.y < _boundingBox.yMin || point.y > _boundingBox.yMax) {
			return false;
		}
		return true;
	}


	private class BoundingBox {
		public double xMax = double.NegativeInfinity;
		public double xMin = double.NegativeInfinity;
		public double yMax = double.NegativeInfinity;
		public double yMin = double.NegativeInfinity;
	}
}