# Convex Polygon class
class ConvexPolygon
	super APolygon

	# Does this polygon intersects `other` ?
	#
	# ~~~
	# var p1 = new Point[Float](0.0, 0.0)
	# var p2 = new Point[Float](5.0, 0.0)
	# var p3 = new Point[Float](0.0, 5.0)
	# var p4 = new Point[Float](5.0, 5.0)
	# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
	# var poly = new ConvexPolygon(arr)
	# poly.sort_ccw
	# p1 = new Point[Float](2.5, 2.5)
	# p2 = new Point[Float](7.5, 2.5)
	# p3 = new Point[Float](2.5, 7.5)
	# p4 = new Point[Float](7.5, 7.5)
	# arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
	# var poly2 = new ConvexPolygon(arr)
	# poly2.sort_ccw
	# assert poly.intersects(poly2)
	# ~~~
	redef fun intersects(other) do
		assert is_convex

		var axes1 = axes
		var axes2 = other.axes
		for axis in axes1 do
			var project1 = project(axis)
			var project2 = other.project(axis)
			if not project1.overlap(project2) then return false
		end
		for axis in axes2 do
			var project1 = project(axis)
			var project2 = other.project(axis)
			if not project1.overlap(project2) then return false
		end
		return true
	end

	# ~~~
	# var p1 = new Point[Float](0.0, 0.0)
	# var p2 = new Point[Float](5.0, 0.0)
	# var p3 = new Point[Float](0.0, 5.0)
	# var p4 = new Point[Float](5.0, 5.0)
	# var p5 = new Point[Float](2.5, 2.5)
	# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
	# var poly = new ConvexPolygon(arr)
	# poly.sort_ccw
	# assert poly.contain(p5)
	# ~~~
	redef fun contain(p) do
		var prev = points[points.length - 1]
		var curr = p
		var next = points[0]
		var is_ccw = turn_left(prev, curr, next)
		for i in [1..points.length[ do
			prev = next
			next = points[i]
			if turn_left(prev, curr, next) != is_ccw then return false
		end
		return true
	end

	# Check if the order of the points in the polygon is counter-clockwise
	# The vertices in the polygon need to be sorted
	#
	# ~~~
	# var p1 = new Point[Float](0.0, 0.0)
	# var p2 = new Point[Float](5.0, 0.0)
	# var p3 = new Point[Float](0.0, 5.0)
	# var p4 = new Point[Float](5.0, 5.0)
	# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
	# var poly = new ConvexPolygon(arr)
	# poly.sort_ccw
	# assert poly.is_ccw
	# ~~~
	fun is_ccw: Bool do
		var min = points[0].y
		var min_index = 0
		for i in [1..points.length - 1[ do
			if points[i].y < min then
				min = points[i].y
				min_index = i
			end
		end
		var prev = points[(min_index - 1 + points.length) % points.length]
		var next = points[(min_index + 1) % points.length]
		return not turn_left(prev, points[min_index], next)
	end



	# Add a vertex to the polygon
	#
	# ~~~
	# var p1 = new Point[Float](0.0, 0.0)
	# var p2 = new Point[Float](5.0, 0.0)
	# var p3 = new Point[Float](0.0, 5.0)
	# var p4 = new Point[Float](5.0, 5.0)
	# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
	# var poly = new ConvexPolygon(arr)
	# var p5 = new Point[Float](2.5, 7.5)
	# assert poly.add_vertex(p5)
	# ~~~
	redef fun add_vertex(p) do
		assert points.length >= 3
		var temp_list = points.clone
		temp_list.add(p)
		var temp_polygon = new ConvexPolygon(temp_list)
		temp_polygon.sort_ccw
		if temp_polygon.is_convex then
			points = temp_polygon.points
			return true
		else
			return false
		end
	end
end