linear_classification.rb

# Ubuntu (last tested on Trusty Tahr (14.10.1), with Gosu 0.8.6)

# Gosu's dependencies for both C++ and Ruby
# sudo apt-get install build-essential libsdl2-dev libsdl2-ttf-dev libpango1.0-dev \
#                     libgl1-mesa-dev libfreeimage-dev libopenal-dev libsndfile-dev

# To install Ruby - if you are using rvm or rbenv, please skip this step
# sudo apt-get install ruby-dev

# If you are using rvm or rbenv, do not use 'sudo'
# sudo gem install gosu

require 'gosu'

class Point
  include Comparable
  # by default, how much will be big the point when is drawn
  OFFSET = 3

  attr_reader :x, :y
  # cached variables used for drawing the point as a square
  attr_reader :x1, :x2, :x3, :x4, :y1, :y2, :y3, :y4

  def initialize (x, y, offset = OFFSET)
    # force x and y as rational numbers
    @x, @y = [x, y]
    # force x and y as floats
    xf = x.to_f
    yf = y.to_f
    @x1 = @x3 = xf + offset
    @x2 = @x4 = xf - offset
    @y1 = @y2 = yf + offset
    @y3 = @y4 = yf - offset
  end

  def == (point)
    @x == point.x and @y == point.y
  end
end

class Segment
  include Comparable

  attr_reader :p, :q

  def initialize (p, q)
    @p, @q = [p, q]
  end
  
  def == (segm)
    @p == segm.p and @q == segm.q
  end
  
  def extend (width, height)
    if @p.y == @q.y
      return Segment.new(Point.new(@p.x, 0), Point.new(@q.x, height))
    end
    m = (@q.y - @p.y) / (@q.x - @p.x)
    q = @p.y - m * @p.x
    return Segment.new(Point.new(0, q), Point.new(width, m * width + q))
  end
end

class DemoWindow < Gosu::Window
  # how much will be big the window
  WIDTH = 640
  HEIGHT = 480

  # how much will be the mouse when is drawn
  MOUSE_SIZE = 10

  # caption will be set as the title of the window
  def initialize(caption)
    super(WIDTH, HEIGHT, false)
    self.caption = caption
    @red_points = []
    @green_points = []
    @segments = []
  end

  # draws a point on the screen using the given color
  def draw_point (point, color = Gosu::Color::CYAN)
    draw_quad(
      point.x1, point.y1, color,
      point.x2, point.y2, color,
      point.x3, point.y3, color,
      point.x4, point.y4, color)
  end

  # represents the segment on the screen using the given color
  def draw_segment (segment, color = Gosu::Color::FUCHSIA)
    draw_line(
      segment.p.x.to_f, segment.p.y.to_f, color,
      segment.q.x.to_f, segment.q.y.to_f, color)
  end

  # draws a nice triangle, representing the mouse
  def draw_mouse(color = Gosu::Color::WHITE)
    draw_triangle(
      mouse_x, mouse_y, color,
      mouse_x + MOUSE_SIZE, mouse_y, color,
      mouse_x, mouse_y + MOUSE_SIZE, color)
  end
  
  def button_down(id)
    if id == Gosu::MsLeft
      point = Point.new(mouse_x, mouse_y)
      @red_points << point
      @segments = (find_best_solutions(@green_points, @red_points).map { |s| s.extend(WIDTH, HEIGHT) })
    elsif id == Gosu::MsRight
      point = Point.new(mouse_x, mouse_y)
      @green_points << point
      @segments = (find_best_solutions(@green_points, @red_points).map { |s| s.extend(WIDTH, HEIGHT) })
    elsif id == Gosu::KbEscape
      @red_points = []
      @green_points = []
      @segments = []
    end
  end
  
  def draw
    @segments.each do |segment|
      draw_segment(segment)
    end
    @red_points.each do |point|
      draw_point(point, Gosu::Color::RED)
    end
    @green_points.each do |point|
      draw_point(point, Gosu::Color::GREEN)
    end
    draw_mouse
  end
end

def determinant2 (a, b, c, d)
  a * d - b * c
end

def find_best_solutions (greens, reds)
  score = 0
  segments = []
  points = greens + reds
  points.combination(2).each do |p, q|
    left_score = right_score = 0
    greens.each do |r|
      if p == r or q == r
        next
      end
      if determinant2(q.x - p.x, r.x - p.x, q.y - p.y, r.y - p.y) > 0
        right_score += 1
      else
        left_score += 1
      end
    end
    reds.each do |r|
      if p == r or q == r
        next
      end
      if determinant2(q.x - p.x, r.x - p.x, q.y - p.y, r.y - p.y) > 0
        left_score += 1
      else
        right_score += 1
      end
    end
    [left_score, right_score].each do |temp_score|
      if temp_score == score
        segments << Segment.new(p, q)
      elsif temp_score > score
        score = temp_score
        segments = [Segment.new(p, q)]
      end
    end
  end
  return segments
end

if __FILE__ == $0
  window = DemoWindow.new "linear classification demo"
  window.show
end