indexing

	description: "[

		Representation of a polygon

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

class POLYGON

inherit

	OBJECT
		undefine
			copy,
			is_equal,
			default_create
		redefine
			set_true_x_y
		end

	EM_POLYGON

create

	make_obj

feature -- Initialization

	make_obj (v1: EM_VECTOR_2D; a_scene: SCENE) is
			-- Make polygon with its first point.
		require
			v1_not_void: v1 /= Void
			a_scene_not_void: a_scene /= Void
		do
			scene := a_scene
			make_empty
			extend (v1)
			true_x := x
			true_y := y
			create true_list.make
			create splitting_lines.make
			create true_splitting_lines.make

			-- create vertices
			create vertex_list.make
			vertex_list.force_last (create {POLYGON_VERTEX}.make (v1, current))

			-- create collidable placeholder, because, we dont know yet, if it will be convex - so it has to be recreated later
			create collidable.make (create {EM_CIRCLE_COLLIDABLE}.make (v1, 0.1), v1)
			collidable.set_holder (current)
			scene.collision_detector.add (current)
			is_collidable_valid := True
			set_changed
		ensure
			scene_set: scene = a_scene
		end

feature -- Access

	collidable: EM_COLLIDABLE_COMPOSITION
			-- returns a collidable polygon

	vertex_list: DS_LINKED_LIST [POLYGON_VERTEX]
			-- a list of vertices that the object has

	true_list: DS_LINKED_LIST [EM_VECTOR_2D]
			-- true list of vertices

	is_collidable_valid: BOOLEAN
			-- is the current collidable valid?

	splitting_lines, true_splitting_lines: DS_LINKED_LIST [EM_PAIR [INTEGER, INTEGER]]
			-- list of all splitting lines

feature -- Element Change

	move_by (an_x, a_y: DOUBLE) is
			-- sets `x' and `y' (screen values, not coordinates -> must be scaled).
		local
			v: EM_VECTOR_2D
		do
			create v.make (an_x / scene.scale, a_y / scene.scale)
			set_x_y (x + (an_x/scene.scale).rounded, y + (a_y / scene.scale).rounded)
		end

	set_true_x_y (an_x, a_y: DOUBLE) is
			-- sets `true_x' and `true_y'
		do
			true_x := an_x
			true_y := a_y
			set_x_y (true_x.rounded, true_y.rounded)

			create true_list.make_from_linear (current)
			set_changed
		end

	set_true_values_internal (a_true_x, a_true_y: DOUBLE; a_x, an_y: INTEGER; a_list, a_true_list: DS_LINKED_LIST [EM_VECTOR_2D]) is
			-- sets `true_list'
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
		do
			if a_list /= Current then
				make_empty
				create cursor.make (a_list)
				from cursor.start
				until cursor.off
				loop
					extend (create {EM_VECTOR_2D}.make_from_other (cursor.item))
					cursor.forth
				end
			end

			x := a_x
			y := an_y
			true_x := a_true_x
			true_y := a_true_y

			create true_list.make
			create cursor.make (a_true_list)
			from cursor.start
			until cursor.off
			loop
				true_list.force_last (create {EM_VECTOR_2D}.make_from_other (cursor.item))
				cursor.forth
			end
		ensure
			items_added: count = a_list.count
		end

	add_splitting_line (a_splitting_line: EM_PAIR [INTEGER, INTEGER]) is
			-- adds a splitting line
		require
			a_splitting_line_not_void: a_splitting_line /= Void
		do
			if a_splitting_line.first >= 1 and a_splitting_line.first <= count and
				a_splitting_line.second >= 1 and a_splitting_line.second <= count and
				((a_splitting_line.first - a_splitting_line.second).abs > 1) and
				not (a_splitting_line.first = count and a_splitting_line.second = 1) and
				not (a_splitting_line.second = count and a_splitting_line.first = 1) then

				if splitting_lines.occurrences (a_splitting_line) = 0 then
					splitting_lines.force_last (a_splitting_line)
				end
			end
		end

	remove_splitting_line (a_splitting_line: EM_PAIR [INTEGER, INTEGER]) is
			-- adds a splitting line
		require
			a_splitting_line_not_void: a_splitting_line /= Void
		do
			splitting_lines.delete (a_splitting_line)
		end

	set_splitting_lines (line_list: DS_LINKED_LIST [EM_PAIR [INTEGER, INTEGER]]) is
			-- sets `splitting_lines' with a copy of `line_list'
		require
			line_list_not_void: line_list /= Void
		do
			splitting_lines := line_list.deep_twin
		end

	set_true_splitting_lines (line_list: DS_LINKED_LIST [EM_PAIR [INTEGER, INTEGER]]) is
			-- sets `splitting_lines' with a copy of `line_list'
		require
			line_list_not_void: line_list /= Void
		do
			true_splitting_lines := line_list.deep_twin
		end

	add_vertex (a_vertex: POLYGON_VERTEX; i: INTEGER) is
			-- adds a vertex to `vertex_list'.
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
		do
			-- update splitting lines
			create cursor.make (splitting_lines)
			from cursor.start
			until cursor.off
			loop
				if cursor.item.first >= i then
					cursor.item.put_first (cursor.item.first+1)
				end
				if cursor.item.second >= i then
					cursor.item.put_second (cursor.item.second+1)
				end
				cursor.forth
			end

			-- add vertex to list
			vertex_list.force (a_vertex, i)
		end

feature -- Computation

	set_changed is
			-- update vertices
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			cursor2: DS_LINKED_LIST_CURSOR [POLYGON_VERTEX]
		do
			-- update vertices
			if points.count /= vertex_list.count then
				-- a point was added/deleted, recreate vertex_list
				create vertex_list.make
				create cursor.make (points)
				from cursor.start
				until cursor.off
				loop
					vertex_list.force_last (create {POLYGON_VERTEX}.make (scene.screen_position_from_coordinates (cursor.item.x, cursor.item.y), current))
					cursor.forth
				end
			else
				-- update vertex positions from `points'
				create cursor2.make (vertex_list)
				create cursor.make (points)
				from cursor.start
					cursor2.start
				until cursor.off or
					cursor.off
				loop
					cursor2.item.set_vector (scene.screen_position_from_coordinates (cursor.item.x, cursor.item.y))
					cursor2.forth
					cursor.forth
				end
			end
		ensure then
			count_ok: vertex_list.count = count
		end

	set_vertexes_updated is
			-- update state from vertexes
		local
			cursor: DS_LINKED_LIST_CURSOR [POLYGON_VERTEX]
			cursor2: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
		do
			make_empty

			create cursor.make (vertex_list)
			from cursor.start
			until cursor.off
			loop
				if not cursor.item.is_deleted then
					extend (scene.coordinates_from_screen_position (cursor.item.vector.x, cursor.item.vector.y))
				else
					-- the vertex will not be added -> update `splitting_lines'
					create cursor2.make (splitting_lines)
					from cursor2.start
					until cursor2.off
					loop
						if cursor2.item.first = cursor.index or cursor2.item.second = cursor.index then
							cursor2.remove
						else

							if cursor2.item.first > cursor.index then
								cursor2.item.put_first (cursor2.item.first-1)
							end
							if cursor2.item.second > cursor.index then
								cursor2.item.put_second (cursor2.item.second-1)
							end

							-- check if the 2 elements are not next to eacht other, otherwise remove from `splitting_lines'
							if ((cursor2.item.first - cursor2.item.second).abs > 1) and
								not (cursor2.item.first = count and cursor2.item.second = 1) and
								not (cursor2.item.second = count and cursor2.item.first = 1) then
								cursor2.forth
							else
								cursor2.remove
							end
						end
					end
				end

				cursor.forth
			end

			-- set_changed
			set_changed
		end

	recreate_collidable is
			-- creacreate `collidable'.
		local
			poly_collidable: EM_POLYGON_CONVEX_COLLIDABLE
			poly: EM_POLYGON
			polygons: DS_LINKED_LIST [EM_POLYGON_CONVEX_COLLIDABLE]
			edges: ARRAY [INTEGER]
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			i, j, k, starting_index, current_index, previous_index: INTEGER
			first_run, hull_is_counterclockwise: BOOLEAN
			v: EM_VECTOR_2D
			circumcircle: EM_PAIR [EM_VECTOR_2D, DOUBLE]
			targets: DS_LINKED_LIST [INTEGER]
			smallest_index: INTEGER
			smallest_angle, current_angle: DOUBLE
			array: ARRAY [EM_VECTOR_2D]
			border: ARRAY [BOOLEAN]
			p1, p2, d1, d2: EM_VECTOR_2D
			dir1, dir2: EM_DIRECTION_2D
			splitting_cursor: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
		do
			collidable.wipe_out
			is_collidable_valid := True
			
			if has_crossing or has_crossing_splitting_lines or has_crossing_splitting_line_with_border or is_splitting_line_out_of_polygon or count < 3 then
				-- the object is not valid, because of crossing lines
				collidable.add (create {EM_CIRCLE_COLLIDABLE}.make (first, 0.1))
				collidable.set_center_only (first)
				is_collidable_valid := False
			else
				-- check for validity of each sub-polygon
				
				-- create array, to ensure O(count)
				create array.make (1, count)
				cursor := new_cursor
				from cursor.start
					i := 1
				until cursor.off
				loop
					array.put (cursor.item, i)
					i := i+1
					cursor.forth
				end
				
				-- create `edges' which counts how many lines a vertex still has
				create edges.make (1, count)
				from i := 1
				until i > count
				loop
					edges.put (2, i)
					i := i + 1
				end
				
				-- create array that saves what border lines have already been passed
				create border.make (1, count)
				
				-- add splitting_lines to `edges'
				create splitting_cursor.make (splitting_lines)
				from splitting_cursor.start
				until splitting_cursor.off
				loop
					edges.put (edges.item (splitting_cursor.item.first) + 2, splitting_cursor.item.first)
					edges.put (edges.item (splitting_cursor.item.second) + 2, splitting_cursor.item.second)
					splitting_cursor.forth
				end

				-- list of added, convex polygons
				-- at the end, all sub-polygons will be added to `polygons'
				create polygons.make
				hull_is_counterclockwise := general_direction
				
				-- Do all polygons touching the hull
				
				-- get `starting_index'
				from i := 1
				variant count - i + 1
				until i > count or else edges.item (i) > 2
				loop
					i := i + 1
				end
				
				if i > count then
					i := 1
				end
				
				
				starting_index := i
				current_index := starting_index
				
				from first_run := True
					j := 0
				variant count - j
				until (current_index = starting_index and not first_run) or is_collidable_valid = False
				loop
					first_run := False
					
					-- find a valid start point
					from 
					until border.item (current_index) = False
					loop
						if current_index = starting_index then
							is_collidable_valid := False
						end
						current_index := (current_index\\count) + 1
					end
					
					-- current polygon
					create poly.make_empty
					p1 := array.item (current_index)
					-- follow the first line along the hull
					edges.put (edges.item (current_index)-1, current_index)
					previous_index := current_index
					
					border.put (True, current_index)
					current_index := (current_index\\count) + 1
					edges.put (edges.item (current_index)-1, current_index)
					p2 := array.item (current_index)
					poly.force_last (p2)
					targets := Void
					
					-- we have p1 to p2 along the hull
					-- try to follow the splitting_lines and hull_lines until back to the previous position
					from i := current_index
						k := 0
					variant
						count - k
					until i = previous_index or is_collidable_valid = False
					loop
						if edges.item (i) = 1 then
							-- only one place to go
							edges.put (edges.item (i)-1, i)
							
							if hull_is_counterclockwise then
								smallest_angle := -4
							else
								smallest_angle := 4
							end
							
							targets :=  targets_of_index (i, edges)
							
							d1 := p2 - p1
							create dir1.make_from_coefficients (d1.x, d1.y)
							
							from targets.start
							until targets.off
							loop
								if array.item (targets.item_for_iteration) /= p1 then
									if not (border.item (i) and (i\\count) + 1 = targets.item_for_iteration) then
										-- don'f follow already done borders
										d2 := array.item (targets.item_for_iteration) - p2
										create dir2.make_from_coefficients (d2.x, d2.y)
										current_angle := angle_difference (dir1.angle, dir2.angle)
										if (hull_is_counterclockwise and current_angle > smallest_angle) or
											(not hull_is_counterclockwise and current_angle < smallest_angle) then
											smallest_index := targets.item_for_iteration
											smallest_angle := current_angle
										end
									end
								end
								
								targets.forth
							end
							
							i := smallest_index
							-- go from i to targets
							p1 := p2
							
							if i = (current_index\\count) + 1 then
								-- the next point is along the hull
								border.put (True, current_index)
								current_index := (current_index\\count) + 1
							end

							p2 := array.item (i)
							poly.force_last (p2)
							edges.put (edges.item (i)-1, i)
						else
							-- check angles from p1 to p2 to possible next points.
							if hull_is_counterclockwise then
								smallest_angle := -4
							else
								smallest_angle := 4
							end
							
							targets :=  targets_of_index (i, edges)
							
							d1 := p2 - p1
							create dir1.make_from_coefficients (d1.x, d1.y)
							
							
							from targets.start
							until targets.off
							loop
								if array.item (targets.item_for_iteration) /= p1 then
									if not (border.item (i) and (i\\count) + 1 = targets.item_for_iteration) then
										d2 := array.item (targets.item_for_iteration) - p2
										create dir2.make_from_coefficients (d2.x, d2.y)
										current_angle := angle_difference (dir1.angle, dir2.angle)
										if (hull_is_counterclockwise and current_angle > smallest_angle) or
											(not hull_is_counterclockwise and current_angle < smallest_angle) then
											smallest_index := targets.item_for_iteration
											smallest_angle := current_angle
										end
									end
								end
								targets.forth
							end
							
							-- move to smallest_index
							p1 := array.item (i)
							edges.put (edges.item (i)-1, i)
							if i = smallest_index then
								-- no found targets
								is_collidable_valid := False
							end
							if (i\\count) + 1 = smallest_index then
								-- go along the border
								border.put (True, i)
							end
							
							i := smallest_index
							p2 := array.item (i)
							poly.force_last (p2)
							edges.put (edges.item (i)-1, i)
						end
						k := k + 1
					end
					
					-- a polygon poly was found, check if it is convex
					if is_collidable_valid and then poly.count > 2 and then poly.is_convex then
						create poly_collidable.make_from_absolute_list (create {EM_VECTOR_2D}.make (0,0), poly)
						circumcircle := poly_collidable.circumcircle
						poly_collidable.set_center_only (circumcircle.first)
						polygons.force_last (poly_collidable)
					else
						is_collidable_valid := False
					end
					
					-- if `current_index' has 0 edges, continue, until either at start again, or one with edges was found
					from k := 0
					variant count - k
					until edges.item (current_index) > 0 or current_index = starting_index
					loop
						current_index := (current_index\\count) + 1
						k := k + 1
					end
					
					j := j + 1
				end
				
				-- now add the rest, which does not touch the hull
				previous_index := count
				current_index := 1
				from 
				until current_index > count or is_collidable_valid = False
				loop
					targets := targets_of_index_over_splitting_lines (current_index, edges)
					
					p1 := array.item (previous_index)
					p2 := array.item (current_index)
					d1 := p2 - p1
					create dir1.make_from_coefficients (d1.x, d1.y)
					
					if targets.count > 0 and edges.item (current_index) > 0 then
						-- first along the largest angle
						create poly.make_empty
						
						if hull_is_counterclockwise then
							smallest_angle := 4
						else
							smallest_angle := -4
						end
						
						from targets.start
						until targets.off
						loop
							d2 := array.item (targets.item_for_iteration) - p2
							create dir2.make_from_coefficients (d2.x, d2.y)
							current_angle := angle_difference (dir1.angle, dir2.angle)
							if (hull_is_counterclockwise and current_angle < smallest_angle) or
								(not hull_is_counterclockwise and current_angle > smallest_angle) then
								smallest_index := targets.item_for_iteration
								smallest_angle := current_angle
							end
							targets.forth
						end
						
						-- the first target is found!
						edges.put (edges.item (current_index)-1, current_index)
						i := smallest_index
						edges.put (edges.item (i)-1, i)
						p1 := p2
						p2 := array.item (i)
						poly.force_last (p2)
						
						-- find the rest of the polygon
						from j := 0
						variant
							count - j
						until i = current_index
						loop
							if hull_is_counterclockwise then
								smallest_angle := -4
							else
								smallest_angle := 4
							end
							
							d1 := p2 - p1
							create dir1.make_from_coefficients (d1.x, d1.y)
							
							targets := targets_of_index_over_splitting_lines (i, edges)
							from targets.start
							until targets.off
							loop
								if array.item (targets.item_for_iteration) /= p1 then
									d2 := array.item (targets.item_for_iteration) - p2
									create dir2.make_from_coefficients (d2.x, d2.y)
									current_angle := angle_difference (dir1.angle, dir2.angle)
									if (hull_is_counterclockwise and current_angle > smallest_angle) or
										(not hull_is_counterclockwise and current_angle < smallest_angle) then
										smallest_index := targets.item_for_iteration
										smallest_angle := current_angle
									end
								end
								targets.forth
							end
							
							-- move forward
							p1 := p2
							edges.put (edges.item (i)-1, i)
							i := smallest_index
							edges.put (edges.item (i)-1, i)
							p2 := array.item (i)
							poly.force_last (p2)
							
							j := j + 1
						end
						
						-- create collidable
						if poly.is_convex and poly.count > 2 then
							from poly.start
							until poly.off
							loop
								poly.forth
							end
							
							create poly_collidable.make_from_absolute_list (create {EM_VECTOR_2D}.make (0,0), poly)
							circumcircle := poly_collidable.circumcircle
							poly_collidable.set_center_only (circumcircle.first)
							polygons.force_last (poly_collidable)
						else
							if poly.count > 2 then
								is_collidable_valid := False
							end
						end
					else
						previous_index := current_index
						current_index := current_index + 1
					end
				end
				
				collidable.wipe_out
				
				-- create `collidable'
				if is_collidable_valid = False then
					-- add dummy collidable of all corners, because no real collidable could be created
					cursor := new_cursor
					create v.make (0,0)
					from cursor.start
					until cursor.off
					loop
						v := v + cursor.item
						collidable.add (create {EM_CIRCLE_COLLIDABLE}.make (cursor.item, 0.1))
						cursor.forth
					end
					
					collidable.set_center_only (v / count)
				else
					-- create composition from `polygons'
					from polygons.start
					until polygons.off
					loop
						collidable.add (polygons.item_for_iteration)
						polygons.forth
					end
					collidable.set_center_only (collidable.center_of_mass)
				end
			end
		end
		
	is_on_border_line_width (a_point: EM_VECTOR_2D; a_width: DOUBLE): EM_PAIR [INTEGER, EM_VECTOR_2D] is
			-- Is `a_point' on boundary line of `Current'?
			-- Returns void, if not on line, other wise a pair of the index of the point where
			-- the line starts (first point is 1) and the point on the line
		local
			px, py: DOUBLE
			p1x, p1y, p2x, p2y: DOUBLE
			lw: DOUBLE
			indx: INTEGER
			p1, p2: EM_VECTOR_2D
			dist, dir, p, a_point_moved: EM_VECTOR_2D
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
		do
			px := a_point.x
			py := a_point.y
			lw := (line_width / 2).max (a_width)

			from
				indx := 1
				cursor := new_cursor
				cursor.start
				p1 := cursor.item
				p1x := p1.x
				p1y := p1.y
			until
				cursor.after or else Result /= Void
			loop
				cursor.forth
				if cursor.after then
					p2 := first
				else
					p2 := cursor.item
				end
				p2x := p2.x
				p2y := p2.y

				-- Calculate rectangular projection on line.
				dir := p2 - p1
				dist := dir.twin
				dist.rotate_rectangularly
				a_point_moved := a_point - dist / 2
				p := a_point_moved.straight_line_intersection_point (dist, p1, dir)

				-- Is distance inside line width
				if p.distance (a_point) <= lw then

					-- only on line segment, if invbetween points.
					if p1x.min (p2x) - eps <= p.x and p.x <= p1x.max (p2x) + eps then
						if p1y.min (p2y) - eps <= p.y and p.y <= p1y.max (p2y) + eps then
							create Result.make (indx, p)
						end
					end
				end

				p1 := p2
				p1x := p2x
				p1y := p2y
				indx := indx + 1
			end
		end
		
	is_on_splitting_line (a_point: EM_VECTOR_2D; a_width: DOUBLE): EM_PAIR [INTEGER, INTEGER] is
			-- is `a_point' on a splitting_line?
			-- returns a reference to the splitting line, otherwise void, if not found
		local
			p1, p2: EM_VECTOR_2D
			dist, dir, p, a_point_moved: EM_VECTOR_2D
			cursor: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
		do
			create cursor.make (splitting_lines)
			from cursor.start
			until cursor.off or Result /= Void
			loop
				p1 := true_list.item (cursor.item.first)
				p2 := true_list.item (cursor.item.second)

				-- Calculate rectangular projection on line.
				dir := p2 - p1
				dist := dir.twin
				dist.rotate_rectangularly
				a_point_moved := a_point - dist / 2
				p := a_point_moved.straight_line_intersection_point (dist, p1, dir)

				-- Is distance inside line width
				if p.distance (a_point) <= a_width then

					-- only on line segment, if invbetween points.
					if p1.x.min (p2.x) - eps <= p.x and p.x <= p1.x.max (p2.x) + eps then
						if p1.y.min (p2.y) - eps <= p.y and p.y <= p1.y.max (p2.y) + eps then
							Result := cursor.item
						end
					end
				end

				cursor.forth
			end
		end
		
	index_of_vertex (a_vertex: VERTEX): INTEGER is
			-- returns the index of a vertex of `vertex_list'
			-- if not found, returns 0
		local
			cursor: DS_LINKED_LIST_CURSOR [POLYGON_VERTEX]
		do
			create cursor.make (vertex_list)
			from cursor.start
			until cursor.off or Result > 0
			loop
				if a_vertex = cursor.item then
					Result := cursor.index
				end
				cursor.forth
			end
		ensure
			intex_in_range: Result >=0 and Result <= count
		end

feature {NONE} -- Implementation

	has_crossing_splitting_lines: BOOLEAN is
			-- do two splitting lines cross?
		local
			cursor1, cursor2: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
			p1, p2, p3, p4: EM_VECTOR_2D
		do
			create cursor1.make (true_splitting_lines)
			create cursor2.make (true_splitting_lines)

			if true_splitting_lines.count > 1 then

				from cursor1.start
				until cursor1.index > true_splitting_lines.count - 1 or Result
				loop

					from cursor2.go_i_th (cursor1.index + 1)
					until cursor2.off or Result
					loop						
						p1 := item (cursor1.item.first)
						p2 := item (cursor1.item.second)
						p3 := item (cursor2.item.first)
						p4 := item (cursor2.item.second)

						if lines_cross (p1, p2, p3, p4) then
							if p1 /= p3 and p1 /= p4 and p2 /= p3 and p2 /= p4 then
								Result := True
							end
						end
						cursor2.forth
					end
					cursor1.forth
				end
			end
		end
		
	is_splitting_line_out_of_polygon: BOOLEAN is
			-- is a splitting line outside of the polygon?
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
			p1, p2: EM_VECTOR_2D
		do
			create cursor.make (true_splitting_lines)
			from cursor.start
			until cursor.off or Result
			loop
				p1 := item (cursor.item.first)
				p2 := item (cursor.item.second)
				if not is_inside ((p1 + p2) / 2) then
					Result := True
				end
				cursor.forth
			end
		end

	has_crossing_splitting_line_with_border: BOOLEAN is
			-- does a splitting line cross a border?
		local
			cursor1: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
			cursor2: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			p1, p2, p3, p4: EM_VECTOR_2D
		do
			create cursor1.make (true_splitting_lines)
			from cursor1.start
			until cursor1.off or Result
			loop
				p1 := item (cursor1.item.first)
				p2 := item (cursor1.item.second)
				
				cursor2 := new_cursor
				cursor2.finish
				p3 := cursor2.item
				from cursor2.start
				until cursor2.off or Result
				loop
					p4 := cursor2.item
					
					if lines_cross (p1, p2, p3, p4) then
						-- now also check if it not right by one of the points
						if p1 /= p3 and p1 /= p4 and p2 /= p3 and p2 /= p4 then
							Result := True
						end
					end
					
					p3 := p4
					cursor2.forth
				end
				
				cursor1.forth
			end
		end

	lines_cross (p1, p2, p3, p4: EM_VECTOR_2D): BOOLEAN is
			-- do two given lines (p1 to p2) and (p3 to p4) cross each other?
			-- the ends do not count as crossing if p1 = p4 for example
		local
			a1, b1, c1, a2, b2, c2, det, tx, ty: DOUBLE
		do
			-- 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 and
					not (tx = p1.x and ty = p1.y) and not (tx = p2.x and ty = p2.y) and 
					not (tx = p3.x and ty = p3.y) and not (tx = p4.x and ty = p4.y) then
					Result := True
				end
			end
		end
		
	splitting_line_contains_index (idx: INTEGER): BOOLEAN is
			-- does `splitting_line' contain the following index?
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
		do
			create cursor.make (splitting_lines)
			from cursor.start
			until cursor.off or Result
			loop
				if cursor.item.first = idx or cursor.item.second = idx then
					Result := True
				end
				cursor.forth
			end
		end
		
	targets_of_index (idx: INTEGER; edges: ARRAY [INTEGER]): DS_LINKED_LIST [INTEGER] is
			-- what indexes are targets of `idx' within `edges'
		require
			possible_indexes_not_void: edges /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
			i: INTEGER
		do
			create cursor.make (splitting_lines)
			create Result.make
			
			from cursor.start
			until cursor.off
			loop
				if cursor.item.first = idx and then edges.item (cursor.item.second) > 0 then
					if cursor.item.second /= idx then
						Result.force_last (cursor.item.second)
					end
				elseif cursor.item.second = idx and then edges.item (cursor.item.first) > 0 then
					if cursor.item.first /= idx then
						Result.force_last (cursor.item.first)
					end
				end
				cursor.forth
			end
			
			i := (idx\\count) + 1
			if edges.item (i) > 0 then
				Result.force_last (i)
			end
			
			-- ignore previouse from hull
		ensure
			target_does_not_have_itself: not Result.has (idx)
		end
		
	targets_of_index_over_splitting_lines (idx: INTEGER; edges: ARRAY [INTEGER]): DS_LINKED_LIST [INTEGER] is
			-- what indexes are targets of `idx' within `edges'
		require
			possible_indexes_not_void: edges /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_PAIR [INTEGER, INTEGER]]
		do
			create cursor.make (splitting_lines)
			create Result.make
			
			from cursor.start
			until cursor.off
			loop
				if cursor.item.first = idx and then edges.item (cursor.item.second) > 0 then
					if cursor.item.second /= idx then
						Result.force_last (cursor.item.second)
					end
				elseif cursor.item.second = idx and then edges.item (cursor.item.first) > 0 then
					if cursor.item.first /= idx then
						Result.force_last (cursor.item.first)
					end
				end
				cursor.forth
			end
		ensure
			target_does_not_have_itself: not Result.has (idx)
		end

	angle_from_three_points (p1, p2, p3: EM_VECTOR_2D): DOUBLE is
			-- returns the angle of the triangle p1->p2->p3 between 0 (backwards) and 2pi (backwards)
			-- pi/2 would be a 90° angle in counterclockwise direction.
		require
			all_different: (p1.x /= p2.x or p1.y /= p2.y) and (p2.x /= p3.x or p2.y /= p3.y)
		local
			d1, d2: EM_VECTOR_2D
			dir1, dir2: EM_DIRECTION_2D
		do
			d1 := p2 - p1
			d2 := p3 - p2
			create dir1.make_from_coefficients (d1.x, d1.y)
			create dir2.make_from_coefficients (d2.x, d2.y)
			Result := angle_difference (dir1.angle, dir2.angle) + pi
		ensure
			result_valid: result >= 0 and result <= 2 * pi + eps
		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
		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
		
	general_direction: BOOLEAN is
			-- is the direction of the hull counterclockwise?
		local
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
			sum: DOUBLE
			p1, p2, p3: EM_VECTOR_2D
		do
			cursor := new_cursor
			cursor.finish
			cursor.back
			p1 := cursor.item
			cursor.forth
			p2 := cursor.item
			from cursor.start
			until cursor.off
			loop
				p3 := cursor.item
				sum := sum + angle_from_three_points (p1, p2, p3) - pi
				
				p1 := p2
				p2 := p3
				cursor.forth
			end
			
			Result := (sum > 0)
		end
		
	
		
end