indexing

	description: "[

		Implementation of some collision functions, mainly to handle cross product computations of all collidables

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

class EM_COLLISION_IMPLEMENTATION

inherit

	DOUBLE_MATH
		export {NONE} all end

feature {NONE} -- Intersection Checks (check if 2 collidables overlap)

	intersect_circle_circle (a_circle, b_circle: EM_CIRCLE_COLLIDABLE): BOOLEAN is
			-- returns true, if two circles collide with each other
		require
			a_circle_not_void: a_circle /= Void
			b_circle_not_void: b_circle /= Void
		do
			Result := (a_circle.center.distance (b_circle.center) <= a_circle.radius + b_circle.radius)
		end

	intersect_circle_rectangle (a_circle: EM_CIRCLE_COLLIDABLE; a_rectangle: EM_RECTANGLE_COLLIDABLE): BOOLEAN is
			-- returns true, if a rectangle collides with a circle
		require
			a_rectangle_not_void: a_rectangle /= Void
			a_circle_not_void: a_circle /= Void
		local
			collision: BOOLEAN
		do
			if
				is_between (a_rectangle.border_left - a_circle.radius, a_rectangle.border_right + a_circle.radius, a_circle.center.x) and
				is_between (a_rectangle.border_top - a_circle.radius, a_rectangle.border_bottom + a_circle.radius, a_circle.center.y)
			then
				collision := true
				-- the circle collides with the rectangle, if it is not in one of the unchecked corners areas
				if a_circle.center.x < a_rectangle.corner_top_left.x and a_circle.center.y < a_rectangle.corner_top_left.y
					and then a_circle.center.distance (a_rectangle.corner_top_left) >= a_circle.radius then
					-- checked top left corner
					collision := false
				elseif a_circle.center.x < a_rectangle.corner_bottom_left.x and a_circle.center.y > a_rectangle.corner_bottom_left.y
					and then a_circle.center.distance (a_rectangle.corner_bottom_left) >= a_circle.radius then
					-- checked bottom left corner
					collision := false
				elseif a_circle.center.x > a_rectangle.corner_top_right.x and a_circle.center.y < a_rectangle.corner_top_right.y
					and then a_circle.center.distance (a_rectangle.corner_top_right) >= a_circle.radius then
					-- checked top right corner
					collision := false
				elseif a_circle.center.x > a_rectangle.corner_bottom_right.x and a_circle.center.y > a_rectangle.corner_bottom_right.y
					and then a_circle.center.distance (a_rectangle.corner_bottom_right) >= a_circle.radius then
					-- checked bottom right corner
					collision := false
				end
			end
			Result := collision
		end

	intersect_rectangle_rectangle (a_rectangle, b_rectangle: EM_RECTANGLE_COLLIDABLE): BOOLEAN is
			-- returns true, if the given rectangles overlap
		require
			a_rectangle_not_void: a_rectangle /= Void
			b_rectangle_not_void: b_rectangle /= Void
		do
			if
				intersect_interval_interval (a_rectangle.border_left, a_rectangle.border_right, b_rectangle.border_left, b_rectangle.border_right) and
				intersect_interval_interval (a_rectangle.border_top, a_rectangle.border_bottom, b_rectangle.border_top, b_rectangle.border_bottom)
			then
				Result := True
			end
		end

	intersect_polygonconvex_rectangle (a_polygon: EM_POLYGON_CONVEX_COLLIDABLE; a_rectangle: EM_RECTANGLE_COLLIDABLE): BOOLEAN is
			-- returns true, if the given collidables overlap
		require
			a_polygon_not_void: a_polygon /= Void
			a_rectangle_not_void: a_rectangle /= Void
		do
			Result := intersect_polygonconvex_polygonconvex (a_polygon, a_rectangle.em_polygon_convex_collidable)
		end

	intersect_polygonconvex_circle (a_polygon: EM_POLYGON_CONVEX_COLLIDABLE; a_circle: EM_CIRCLE_COLLIDABLE): BOOLEAN is
			-- returns true, if the given collidables overlap
			-- see http://www.harveycartel.org/metanet/tutorials/tutorialA.html for details
		require
			a_polygon_not_void: a_polygon /= Void
			a_circle_not_void: a_circle /= Void
		local
			vertex_start, vertex_end: EM_VECTOR_2D
			intersect, max_set, min_set: BOOLEAN
			cursor1, cursor2: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			dx, dy, distance, min, max, len: DOUBLE
		do
			-- save last vertex of polygon
			create vertex_start.make_from_other (a_polygon.vertex_list_absolute.last)
			create vertex_end.make (0,0)

			-- we assume, that both collidables intersect, until shown, that they can't intersect
			intersect := True

			-- loop through the polygons edges
			create cursor1.make (a_polygon.vertex_list_absolute)
			create cursor2.make (a_polygon.vertex_list_absolute)

			from cursor1.start
			until cursor1.off or not intersect
			loop
				vertex_end.set_x (cursor1.item.x)
				vertex_end.set_y (cursor1.item.y)

				-- check the edge from `vertex_start' to `vertex_end'
				dx := vertex_end.x - vertex_start.x
				dy := vertex_end.y - vertex_start.y
				len := sqrt(dx*dx + dy*dy)

				min := 0
				max := 0

				-- check if length = 0. Actually should not happen if the polygons are correct
				if len /= 0 then
					-- Loop through the vertexes and compare them with the current edge (`vertex_start' to `vertex_end')
					from cursor2.start
					until cursor2.off or len = 0
					loop
						distance := ((dx*(vertex_start.y-cursor2.item.y))-(dy*(vertex_start.x-cursor2.item.x))) / len
						if distance > max then
							max := distance
						elseif distance < min then
							min := distance
						end
						cursor2.forth
					end

					-- distance from `vertex_start' in direction of (dx, dy)
					distance := ((dx*(vertex_start.y-a_circle.center.y))-(dy*(vertex_start.x-a_circle.center.x))) / len

					if not intersect_interval_interval (min, max, distance - a_circle.radius, distance + a_circle.radius) then
						intersect := False
					end
				end

				vertex_start.make_from_other (vertex_end)
				cursor1.forth
			end

			if intersect then
				-- If we still have an intersection it is still possible, that some overlappings have been missed
				-- check intersections from the vertices of the polygon to the center of the circle

				from cursor1.start
				until cursor1.off or not intersect
				loop
					-- check the edge from a polygon vertex to the center of the circle
					dx := - (cursor1.item.y - a_circle.center.y)
					dy := cursor1.item.x - a_circle.center.x
					len := sqrt(dx*dx + dy*dy)

					min_set := False
					max_set := False

					-- Loop through the vertexes and compare them with the current edge (`vertex_start' to `vertex_end')
					from cursor2.start
					until cursor2.off
					loop
						if len /= 0 then
							-- distance from center to projection
							distance := ((dx*(a_circle.center.y-cursor2.item.y))-(dy*(a_circle.center.x-cursor2.item.x))) / len
							-- check for maximum or minimum
							if not max_set or (max_set and distance > max) then
								max := distance
								max_set := True
							end

							if not min_set or (min_set and distance < min) then
								min := distance
								min_set := True
							end
						end
						cursor2.forth
					end

					if not intersect_interval_interval (min, max, -a_circle.radius, a_circle.radius) then
						intersect := False
					end
					vertex_start.make_from_other (vertex_end)
					cursor1.forth
				end
			end
			Result := intersect
		end

	intersect_polygonconvex_polygonconvex (a_polygon, b_polygon: EM_POLYGON_CONVEX_COLLIDABLE): BOOLEAN is
			-- returns true, if the given collidables overlap
		require
			a_polygon_not_void: a_polygon /= Void
			b_polygon_not_void: b_polygon /= Void
		do
			Result := intersect_polygonconvex_polygonconvex_internal (a_polygon, b_polygon) and intersect_polygonconvex_polygonconvex_internal (b_polygon, a_polygon)
		end

	intersect_polygonconvex_polygonconvex_internal (a_polygon, b_polygon: EM_POLYGON_CONVEX_COLLIDABLE): BOOLEAN is
			-- checks if polygon a collides with polygon b (just one direction. must be called in both directions!
			-- see `intersect_polygonconvex_polygonconvex' on how to use.
		require
			a_polygon_not_void: a_polygon /= Void
			b_polygon_not_void: b_polygon /= Void
		local
			vertex_start, vertex_end: EM_VECTOR_2D
			intersect, found_before, found_after, max_set, min_set, found: BOOLEAN
			cursor1, cursor2, cursor3: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			dx, dy, distance, min, max: DOUBLE
		do
			-- save last vertex of polygon
			create vertex_start.make_from_other (a_polygon.vertex_list_absolute.last)
			create vertex_end.make (0,0)

			-- we assume, that both collidables intersect, until shown, that they can't intersect
			intersect := True

			-- loop through the first polygons edges
			create cursor1.make (a_polygon.vertex_list_absolute)
			create cursor2.make (b_polygon.vertex_list_absolute)
			create cursor3.make (a_polygon.vertex_list_absolute)
			from cursor1.start
			until cursor1.off or not intersect
			loop
				vertex_end.set_x (cursor1.item.x)
				vertex_end.set_y (cursor1.item.y)

				found_before := False
				found_after := False
				max_set := False
				min_set := False

				-- check the edge from `vertex_start' to `vertex_end'
				dx := vertex_end.x - vertex_start.x
				dy := vertex_end.y - vertex_start.y

				-- compute distance from other vertices to the line of vertes_start to vertex_end in order to check for overlappings
				from cursor2.start
				until cursor2.off or (found_after and found_before)
				loop
					distance := ((dx*(vertex_start.y-cursor2.item.y))-(dy*(vertex_start.x-cursor2.item.x)))
					if distance < 0 then
						found_before := True
					elseif distance > 0 then
						found_after := True
					else
						-- found between
						found_before := True
						found_after := True
					end

					-- check for maximum or minimum
					if not max_set or (max_set and distance > max) then
						max := distance
						max_set := True
					end

					if not min_set or (min_set and distance < min) then
						min := distance
						min_set := True
					end

					cursor2.forth
				end

				if (not (found_after and found_before)) then
					-- no overlapping found till now, still possible for other vertices of `a_polygon' to be between min and max

					found := False

					-- loop through all vertices of `a_polygon'
					from cursor3.start
					until cursor3.off or found
					loop
						distance := (dx*(vertex_start.y-cursor3.item.y)-dy*(vertex_start.x-cursor3.item.x))
						if intersect_interval_interval (0, distance, min, max) then
							-- we found an intersection, leave loop
							found := True
						end
						cursor3.forth
					end

					if found = False then
						intersect := False
					end
				end

				-- clean up for next edge
				vertex_start.set_x (vertex_end.x)
				vertex_start.set_y (vertex_end.y)
				cursor1.forth
			end
			Result := intersect
		end

	intersect_composition_polygonconvex (a_composition: EM_COLLIDABLE_COMPOSITION; a_polygon: EM_POLYGON_CONVEX_COLLIDABLE): BOOLEAN is
			-- returns true, if the given collidables overlap
		require
			a_composition_not_void: a_composition /= Void
			a_polygon_not_void: a_polygon /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
		do
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off or Result = True
			loop
				Result := a_polygon.collides_with (cursor.item)
				cursor.forth
			end
		end

	intersect_composition_circle (a_composition: EM_COLLIDABLE_COMPOSITION; a_circle: EM_CIRCLE_COLLIDABLE): BOOLEAN is
			-- returns true, if the given collidables overlap
		require
			a_composition_not_void: a_composition /= Void
			a_circle_not_void: a_circle /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
		do
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off or Result = True
			loop
				Result := a_circle.collides_with (cursor.item)
				cursor.forth
			end
		end

	intersect_composition_composition (a_composition, b_composition: EM_COLLIDABLE_COMPOSITION): BOOLEAN is
			-- returns true, if the given collidables overlap
		require
			a_composition_not_void: a_composition /= Void
			b_composition_not_void: b_composition /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
		do
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off or Result = True
			loop
				Result := cursor.item.collides_with (b_composition)
				cursor.forth
			end
		end

	intersect_composition_rectangle (a_composition: EM_COLLIDABLE_COMPOSITION; a_rectangle: EM_RECTANGLE_COLLIDABLE): BOOLEAN is
			-- returns true, if the given collidables overlap
		require
			a_composition_not_void: a_composition /= Void
			a_rectangle_not_void: a_rectangle /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
		do
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off or Result = True
			loop
				Result := a_rectangle.collides_with (cursor.item)
				cursor.forth
			end
		end

feature {NONE} -- Intersection Point

	intersection_point_circle_circle (a_circle, b_circle: EM_CIRCLE_COLLIDABLE): EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D] is
			-- returns the average intersection point and tangential angle.
			-- if not found, returns a pair of Voids
		require
			a_circle_not_void: a_circle /= Void
			b_circle_not_void: b_circle /= Void
			circles_must_intersect: intersect_circle_circle (a_circle, b_circle) = True
		local
			x, d: DOUBLE
			position: EM_VECTOR_2D
			direction: EM_DIRECTION_2D
		do
			-- distance of centers
			d := a_circle.center.distance (b_circle.center)
			if d /= 0 then
				-- distance of intersection from a_circle
				x := (d*d - a_circle.radius * a_circle.radius + b_circle.radius * b_circle.radius) / (2 * d)
				create position.make_from_other (b_circle.center - a_circle.center)
				create direction.make_from_coefficients (- position.y, position.x)
				position := - position * x / d + b_circle.center
				if position.distance (a_circle.center) < a_circle.radius then
					Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (position, direction)
				else
					Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
				end
			else
				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
			end
		end

	intersection_point_circle_rectangle (a_circle: EM_CIRCLE_COLLIDABLE; a_rectangle: EM_RECTANGLE_COLLIDABLE): EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D] is
			-- returns the average intersection point and tangential angle.
			-- if not found, returns a pair of Voids
		require
			a_circle_not_void: a_circle /= Void
			a_rectangle_not_void: a_rectangle /= Void
			circles_must_intersect: intersect_circle_rectangle (a_circle, a_rectangle) = True
		local
			list: DS_LINKED_LIST [EM_VECTOR_2D]
			pos, dir: EM_VECTOR_2D
			c: INTEGER
			is_horizontal: BOOLEAN
		do
			create list.make
			list.extend_last (intersection_point_circle_line (a_circle, a_rectangle.corner_top_left, a_rectangle.corner_top_right))
			if list.count < 2 then
				list.extend_last (intersection_point_circle_line (a_circle, a_rectangle.corner_bottom_right, a_rectangle.corner_bottom_left))
				if list.count < 2 then
					if list.count = 1 then is_horizontal := true end
					c := list.count
					list.extend_last (intersection_point_circle_line (a_circle, a_rectangle.corner_top_right, a_rectangle.corner_bottom_right))
					if list.count < 2 then
						list.extend_last (intersection_point_circle_line (a_circle, a_rectangle.corner_bottom_left, a_rectangle.corner_top_left))
						if list.count - c = 1 then is_horizontal := false end
					end
				end
			end

			if list.count >= 2 then
				pos := (list.item (1) + list.item (2)) / 2
				dir := pos - list.item(1)
				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (pos, create {EM_DIRECTION_2D}.make_from_coefficients (dir.x, dir.y))
			elseif list.count = 1 then
				-- since we don't know the direction anymore of there is only one intersection point (in case of a tangent),
				-- that informationn was saved in `is_horizontal'
				if is_horizontal then
					Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (list.item(1), create {EM_DIRECTION_2D}.make)
				else
					Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (list.item(1), create {EM_DIRECTION_2D}.make_from_coefficients (0, 1))
				end
			else
				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
			end
		end

	intersection_point_rectangle_rectangle (a_rectangle, b_rectangle: EM_RECTANGLE_COLLIDABLE): EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_rectangle_not_void: a_rectangle /= Void
			b_rectangle_not_void: b_rectangle /= Void
			rectangles_collide: intersect_rectangle_rectangle (a_rectangle, b_rectangle) = True
		local
			pos1, pos2: EM_VECTOR_2D
		do
			Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
			if is_between (a_rectangle.center.x - a_rectangle.half_width, a_rectangle.center.x + a_rectangle.half_width, b_rectangle.center.x - b_rectangle.half_width) then
				-- left corner of `b_rectangle' is in the area of `a_rectangle' in x-direction
				if is_between (a_rectangle.center.x - a_rectangle.half_width, a_rectangle.center.x + a_rectangle.half_width, b_rectangle.center.x + b_rectangle.half_width) then
					-- `b_rectangle' is in between of `a_rectangle' in x-direction
					if b_rectangle.border_top < a_rectangle.border_top then
						if b_rectangle.border_bottom < a_rectangle.border_bottom then
							Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (b_rectangle.center.x, a_rectangle.border_top), create {EM_DIRECTION_2D}.make)
						else
							Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (b_rectangle.center.x, a_rectangle.center.y), create {EM_DIRECTION_2D}.make)
						end
					elseif b_rectangle.border_bottom > a_rectangle.border_bottom then
						Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (b_rectangle.center.x, a_rectangle.border_bottom), create {EM_DIRECTION_2D}.make)
					else
					-- `b_rectangle' is included in `a_rectangle'
						Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
					end
				else
					-- `b_rectangle' is on the right hand side of `a_rectangle'
					if b_rectangle.border_top < a_rectangle.border_top then
						if b_rectangle.border_bottom < a_rectangle.border_bottom then
							-- `b_rectangle' is on the top right side of `a_rectangle'
							pos1 := create {EM_VECTOR_2D}.make (b_rectangle.border_left, a_rectangle.border_top)
							pos2 := create {EM_VECTOR_2D}.make (a_rectangle.border_right, b_rectangle.border_bottom)
							pos1 := (pos1 + pos2) / 2
							pos2 := pos1 - pos2
							Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (pos1, create {EM_DIRECTION_2D}.make_from_coefficients (pos2.x, pos2.y))
						else
							-- `a_rectangle' is included on the left side of `b_rectangle'
							Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (b_rectangle.border_left, a_rectangle.center.y), create {EM_DIRECTION_2D}.make_from_coefficients (0, 1))
						end
					else
						if b_rectangle.border_bottom > a_rectangle.border_bottom then
							-- `b_rectangle' is on the bottom left side of `a_rectangle'
							pos1 := create {EM_VECTOR_2D}.make (b_rectangle.border_left, a_rectangle.border_bottom)
							pos2 := create {EM_VECTOR_2D}.make (a_rectangle.border_right, b_rectangle.border_top)
							pos1 := (pos1 + pos2) / 2
							pos2 := pos1 - pos2
							Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (pos1, create {EM_DIRECTION_2D}.make_from_coefficients (pos2.x, pos2.y))
						else
							-- `b_rectangle' is included in the right side of `a_rectangle'
							Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (a_rectangle.border_right, b_rectangle.center.y), create {EM_DIRECTION_2D}.make_from_coefficients (0, 1))
						end
					end
				end
			elseif is_between (a_rectangle.center.x - a_rectangle.half_width, a_rectangle.center.x + a_rectangle.half_width, b_rectangle.center.x + b_rectangle.half_width) then
				-- right corner of `b_rectangle' is in the area of `a_rectangle' in x-direction
				Result := intersection_point_rectangle_rectangle (b_rectangle, a_rectangle)
			else
				-- `b_rectangle' surrounds `a_rectangle' in x-direction
				if a_rectangle.border_top < b_rectangle.border_top then
					if a_rectangle.border_bottom < b_rectangle.border_bottom then
						Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (a_rectangle.center.x, b_rectangle.border_top), create {EM_DIRECTION_2D}.make)
					else
						Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (a_rectangle.center.x, b_rectangle.center.y), create {EM_DIRECTION_2D}.make)
					end
				elseif a_rectangle.border_bottom > b_rectangle.border_bottom then
					Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (create {EM_VECTOR_2D}.make (a_rectangle.center.x, b_rectangle.border_bottom), create {EM_DIRECTION_2D}.make)
				else
					-- `a_rectangle' is included in `b_rectangle'
					Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
				end
			end
		end

	intersection_point_polygonconvex_circle (a_polygon: EM_POLYGON_CONVEX_COLLIDABLE; a_circle: EM_CIRCLE_COLLIDABLE): EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_polygon_not_void: a_polygon /= Void
			a_circle_not_void: a_circle /= Void
			collidables_collide: intersect_polygonconvex_circle (a_polygon, a_circle)
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			pos1, pos2: EM_VECTOR_2D
			intersections: DS_LINKED_LIST [EM_VECTOR_2D]
		do
			create cursor.make (a_polygon.vertex_list_absolute)
			create pos1.make_from_other (a_polygon.vertex_list_absolute.last)
			create intersections.make

			from cursor.start
			until cursor.off or intersections.count >= 2
			loop
				pos2 := cursor.item

				-- check for intersection of the edge from `pos1' to `pos2' with `a_circle'
				intersections.extend_last (intersection_point_circle_line (a_circle, pos1, pos2))

				pos1.set_x (pos2.x)
				pos1.set_y (pos2.y)
				cursor.forth
			end

			if intersections.count < 2 then
				-- no intersection found, return empty pair
				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
			else
				-- at least 2 intersections were found, take the first 2 and build an average
				pos1 := intersections.first
				pos2 := intersections.item (2)
				-- average
				pos1 := (pos1 + pos2) / 2
				-- direction
				pos2 := pos1 - pos2

				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (pos1, create {EM_DIRECTION_2D}.make_from_coefficients (pos2.x, pos2.y))
			end
		end

	intersection_point_polygonconvex_rectangle (a_polygon: EM_POLYGON_CONVEX_COLLIDABLE; a_rectangle: EM_RECTANGLE_COLLIDABLE): EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_polygon_not_void: a_polygon /= Void
			a_rectangle_not_void: a_rectangle /= Void
			collidables_collide: intersect_polygonconvex_rectangle (a_polygon, a_rectangle)
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			pos1, pos2, intersection: EM_VECTOR_2D
			intersections: DS_LINKED_LIST [EM_VECTOR_2D]
		do
			create cursor.make (a_polygon.vertex_list_absolute)
			create pos1.make_from_other (a_polygon.vertex_list_absolute.last)
			create intersections.make

			from cursor.start
			until cursor.off or intersections.count >= 2
			loop
				pos2 := cursor.item

				-- check for intersection of the edge from `pos1' to `pos2' with `a_rectangle'
				intersection := intersection_point_line_line (pos1, pos2, a_rectangle.corner_top_left, a_rectangle.corner_top_right)
				if intersection /= Void then
					intersections.force_last (intersection)
				end
				intersection := intersection_point_line_line (pos1, pos2, a_rectangle.corner_top_right, a_rectangle.corner_bottom_right)
				if intersection /= Void then
					intersections.force_last (intersection)
				end
				intersection := intersection_point_line_line (pos1, pos2, a_rectangle.corner_bottom_right, a_rectangle.corner_bottom_left)
				if intersection /= Void then
					intersections.force_last (intersection)
				end
				intersection := intersection_point_line_line (pos1, pos2, a_rectangle.corner_bottom_left, a_rectangle.corner_top_left)
				if intersection /= Void then
					intersections.force_last (intersection)
				end

				pos1.set_x (pos2.x)
				pos1.set_y (pos2.y)
				cursor.forth
			end

			if intersections.count < 2 then
				-- no intersection found, return empty pair
				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
			else
				-- at least 2 intersections were found, take the first 2 and build an average
				pos1 := intersections.item (1)
				pos2 := intersections.item (2)
				-- average
				pos1 := (pos1 + pos2) / 2
				-- direction
				pos2 := pos1 - pos2

				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (pos1, create {EM_DIRECTION_2D}.make_from_coefficients (pos2.x, pos2.y))
			end
		end

	intersection_point_polygonconvex_polygonconvex (a_polygon, b_polygon: EM_POLYGON_CONVEX_COLLIDABLE): EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_polygon_not_void: a_polygon /= Void
			b_polygon_not_void: b_polygon /= Void
			collidables_collide: intersect_polygonconvex_polygonconvex (a_polygon, b_polygon)
		local
			cursor1, cursor2: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			pos1, pos2, intersection, pos3, pos4: EM_VECTOR_2D
			intersections: DS_LINKED_LIST [EM_VECTOR_2D]
		do
			create cursor1.make (a_polygon.vertex_list_absolute)
			create cursor2.make (b_polygon.vertex_list_absolute)
			create pos1.make_from_other (a_polygon.vertex_list_absolute.last)
			create intersections.make

			from cursor1.start
			until cursor1.off or intersections.count >= 2
			loop
				pos2 := create {EM_VECTOR_2D}.make_from_other (cursor1.item)

				-- check for intersection of the edge from `pos1' to `pos2' with `b_polygon'
				pos3 := create {EM_VECTOR_2D}.make_from_other (b_polygon.vertex_list_absolute.last)
				from cursor2.start
				until cursor2.off
				loop
					pos4 := create {EM_VECTOR_2D}.make_from_other (cursor2.item)

					intersection := intersection_point_line_line (pos1, pos2, pos3, pos4)
					if intersection /= Void then
						intersections.force_last (intersection)
					end

					pos3.set_x (pos4.x)
					pos3.set_y (pos4.y)
					cursor2.forth
				end

				pos1.set_x (pos2.x)
				pos1.set_y (pos2.y)
				cursor1.forth
			end

			if intersections.count < 2 then
				-- no intersection found, return empty pair
				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void)
			else
				-- at least 2 intersections were found, take the first 2 and build an average
				pos1 := intersections.item (1)
				pos2 := intersections.item (2)
				-- average
				pos1 := (pos1 + pos2) / 2
				-- direction
				pos2 := pos1 - pos2

				Result := create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (pos1, create {EM_DIRECTION_2D}.make_from_coefficients (pos2.x, pos2.y))
			end
		end

	intersection_point_composition_circle (a_composition: EM_COLLIDABLE_COMPOSITION; a_circle: EM_CIRCLE_COLLIDABLE): DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_composition_not_void: a_composition /= Void
			a_circle_not_void: a_circle /= Void
			collidables_collide: intersect_composition_circle (a_composition, a_circle)
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
			coll: DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]]
		do
			create Result.make
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off
			loop
				if a_circle.collides_with (cursor.item) then
					coll := a_circle.intersection_points (cursor.item)
					if coll /= Void then
						-- a collision point was found, add to list
						Result.extend_last (coll)
					end
				end
				cursor.forth
			end

			if Result = Void then
				create Result.make
				Result.force_last (create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void))
			end
		end

	intersection_point_composition_rectangle (a_composition: EM_COLLIDABLE_COMPOSITION; a_rectangle: EM_RECTANGLE_COLLIDABLE): DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_composition_not_void: a_composition /= Void
			a_rectangle_not_void: a_rectangle /= Void
			collidables_collide: intersect_composition_rectangle (a_composition, a_rectangle)
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
			coll: DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]]
		do
			create Result.make
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off
			loop
				if a_rectangle.collides_with (cursor.item) then
					coll := a_rectangle.intersection_points (cursor.item)
					if coll /= Void then
						-- a collision point was found, add to list
						Result.extend_last (coll)
					end
				end
				cursor.forth
			end

			if Result = Void then
				create Result.make
				Result.force_last (create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void))
			end
		end

	intersection_point_composition_polygonconvex (a_composition: EM_COLLIDABLE_COMPOSITION; a_polygon: EM_POLYGON_CONVEX_COLLIDABLE): DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_polygon_not_void: a_polygon /= Void
			a_composition_not_void: a_composition /= Void
			collidables_collide: intersect_composition_polygonconvex (a_composition, a_polygon)
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
			coll: DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]]
		do
			create Result.make
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off
			loop
				if a_polygon.collides_with (cursor.item) then
					coll := a_polygon.intersection_points (cursor.item)
					if coll /= Void then
						-- a collision point was found, add to list
						Result.extend_last (coll)
					end
				end
				cursor.forth
			end

			if Result = Void then
				create Result.make
				Result.force_last (create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void))
			end
		end

	intersection_point_composition_composition (a_composition, b_composition: EM_COLLIDABLE_COMPOSITION): DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]] is
			-- returns the average intersection point and tangential angle.
			-- if not found (in case of complete inclusion), returns a pair of Voids
		require
			a_composition_not_void: a_composition /= Void
			b_composition_not_void: b_composition /= Void
			collidables_collide: intersect_composition_composition (a_composition, b_composition)
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLIDABLE]
			coll: DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]]
		do
			create Result.make
			create cursor.make (a_composition.collidables)
			from cursor.start
			until cursor.off
			loop
				if cursor.item.collides_with (b_composition) then
					coll := cursor.item.intersection_points (b_composition)
					if coll /= Void then
						-- a collision point was found, add to list
						Result.extend_last (coll)
					end
				end
				cursor.forth
			end

			if Result = Void then
				create Result.make
				Result.force_last (create {EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]}.make (Void, Void))
			end
		end

feature {NONE} -- Computation

	intersection_point_line_line (line_1_start, line_1_end, line_2_start, line_2_end: EM_VECTOR_2D): EM_VECTOR_2D is
			-- Returns the intersection point of 2 lines if there is one, otherwise returns `Void'
			-- see for more details: http://mathworld.wolfram.com/Line-LineIntersection.html
		require
			line_1_not_void: line_1_start /= Void and line_1_end /= Void
			line_2_not_void: line_2_start /= Void and line_2_end /= Void
			line_1_valid: line_1_start.x /= line_1_end.x or line_1_start.y /= line_1_end.y
		local
			y, a, c, x: DOUBLE
			dx1, dx2: DOUBLE
			pos: EM_VECTOR_2D
			b: BOOLEAN
		do
			dx1 := line_1_end.x-line_1_start.x
			dx2 := line_2_end.x-line_2_start.x
			if dx1 = 0 then
				-- line 1 is along the y-axis.
				if dx2 = 0 then
					-- both lines are along the y-axis
					-- this means that we only can have an intersection, if both x'es are the same
					if line_1_start.x = line_2_start.x then
						-- we have infinite intersections, check if they overlap
						if intersect_interval_interval (line_1_start.y, line_1_end.y, line_2_start.y, line_2_end.y) then
							create pos.make (line_1_start.x, line_1_start.y)
							b := true
						end
					end
				else
					-- just the first line is along the y-axis
					y := value_at_position (line_1_start.x, line_2_start, line_2_end)
					if is_between_first_equal (line_2_start.x, line_2_end.x, line_1_start.x) and is_between_first_equal (line_1_start.y, line_1_end.y, y) then
						b := true
						create pos.make (line_1_start.x, y)
					end
				end
			elseif dx2 = 0 then
				-- just the second line is along the y-axis
				y := value_at_position (line_2_start.x, line_1_start, line_1_end)
				if is_between_first_equal (line_1_start.x, line_1_end.x, line_2_start.x) and is_between (line_2_start.y, line_2_end.y, y) then
					b := true
					create pos.make (line_2_start.x, y)
				end

			else
				-- none of the 2 lines are along the y-axis

				y := determinant(line_1_start.x-line_1_end.x, line_1_start.y-line_1_end.y, line_2_start.x-line_2_end.x, line_2_start.y-line_2_end.y)
				if y /= 0 then
					-- the lines are not parallel
					a := determinant (line_1_start.x,line_1_start.y,line_1_end.x,line_1_end.y)
					c := determinant (line_2_start.x,line_2_start.y,line_2_end.x,line_2_end.y)
					x := determinant (a, line_1_start.x-line_1_end.x, c, line_2_start.x-line_2_end.x) / y

					-- possible intersection
					if is_between_equal (line_1_start.x, line_1_end.x, x) and is_between_equal (line_2_start.x, line_2_end.x, x) then
						y := determinant (a, line_1_start.y-line_1_end.y, c, line_2_start.y-line_2_end.y) / y
						pos := create {EM_VECTOR_2D}.make (x, y)
						b := True
					end
				end
			end

			if b = true then
				-- we already tested the intersection for validity
				Result := pos
			elseif pos /= Void then
				-- check if we have an intersection of the extensions of both lines
				if is_between_equal (line_1_start.x, line_1_end.x, pos.x) and is_between_equal (line_1_start.y, line_1_end.y, pos.y) and
					is_between_equal (line_2_start.x, line_2_end.x, pos.x) and is_between_equal (line_2_start.y, line_2_end.y, pos.y) then
					Result := pos
				end
			end
		end

	intersection_point_circle_line (a_circle: EM_CIRCLE_COLLIDABLE; line_start, line_end: EM_VECTOR_2D): DS_LINKED_LIST [EM_VECTOR_2D] is
			-- returns the intersection points of a circle and a line if there are any, otherwise returns an empty list
			-- see `http://mathworld.wolfram.com/Circle-LineIntersection.html' for more detail
		require
			a_circle_not_void: a_circle /= Void
			line_not_void: line_start /= Void and line_end /= Void
		local
			discriminant, dr, dx, dy, det, x, y: DOUBLE
			signum: INTEGER
			list: DS_LINKED_LIST [EM_VECTOR_2D]
			line_start_centered, line_end_centered: EM_VECTOR_2D
		do
			create list.make
			line_start_centered := line_start - a_circle.center
			line_end_centered := line_end - a_circle.center

			dx := line_end_centered.x - line_start_centered.x
			dy := line_end_centered.y - line_start_centered.y

			dr := sqrt (dx*dx + dy*dy)
			det := line_start_centered.x * line_end_centered.y - line_end_centered.x * line_start_centered.y
			discriminant := a_circle.radius * a_circle.radius * dr * dr - det * det

			if discriminant > 0 and dr /= 0 then
				-- 2 intersections
				discriminant := sqrt (discriminant)
				dr := dr * dr
				if dy >= 0 then
					signum := 1
				else
					signum := -1
				end
				x := ((det * dy + signum * dx * discriminant) / dr) + a_circle.center.x
				y := ((-det * dx + dy.abs * discriminant) / dr) + a_circle.center.y
				if is_between_equal_eps (line_start.x, line_end.x, x) and is_between_equal_eps (line_start.y, line_end.y, y) then
					list.force_last (create {EM_VECTOR_2D}.make (x, y))
				end

				x := ((det * dy - signum * dx * discriminant) / dr) + a_circle.center.x
				y := ((-det * dx - dy.abs * discriminant) / dr) + a_circle.center.y
				if is_between_equal_eps (line_start.x, line_end.x, x) and is_between_equal_eps (line_start.y, line_end.y, y) then
					list.force_last (create {EM_VECTOR_2D}.make (x, y))
				end
			elseif discriminant = 0 and dr /= 0 then
				-- 1 intersection (tangent)
				dr := dr * dr
				x := det * dy / dr
				y := -det * dx / dr
				list.force_last (create {EM_VECTOR_2D}.make (x + a_circle.center.x, y + a_circle.center.y))
			else

			end
			Result := list
		end

	is_between (outer_a, outer_b, inner: DOUBLE): BOOLEAN is
			-- checks if `inner' is between `outer_a' and `outber_b'
			-- this operator is strict (equal is not between)
		do
			Result := (outer_a > inner and outer_b < inner) or (outer_a < inner and outer_b > inner)
		end

	is_between_first_equal (outer_a, outer_b, inner: DOUBLE): BOOLEAN is
			-- checks if `inner' is between `outer_a' and `outber_b'
			-- this operator is strict on `outer_a'
			-- this prevents having the same vertex twice in a polygon
		do
			Result := (outer_a >= inner and outer_b < inner) or (outer_a <= inner and outer_b > inner)
		end

	is_between_equal (outer_a, outer_b, inner: DOUBLE): BOOLEAN is
			-- checks if `inner' is between `outer_a' and `outber_b'
			-- this operator is not strict (equal is between)
		do
			Result := (outer_a >= inner and outer_b <= inner) or (outer_a <= inner and outer_b >= inner)
		end

	is_between_equal_eps (outer_a, outer_b, inner: DOUBLE): BOOLEAN is
			-- checks if `inner' is between `outer_a' and `outber_b'
			-- this operator allows +-eps error tolerance
		do
			Result := (outer_a+eps >= inner and outer_b-eps <= inner) or (outer_a-eps <= inner and outer_b+eps >= inner)
		end

	intersect_interval_interval (first_interval_a, first_interval_b, second_interval_a, second_interval_b: DOUBLE): BOOLEAN is
			-- returns true, if the two intervals (first_interval and second_interval) overlap
		do
			Result := is_between_equal (first_interval_a, first_interval_b, second_interval_a) or
				is_between_equal (first_interval_a, first_interval_b, second_interval_b) or
				is_between_equal (second_interval_a, second_interval_b, first_interval_a) or
				is_between_equal (second_interval_a, second_interval_b, first_interval_b)
		end

	value_at_position (an_x: DOUBLE; p1, p2: EM_VECTOR_2D):DOUBLE is
			-- takes 2 points and generates the value of the line, going through both points, at position x.
		require
			line_not_along_y_axis: p1.x /= p2.x
		local
			dx: DOUBLE
		do
			dx := (p2.y-p1.y)/(p2.x-p1.x)
			Result := dx*an_x + p1.y - dx*p1.x
		end

	angle_difference (an_angle, other_angle: DOUBLE): DOUBLE is
			-- computes the difference of 2 angles between -pi and pi from the first given angle
			-- both angles must be in range
		require
			an_angle_in_range: an_angle >= 0 and an_angle <= 2*pi
			other_angle_in_range: other_angle >= 0 and other_angle <= 2*pi
		do
			Result := (an_angle - other_angle)
			if Result < 0 then
				Result := Result + 2*pi
			end
			if Result > pi then
				Result := - 2*pi + Result
			end
		end

	normalized_angle (an_angle: DOUBLE): DOUBLE is
			-- takes an angle in radian and returns the same angle in the interval [0 2*pi[
		local
			factor: DOUBLE
		do
			if an_angle < 0 then
				factor := (an_angle / (2 * pi)).ceiling
				Result := an_angle + factor * 2 * pi
			elseif an_angle >= 2 * pi then
				factor := (an_angle / (2 * pi)).floor
				Result := an_angle - factor * 2 * pi
			else
				Result := an_angle
			end
		ensure
			angle_in_range: Result >= 0 and Result < 2*pi
		end

	determinant (a, b, c, d: DOUBLE): DOUBLE is
			-- gives the determinant of the following matrix:
			-- [a b; c d]
		do
			Result := a * d - b * c
		end

feature {NONE} -- Constants

	eps: DOUBLE is 0.0000001
			-- Epsilon

end