indexing

	description: "[

		A convex polygonal bounding area for the collision detection.
		The vertexes are saved with absolute positioning.
		
		EM_POLYGON_CONVEX_COLLIDABLE is used by EM_POLYGON_COLLIDABLE, which is made of
		convex polygons. You may use EM_POLYGON_CONVEX_COLLIDABLE directly, if the
		polygon is convex. If so, upon generation the polygon will not have to be
		decomposed, which of course takes some time.
		
		If a vertex is modified from the outside, do not forget to call `process_change',
		which computes the new radius of the collidable.
		
		The center should be placed in the center of the polygon. Badly placed centers will
		not be moved by `process_change' (only the radius will be computed), it is the clients
		responsibility to place the center adequately. However a function is provided which
		computes the cifrumcircle of the polygon, called `circumcircle', which returns center
		and radius of the circumcircle.

	]"
	date: "$Date$"
	revision: "$Revision$"

class EM_POLYGON_CONVEX_COLLIDABLE

inherit

	EM_COLLIDABLE
		redefine
			collides_with,
			set_center,
			set_x_y,
			move_by,
			process_changes
		end

create

	make_empty, make_from_relative_list, make_from_absolute_list, make_from_absolute_array, make_from_other

feature -- Initialization

	make_empty is
			-- Creates an empty Polygon
		do
			initialize
			radius := 0
			rotatable := True
			center := create {EM_VECTOR_2D}.make (0, 0)
			last_center := create {EM_VECTOR_2D}.make_from_other (center)
		end

	make_from_relative_list (a_center: EM_VECTOR_2D; vertexes: DS_LINKED_LIST [EM_VECTOR_2D]) is
			-- Creates a polygon from a list of vertexes and a center.
			-- The vertexes are positioned relatively to the center
		require
			a_center_not_void: a_center /= Void
			vertext_not_void: vertexes /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
		do
			create center.make_from_other (a_center)
			last_center := create {EM_VECTOR_2D}.make_from_other (center)
			create vertex_list_absolute.make
			create backup.make
			create cursor.make (vertexes)
			from cursor.start
			until cursor.off
			loop
				backup.force_last (cursor.item)
				vertex_list_absolute.force_last (cursor.item + center)
				cursor.forth
			end
			rotatable := True
			initialize
			process_changes
		end

	make_from_absolute_list (a_center: EM_VECTOR_2D; vertexes: DS_LINKED_LIST [EM_VECTOR_2D]) is
			-- Creates a polygon from a list of vertexes and a center.
			-- The vertexes are positioned absolutely (relatively to the (0,0))
		require
			a_center_not_void: a_center /= Void
			vertext_not_void: vertexes /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
		do
			create center.make_from_other (a_center)
			last_center := create {EM_VECTOR_2D}.make_from_other (center)
			create vertex_list_absolute.make
			create backup.make
			create cursor.make (vertexes)

			from cursor.start
			until cursor.off
			loop
				backup.force_last (cursor.item - center)
				vertex_list_absolute.force_last (create {EM_VECTOR_2D}.make_from_other (cursor.item))
				cursor.forth
			end

			rotatable := True
			initialize
			process_changes
		end

	make_from_absolute_array (a_center: EM_VECTOR_2D; vertexes: ARRAY [EM_VECTOR_2D]) is
			-- Creates a polygon from an array of vertexes and a center.
			-- The vertexes are positioned relatively to the center
		require
			a_center_not_void: a_center /= Void
			vertext_not_void: vertexes /= Void
		local
			i: INTEGER
		do
			create center.make_from_other (a_center)
			last_center := create {EM_VECTOR_2D}.make_from_other (center)
			create vertex_list_absolute.make
			create backup.make

			from i := vertexes.lower
			until i > vertexes.upper
			loop
				backup.force_last (vertexes.item (i) - center)
				vertex_list_absolute.force_last (vertexes.item (i))
				i := i + 1
			end
			initialize
			rotatable := True
			process_changes
		end

	make_from_other (a_polygon: EM_POLYGON_CONVEX_COLLIDABLE) is
			-- creates a polygon from another one
		do
			make_from_absolute_list (a_polygon.center, a_polygon.vertex_list_absolute)
		end

feature -- Status Report

	collides_with (a_collidable: EM_COLLIDABLE): BOOLEAN is
			-- checks if two objects collide
		local
			collision: BOOLEAN
			dx, dy: DOUBLE
			a_circle: EM_CIRCLE_COLLIDABLE
			a_rectangle: EM_RECTANGLE_COLLIDABLE
			a_composition: EM_COLLIDABLE_COMPOSITION
			a_polygonconvex: EM_POLYGON_CONVEX_COLLIDABLE
		do
			dx := a_collidable.center.x - center.x
			dy := a_collidable.center.y - center.y
			if dx*dx + dy*dy <= (radius + a_collidable.radius)*(radius + a_collidable.radius) then
				-- a rough collision was detected
				-- -> check for exact collision

				a_circle ?= a_collidable
				a_rectangle ?= a_collidable
				a_composition ?= a_collidable
				a_polygonconvex ?= a_collidable

				if a_circle /= Void then
					-- the other collidable was a circle
					collision := intersect_polygonconvex_circle (current, a_circle)
				elseif a_rectangle /= Void then
					-- check for collision: circle with rectangle
					collision := intersect_polygonconvex_rectangle (current, a_rectangle)
				elseif a_composition /= Void then
					-- check for collision: polygon with polygon
					collision := intersect_composition_polygonconvex (a_composition, current)
				elseif a_polygonconvex /= Void then
					-- check for collision: polygon with polygon
					collision := intersect_polygonconvex_polygonconvex (current, a_polygonconvex)
				else
					debug
						logger.write_warning ("A convex polygon collided with an unknown collidable, please check if the functions `collides_with' have been redefined correctly.")
					end
				end
			end
			Result := collision
		end

	intersection_points (a_collidable: EM_COLLIDABLE): DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]] is
			-- returns the average collision point and tangential direction of the 2 collidable objects `current' and `a_collidable'
			-- if no intersection points were found, returns `Void'
		local
			a_circle: EM_CIRCLE_COLLIDABLE
			a_rectangle: EM_RECTANGLE_COLLIDABLE
			a_composition: EM_COLLIDABLE_COMPOSITION
			a_polygonconvex: EM_POLYGON_CONVEX_COLLIDABLE
			list: DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]]
		do
			create list.make
			a_circle ?= a_collidable
			a_rectangle ?= a_collidable
			a_composition ?= a_collidable
			a_polygonconvex ?= a_collidable

			if a_circle /= Void then
				-- the other collidable was a circle
				list.force_last (intersection_point_polygonconvex_circle (current, a_circle))
			elseif a_rectangle /= Void then
				-- check for collision: circle with rectangle
				list.force_last (intersection_point_polygonconvex_rectangle (current, a_rectangle))
			elseif a_polygonconvex /= Void then
				-- check for collision: rectangle with polygonconvex
				list.force_last (intersection_point_polygonconvex_polygonconvex (a_polygonconvex, current))
			elseif a_composition /= Void then
				-- check for collision: rectangle with polygon
				list.extend_last (intersection_point_composition_polygonconvex (a_composition, current))
			else
				debug
					logger.write_warning ("A convex polygon was checked for a collision with an unknown collidable, ")
					logger.write_warning ("please check if the functions `intersection_point' have been redefined correctly.")
				end
			end
			Result := list
		end

feature -- Element change

	set_rotatable (v: BOOLEAN) is
			-- sets if the polygon is rotatable
		do
			rotatable := v
		ensure then
			rotatable_set: rotatable = v
		end

	set_x_y (x_position, y_position: DOUBLE) is
			-- sets `center', which also moves the whole object surrounding it
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			dx, dy: DOUBLE
		do
			dx := x_position - center.x
			dy := y_position - center.y

			-- move center
			last_center.set_x (center.x)
			last_center.set_y (center.y)
			center.set_x (x_position)
			center.set_y (y_position)

			-- move polygon
			create cursor.make (vertex_list_absolute)
			from cursor.start
			until cursor.off
			loop
				cursor.item.set_x (cursor.item.x + dx)
				cursor.item.set_y (cursor.item.y + dy)
				cursor.forth
			end
		end

	set_center (a_center: EM_VECTOR_2D) is
			-- sets `center', which also moves the whole object surrounding it
		do
			set_x_y (a_center.x, a_center.y)
		end

	set_center_only (a_center: EM_VECTOR_2D) is
			-- sets `center', does not move the surrounding polygon
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			center_diff: EM_VECTOR_2D
		do
			-- change the backup
			center_diff := - a_center + center
			create cursor.make (backup)
			from cursor.start
			until cursor.off
			loop
				cursor.item.set_x (cursor.item.x + center_diff.x)
				cursor.item.set_y (cursor.item.y + center_diff.y)
				cursor.forth
			end

			-- change the center
			center.set_x (a_center.x)
			center.set_y (a_center.y)
			last_center.set_x (a_center.x)
			last_center.set_y (a_center.y)

			process_changes
		end

	move_by (an_x, a_y: DOUBLE) is
			-- moves the object by an_x, a_y
		do
			set_x_y (center.x + an_x, center.y + a_y)
		end

	process_changes is
			-- computes the radius and sets the value.
			-- uses `vertex_list_absolute' and `center' to compute `radius'
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			d, max: DOUBLE
		do
			create cursor.make (vertex_list_absolute)
			from cursor.start
			until cursor.off
			loop
				d := cursor.item.distance (center)
				if d > max then
					max := d
				end
				cursor.forth
			end
			radius := max
		end

feature -- Access

	vertex_list_absolute: DS_LINKED_LIST [EM_VECTOR_2D]
			-- a list of points of the current polygon, absolute positioning

	vertex_list_relative: DS_LINKED_LIST [EM_VECTOR_2D] is
			-- a list of points of the current polygon, relatively positioned to the center
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			a_list: DS_LINKED_LIST [EM_VECTOR_2D]
		do
			create a_list.make
			create cursor.make (vertex_list_absolute)
			from cursor.start
			until cursor.off
			loop
				a_list.force_last (cursor.item - center)
				cursor.forth
			end
			Result := a_list
		end

	em_polygon: EM_POLYGON is
			-- returns an equivalent EM_POLYGON object
		local
			a_polygon: EM_POLYGON
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
		do
			create a_polygon.make_empty
			create cursor.make (vertex_list_absolute)
			from cursor.start
			until cursor.off
			loop
				a_polygon.extend (cursor.item)
				cursor.forth
			end
			Result := a_polygon
		end

feature -- Drawing

	draw (a_surface: EM_SURFACE) is
			-- Draw `Current' to `a_surface'
			-- The screen clipping is set with `set_draw_clipping'
		local
			a_polygon: EM_POLYGON
			a_circle: EM_CIRCLE
		do

			a_polygon := em_polygon
			a_polygon.set_fill_color (color)
			a_polygon.draw (a_surface)

			if draw_circumcircle then
				create a_circle.make ((center - clipping) * zoom_factor, radius * zoom_factor)
				a_circle.set_filled (False)
				a_circle.set_line_width (1)
				a_circle.set_line_color (draw_circumcircle_color)
				a_circle.draw (a_surface)
			end
		end

feature -- Computation

	center_of_mass: EM_VECTOR_2D is
			-- returns the center of mass
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			cx, cy, t: DOUBLE
			p: EM_VECTOR_2D
		do
			create cursor.make (vertex_list_absolute)
			p := create {EM_VECTOR_2D}.make_from_other (vertex_list_absolute.last)

			-- loop through polygon
			from cursor.start
			until cursor.off
			loop
				t := (p.x * cursor.item.y - cursor.item.x * p.y)
				cx := cx + (cursor.item.x + p.x) * t
				cy := cy + (cursor.item.y + p.y) * t

				p.set_x (cursor.item.x)
				p.set_y (cursor.item.y)
				cursor.forth
			end

			t := 6 * area_signed
			if t = 0 then
				create p.make (0,0)
				-- the polygon had no mass, just take the average of all points
				from cursor.start
				until cursor.off
				loop
					p := p + cursor.item
					cursor.forth
				end
				create Result.make_from_other (p / vertex_list_absolute.count)
			else
				create Result.make (cx/t, cy/t)
			end

		end

	area: DOUBLE is
			-- area of the collidable in pixel^2
		do
			Result := area_signed.abs
		end

	circumcircle: EM_PAIR [EM_VECTOR_2D, DOUBLE] is
			-- a fast approximation of the bounding ball for a point set
			-- based on the algorithm given by [Jack Ritter, 1990]
			-- and softSurfer (www.softsurfer.com)
		local
			cent: EM_VECTOR_2D -- center
			vxmin, vxmax, vymin, vymax: EM_VECTOR_2D
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			dvx, dvy, dv: EM_VECTOR_2D
			rad, rad2, dist, dist2: DOUBLE
		do
			if vertex_list_absolute.count > 0 then
				-- compute the bounding box and save its extreme points
				create cursor.make (vertex_list_absolute)
				cursor.start
				vxmin := cursor.item
				vxmax := cursor.item
				vymin := cursor.item
				vymax := cursor.item

				-- loop through all points to get minimum and maximum in both x and y direction
				from
				until cursor.off
				loop
					if cursor.item.x < vxmin.x then
						vxmin := cursor.item
					end
					if cursor.item.x > vxmax.x then
						vxmax := cursor.item
					end
					if cursor.item.y < vymin.y then
						vymin := cursor.item
					end
					if cursor.item.y > vymax.y then
						vymax := cursor.item
					end

					cursor.forth
				end

				-- vectors from the minimum position to the maximum position
				dvx := vxmax - vxmin
				dvy := vymax - vymin

				if dvx.length_squared >= dvy.length_squared then
					create cent.make_from_other (vxmin + dvx/2)
					rad2 := (vxmax - cent).length_squared
				else
					create cent.make_from_other (vymin + dvy/2)
					rad2 := (vymax - cent).length_squared
				end
				rad := sqrt (rad)

				-- loop through all points again
				from cursor.start
				until cursor.off
				loop
					dv := cursor.item - cent
					dist2 := dv.length_squared

					if dist2 > rad2 then
						-- the vertex is not in the current circle
						rad := (rad + sqrt(dist2)) / 2
						rad2 := rad * rad
						dist := sqrt(dist2)

						-- shift center towards cursor.item
						cent := cent + dv * ((dist-rad)/dist)
					end

					cursor.forth
				end

				create Result.make (cent, rad)
			else
				create Result.make (create {EM_VECTOR_2D}.make (0,0), 0)
			end
		end

	max_distance_to_position (a_position: EM_VECTOR_2D): DOUBLE is
			-- computes the maximal distance to a certain position.
			-- this is used to compute the radius of compositions of collidables
		local
			dist: DOUBLE
		do
			from vertex_list_absolute.start
			until vertex_list_absolute.off
			loop
				dist := vertex_list_absolute.item_for_iteration.distance (a_position)
				if dist > Result then
					Result := dist
				end
				vertex_list_absolute.forth
			end
		end

	duplicate: like Current is
			-- returns an equivalent copy of the collidable (just the position and borders)
		do
			Result := duplicate_polygon
		end

	duplicate_polygon: EM_POLYGON_CONVEX_COLLIDABLE is
			-- returns an equivalent copy of the object as a EM_POLYGON_CONVEX_COLLIDABLE
		do
			create Result.make_from_absolute_list (center, vertex_list_absolute)
		end

feature {NONE} -- Implementation

	turn_around_center (an_angle: DOUBLE; a_center: EM_VECTOR_2D) is
			-- turn the polygon by a certain angle
		local
			cursor, cursor2: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			pos: EM_VECTOR_2D
		do
			center := center.rotation (a_center, an_angle)
			create cursor.make (backup)
			create cursor2.make (vertex_list_absolute)
			from cursor.start
				cursor2.start
			until cursor.off or cursor2.off
			loop
				-- set new position
				pos := cursor.item.rotation_around_zero (angle + an_angle)
				cursor2.item.set_x (pos.x + center.x)
				cursor2.item.set_y (pos.y + center.y)
				cursor2.forth
				cursor.forth
			end
		end

	is_convex: BOOLEAN is
			-- checks if the polygon is convex
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			p_prev, p_curr, p_next: EM_VECTOR_2D
			clockwise, counterclockwise, reverse: BOOLEAN
			next_y: DOUBLE
		do
			Result := True
			if vertex_list_absolute.count > 3 then
				if has_crossing then
					Result := False
				else
					create cursor.make (vertex_list_absolute)
					cursor.finish
					cursor.back
					-- second last
					create p_prev.make_from_other (cursor.item)
					cursor.forth
					-- last
					create p_curr.make_from_other (cursor.item)
					create p_next.make (0,0)

					from cursor.start
					until cursor.off or Result = False
					loop
						p_next.set_x (cursor.item.x)
						p_next.set_y (cursor.item.y)

						-- check if the 3 points (p_prev, p_curr, p_next) are going clockwise or counterclockwise
						if p_curr.x /= p_next.x or p_curr.y /= p_next.x then
							-- current and next were not the same
							if p_prev.x = p_curr.x then
								-- if the 2 points are along the y-axis
								if p_next.x = p_curr.x then
									-- if the third is aswell
									if (p_curr.y - p_prev.y).sign /= (p_next.y - p_curr.y).sign then
										-- there was a 180° change in direction
										reverse := True
									else
										-- just ignore this step, all points are aligned
									end
								else
									-- check if the third point is to the left or the right of the line
									if (p_curr.y - p_prev.y).sign = 1 then
										-- going upwards
										if p_next.x < p_curr.x then
											counterclockwise := True
										else
											clockwise := True
										end
									else
										-- going downwards
										if p_next.x < p_curr.x then
											clockwise := True
										else
											counterclockwise := True
										end
									end
								end
							else
								next_y := value_at_position (p_next.x, p_prev, p_curr)
								if p_curr.x - p_prev.x > 0 then
									-- going right
									if p_next.y > next_y then
										counterclockwise := True
									elseif p_next.y < next_y then
										clockwise := True
									end
								else
									-- going left
									if p_next.y > next_y then
										clockwise := True
									elseif p_next.y < next_y then
										counterclockwise := True
									end
								end
							end

							-- move forth
							p_prev.set_x (p_curr.x)
							p_prev.set_y (p_curr.y)
							p_curr.set_x (p_next.x)
							p_curr.set_y (p_next.y)
						end

						-- check if we have counterclockwise and clockwise steps
						if clockwise and counterclockwise then
							Result := False
						end

						cursor.forth
					end

					-- check for special cases
					if reverse and (clockwise or counterclockwise) then
						-- there was a reverse in direction and a bend, so the polygon can not be convex
						Result := False
					end
				end
			end
		end

	has_crossing: BOOLEAN is
			-- do 2 lines of the polygon cross each other?
		local
			cursor1, cursor2: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			p1, p2, p3, p4: EM_VECTOR_2D
			first_run: BOOLEAN
			a1, b1, c1, a2, b2, c2, det, tx, ty: DOUBLE
		do
			if vertex_list_absolute.count > 3 then
				first_run := True

				create cursor1.make (vertex_list_absolute)
				create cursor2.make (vertex_list_absolute)
				cursor1.finish
				p1 := cursor1.item
				cursor1.start

				from
				until cursor1.index > vertex_list_absolute.count - 2 or Result = True
				loop
					p2 := cursor1.item

					cursor2.go_i_th (cursor1.index+1)
					p3 := cursor2.item
					cursor2.forth

					from
					until cursor2.off or Result = True
					loop
						p4 := cursor2.item

						-- check if there is an intersection of the line `p1'-`p2' to `p3'-`p4'
						a1 := p2.y - p1.y
						b1 := p1.x - p2.x
						c1 := a1 * p1.x + b1 * p1.y
						a2 := p4.y - p3.y
						b2 := p3.x - p4.x
						c2 := a2 * p3.x + b2 * p3.y
						det := a1*b2 - a2*b1

						if det /= 0 then
							-- the lines are not parallel
							tx := (b2*c1 - b1*c2) / det
							ty := (a1*c2 - a2*c1) / det

							if p1.x.min(p2.x)-eps <= tx and tx <= p1.x.max(p2.x)+eps and
								p1.y.min(p2.y)-eps <= ty and ty <= p1.y.max(p2.y)+eps and
								p3.x.min(p4.x)-eps <= tx and tx <= p3.x.max(p4.x)+eps and
								p3.y.min(p4.y)-eps <= ty and ty <= p3.y.max(p4.y)+eps then
								Result := True
							end
						end

						p3 := p4
						cursor2.forth

						if first_run and then cursor2.is_last then
							first_run := False
							cursor2.forth
						end
					end
					p1 := p2
					cursor1.forth
				end
			end
		end

	backup: DS_LINKED_LIST [EM_VECTOR_2D]
			-- a backup of the original polygon (relative positioning), this is saved at an angle of 0

	area_signed: DOUBLE is
			-- internal area computation which returns the sign (determines, if the polygon is ordered
			-- clockwise or counterclockwise)
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			a: DOUBLE
			p: EM_VECTOR_2D
		do
			create cursor.make (vertex_list_absolute)
			p := create {EM_VECTOR_2D}.make_from_other (vertex_list_absolute.last)

			-- loop through polygon
			from cursor.start
			until cursor.off
			loop
				a := a + p.x * cursor.item.y - p.y * cursor.item.x
				p.set_x (cursor.item.x)
				p.set_y (cursor.item.y)
				cursor.forth
			end

			Result := a / 2
		end

invariant

	polygon_is_convex: is_convex
	vertex_list_not_void: vertex_list_absolute /= Void and vertex_list_relative /= Void
	backup_not_void: backup /= Void
	backup_count_correct: backup.count = vertex_list_absolute.count

end