indexing

	description: "[

		A polygon drawable in EiffelMedia

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

class EM_POLYGON

inherit

	EM_MULTI_POINTED_FIGURE
		undefine
			default_create
		redefine
			draw, publish_mouse_event
		end

	EM_CLOSED_FIGURE
		undefine
			is_equal,
			copy,
			set_x_y,
			publish_mouse_event
		end

	DOUBLE_MATH
		export
			{NONE} all
		undefine
			is_equal,
			copy,
			default_create
		end

create

	make_empty, make_from_array, make_from_list, make_regular

feature -- Initialization

	make_regular (n: INTEGER; first_point, first_edge: EM_VECTOR_2D) is
			-- Create a regular polygon with `n' points.
			-- Starting with `first_point' and going into direction of `first_edge' (clockwise).
		require
			at_least_3_points: n >= 3
			first_point_not_void: first_point /= Void
			first_edge_not_void: first_edge /= Void
			first_edge_not_zero: first_edge.length > 0
		local
			i: INTEGER
			step_angle: DOUBLE
			cur_point, cur_edge: EM_VECTOR_2D
		do
			make_empty
			from
				i := 1
				cur_point := first_point.twin
				cur_edge := first_edge.twin
				step_angle := 2 * Pi / n
			until
				i > n
			loop
				extend (cur_point)
				cur_point := cur_point + cur_edge
				cur_edge.rotate (step_angle)
				i := i + 1
			end
		ensure
			polygon_with_n_points_created: count = n
			first_point_set: first.is_equal (first_point)
			is_visible: is_visible
		end

feature -- Drawing

	draw (surface: EM_SURFACE) is
			-- Draw `Current' onto `surface'.
		do
			if is_visible then
				if is_filled then
					surface.set_drawing_color (fill_color)
					surface.fill_polygon (Current)
				end
				if line_width > 0 then
					surface.set_drawing_color (line_color)
					surface.set_line_width (line_width)
					surface.draw_polygon (Current)
				end
			end
		end

feature -- Mouse Events

	is_inside (a_point: EM_VECTOR_2D): BOOLEAN is
			-- Is `a_point' inside boundaries of `Current'.
		local
			px, py: DOUBLE
			p1x, p1y, p2x, p2y: DOUBLE
			cursor: DS_LINKED_LIST_CURSOR [EM_VECTOR_2D]
		do
			px := a_point.x
			py := a_point.y

			from
				cursor := new_cursor
				cursor.start
				p1x := cursor.item.x
				p1y := cursor.item.y
			until
				cursor.after
			loop
				cursor.forth
				if cursor.after then
					p2x := first.x
					p2y := first.y
				else
					p2x := cursor.item.x
					p2y := cursor.item.y
				end

				if (p1y < py and then p2y >= py) or else (p2y < py and then p1y >= py) then
					if p1x + (py - p1y) / (p2y - p1y) * (p2x - p1x) < px then
						Result := not Result
					end
				end
				p1x := p2x
				p1y := p2y
			end
		end

	is_on_border_line (a_point: EM_VECTOR_2D): BOOLEAN is
			-- Is `a_point' on boundary line of `Current'?
		local
			px, py: DOUBLE
			p1x, p1y, p2x, p2y: DOUBLE
			lw: DOUBLE
			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 (0.001)

			from
				cursor := new_cursor
				cursor.start
				p1 := cursor.item
				p1x := p1.x
				p1y := p1.y
			until
				cursor.after or Result = True
			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
							Result := True
						end
					end
				end

				p1 := p2
				p1x := p2x
				p1y := p2y
			end
		end

	publish_mouse_event (a_mouse_event: EM_MOUSE_EVENT) is
			-- Publish mouse event when `a_mouse_event' occured on `Current'.
			-- Only publish mouse event, if `proportional_point' lies on a point.
		do
			if bounding_box.has (a_mouse_event.proportional_position) then
				if (is_filled and then is_inside (a_mouse_event.proportional_position)) or else is_on_border_line (a_mouse_event.proportional_position) then
					dispatch_mouse_event (a_mouse_event)
					a_mouse_event.set_caught (True)
				end
			end

		end

	is_convex: BOOLEAN is
			-- is the polygon 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, dx: DOUBLE
		do
			Result := True
			if points.count > 3 then
				if not has_crossing then
					create cursor.make (points)
					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
								dx := (p_curr.y-p_prev.y)/(p_curr.x-p_prev.x)
								next_y := dx*p_next.x + p_prev.y - dx*p_prev.x

								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
				else
					-- the polygon had crossings
					Result := False
				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 count > 3 then
				first_run := True

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

				from
				until cursor1.index > 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

feature {NONE} -- Implementation

	eps: DOUBLE is 0.0001
			-- epsilon, needed for double precision errors

end