#193180 by Denis Defreyne (ddfreyne)

Theme:
class ParamsFile

  def self.read(filename)
    # Read params
    lines = File.read(filename).gsub("\r", '').split("\n")

    # Convert vertices
    vertex_count  = lines[1].to_i
    vertices_raw  = lines[2,2+vertex_count].map { |line| line.split(',').map { |coord| coord.to_i } }
    vertices      = vertices_raw.map { |c| Vertex.new(c[0].to_f, c[1].to_f) }
    polygon       = Polygon.new(vertices)

    # Convert into hash
    { :output_filename => lines[0], :polygon => polygon }
  end

end

##########

class OutputFile

  def initialize(triangles, filename)
    @triangles  = triangles
    @filename   = filename
  end

  def write
    File.open(@filename, 'w') do |io|
      @triangles.each do |t|
        io.write([ t.a.x, t.a.y, t.b.x, t.b.y, t.c.x, t.c.y ].join(','))
      end
    end
  end

end

##########

module Enumerable

  def max
    inject { |max, obj| obj > max ? obj : max }
  end

end

##########

class Vertex

  attr_accessor :x, :y

  def initialize(x, y)
    @x, @y = x, y
  end

  def -(other)
    Vertex.new(self.x - other.x, self.y - other.y)
  end

  def *(other)
    self.x*other.x + self.y*other.y
  end

  def to_s
    "Vertex(#{@x}, #{@y})"
  end

end

##########

class LineSegment

  attr_reader :a, :b

  def initialize(a, b)
    @a = a
    @b = b
  end

  def middle
    Vertex.new((@a.x + @b.x)/2.0, (@a.y + @b.y)/2.0)
  end

  def intersect?(other)
    # FIXME support vertical (horizontal?) lines
 
    # Calculate slopes
    m1 = (self.b.y  - self.a.y )/(self.b.x  - self.a.x )
    m2 = (other.b.y - other.a.y)/(other.b.x - other.a.x)

    # Calculate y intersection
    b1 = self.a.y  - self.a.x  * (self.b.y  - self.a.y )/(self.b.x  - self.a.x )
    b2 = other.a.y - other.a.x * (other.b.y - other.a.y)/(other.b.x - other.a.x)

    # Calculate intersection point
    ix = (b2 - b1)/(m1 - m2)
    iy = m1 * ix + b1

    # Check whether intersection point is on line (X)
    return false unless (ix >= self.a.x  and ix <= self.b.x ) or (ix <= self.a.x  and ix >= self.b.x)
    return false unless (ix >= other.a.x and ix <= other.b.x) or (ix <= other.a.x and ix >= other.b.x)

    # Check whether intersection point is on line (Y)
    return false unless (iy >= self.a.y  and iy <= self.b.y ) or (iy <= self.a.y  and iy >= self.b.y)
    return false unless (iy >= other.a.y and iy <= other.b.y) or (iy <= other.a.y and iy >= other.b.y)

    true
  end

  def right_vertex
    @a.x > @b.x ? @a : @b
  end

  def left_vertex
    @a.x < @b.x ? @a : @b
  end

  def top_vertex
    @a.y > @b.y ? @a : @b
  end

  def bottom_vertex
    @a.y < @b.y ? @a : @b
  end

  def to_s
    "LineSegment(#{@a}, #{@b})"
  end

end

##########

class Polygon

  def initialize(vertices)
    @vertices = vertices
  end

  def contain?(vertex, vertices=@vertices)
    # Calculate edges
    edges = []
    vertices.each_with_index do |_, i|
      prev_vertex = vertices[i-1]
      this_vertex = vertices[i]

      edges << LineSegment.new(prev_vertex, this_vertex)
    end

    # Create horizontal ray
    max_x = vertices.map { |v| v.x }.max
    ray = LineSegment.new(vertex, Vertex.new(max_x+1.0, vertex.y))

    # Find intersecting edges
    intersecting_edges = edges.select { |edge| edge.intersect?(ray) }

    # Check number of intersections
    (intersecting_edges.size % 2) == 1
  end

  def triangulate
    # Check whether we have at least 4 vertices
    raise ArgumentError.new("Cannot triangulate if vertex count < 4") if @vertices.size < 4

    # Vertices in new polygon
    remaining_vertices = @vertices.dup

    # Triangles cut off from original polygon
    triangles = []

    until remaining_vertices.size < 3
      # Find ears
      ears = {}
      remaining_vertices.each_with_index do |_, i|
        # Get relevant vertices
        prev_vertex = remaining_vertices[i-1]
        this_vertex = remaining_vertices[i]
        next_vertex = remaining_vertices[(i+1) % remaining_vertices.size]

        # Get middle of prev-next line segment
        middle_vertex = LineSegment.new(prev_vertex, next_vertex).middle

        # Check whether vertex is an ear if middle point is inside the polygon
        ears[i] = this_vertex if self.contain?(middle_vertex, remaining_vertices)
      end

      # Pick first ear
      index = ears.keys.first

      # Create triangle
      prev_vertex = remaining_vertices[index-1]
      this_vertex = remaining_vertices[index]
      next_vertex = remaining_vertices[(index+1) % remaining_vertices.size]
      triangles << Triangle.new(prev_vertex, this_vertex, next_vertex)

      # Remove ear
      remaining_vertices.delete_at(index)
    end

    # Debug
    puts "Triangles:"
    puts triangles

    # Return triangles
    triangles
  end

  def to_s
    "Polygon(vertices = [ #{@vertices.join(', ')} ])"
  end

end

##########

class Triangle

  attr_accessor :a, :b, :c

  def initialize(a, b, c)
    @a, @b, @c = a, b, c
  end

  def contain?(vertex)
    # Get vectors starting from @a
    v0 = @c - @a
    v1 = @b - @a
    v2 = vertex - @a

    # Compute dot products
    dot00 = v0 * v0
    dot01 = v0 * v1
    dot02 = v0 * v2
    dot11 = v1 * v1
    dot12 = v1 * v2

    # Compute barycentric coords
    idenom = 1.0 / (dot00 * dot11 - dot01 * dot01)
    u = (dot11 * dot02 - dot01 * dot12) * idenom
    v = (dot00 * dot12 - dot01 * dot02) * idenom

    # Check whether it's inside
    u > 0.0 and v > 0.0 and u + v < 1.0
  end

  def to_s
    "Triangle(#{@a}, #{@b}, #{@c})"
  end

end

##########

# Check commandline options
if(ARGV.size != 1)
  puts "usage: gra1opl.rb [filename]"
  exit 1
end

# Read params
params = ParamsFile.read(ARGV[0])

# Triangulate
triangles = params[:polygon].triangulate

# Write output
OutputFile.new(triangles, params[:output_filename]).write