class HULL_TOOL

  -- Since this class just defines the convex hull
  -- function and carries no data, it has no creation
  -- routines.

feature

convex_hull ( points: ARRAY [POINT] ): GBN_DLIST [INTEGER] is

  require
    nonempty : not points.is_empty

  local
    u_hull : GBN_DLIST [INTEGER]
    i, j : INTEGER

  do
    Result := half_hull ( points, points.lower, points.upper, true )
    		-- returns the lower half of hull, ordered left to
		-- right

    if points.count > 1 then
      u_hull := half_hull ( points, points.lower, points.upper, false )
      		-- upper half of hull, ordered right to left
      u_hull . remove_first
      u_hull . remove_last
      		-- remove endpoints common to lower half
      Result . absorb_suffix ( u_hull )
      		-- concatenate: hull in anticlockwise order
    end -- if count > 1
  end
    

half_hull ( points: ARRAY[POINT]; low, high: INTEGER; lower_half: BOOLEAN )
	: GBN_DLIST [INTEGER] is
  require
    nonvoid : points /= Void
    in_range : points.lower <= low and low <= high and
    	high <= points.upper

  local
    m : INTEGER
    p, q, r : POINT
    p_ok, q_ok : BOOLEAN
    first_hull, second_hull : GBN_DLIST[INTEGER]

  do
    if low = high then
    		-- Only one point
      !! Result.make
      Result.add_first ( low )
    else
      m := (low+high) // 2
      from
        if lower_half then
		-- lower halves of hulls, ordered left to right
          first_hull := half_hull ( points, low, m, true )
          second_hull := half_hull ( points, m+1, high, true )
        else
		-- upper halves ordered right to left
          second_hull := half_hull ( points, low, m, false )
          first_hull := half_hull ( points, m+1, high, false )
        end
      until
        p_ok and q_ok
      loop
        p := points.item ( first_hull . last_item )
        q := points.item ( second_hull . first_item )

	if first_hull.count > 1 then
	  r := points . item (
	  	first_hull . item (
	  	first_hull . pred (
		  first_hull . last_place )) )
	  p_ok := r . left_of (p,q)

	  if not p_ok then
	    first_hull . remove_last
	    p := points . item  ( first_hull . last_item )
	  end
	else
	  p_ok := true
	end

	if second_hull.count > 1 then
	  r := points . item (
	  	second_hull . item (
	  	second_hull . succ (
		  second_hull . first_place )) )
	  q_ok := r . left_of (p,q)
	  
	  if not q_ok then
	    second_hull . remove_first
	  end
	else
	  q_ok := true
	end
      end -- loop

      Result := first_hull
      Result . absorb_suffix ( second_hull )

    end -- if more than one point
  end

end -- class HULL_TOOL