Quadrilateral shape decider and drawer

quadrilateral-drawer.rb

#!/usr/bin/env ruby

# quadrilateral-drawer.rb : Quadrilateral shape decider and drawer
#   by takehikom

# This program invokes ImageMagick's "convert" command.

class QuadrilateralDrawer
  def initialize(opt = {})
    @margin = (opt[:margin] || 10).to_i
    @radius1 = (opt[:r1] || 150).to_f
    @radius2 = (opt[:r2] || @radius1 * 0.5).to_f
    @circlewidth = (opt[:stroke1] || 2).to_f
    @quadcolor = opt[:col] || "blue"
    @quadwidth = (opt[:stroke2] || @circlewidth * 1.5).to_f
    @pointsize = (opt[:pointsize] || 20).to_f
    @bgcolor = opt[:bg] || "#f0fff0"
    @img_base = opt[:base] || "base.png"
    @angle_mid = (opt[:mid] || 135).to_f
    @poly = opt[:poly] || ""
    @option_allnode = opt[:allnode] # すべての頂点名を書くなら真
    @option_nodraw = opt[:nodraw] # 画像を作成しないなら真
    @option_inclusive = opt[:inclusive] # 包摂的な判定をする（"RECTANGLE"のとき"PARALLELOGRAM"なども含む）なら真
    @shape_a = []

    @width = @height = @margin * 2 + @radius1 * 2

    setup_nodes
  end
  attr_reader :shape_a

  def start
    draw_base if !@option_nodraw
    if !@poly.empty?
      setup_shape
      print_shape
    end
  end

  def setup_shape
    # 頂点から座標取得
    setup_points

    # 画像作成
    draw_poly if @point_a.length >= 3 && !@option_nodraw

    # 四角形にならない場合の判定
    # 頂点数が4でない
    if @point_a.length != 4
      add("NONQUADRILATERAL")
      return
    end
    # 3点が同一直線上にある
    if colinear?
      add("COLINEAR")
      return
    end
    # 交わりがある
    if intersect?
      add("INTERSECTED")
      return
    end

    # 形状判定のための値を算出
    # 隣り合う2辺の長さの平方: @length_a
    setup_lengths
    # 隣り合う2角の大きさ: @angle_a
    setup_angles
    # 隣り合う2辺のベクトル（平行判定用）: @vector_a
    setup_vectors

    # 各形状の判定
    (%w(square rectangle rhombus parallelogram) +
      %w(isosceles_trapezoid trapezoid kite)).each do |shape|
      sym = ("judge_#{shape}?").to_sym
      puts "DEBUG: send #{sym}" if $DEBUG
      if self.send(sym)
        add(shape.upcase)
      end
    end
    add("QUADRILATERAL") if @shape_a.empty?
    reduce_shape if !@option_inclusive

    @shape_a
  end

  def setup_nodes
    @node = {}
    @node["A"] = [@radius1, 90]
    @node["B"] = [@radius1, @angle_mid]
    @node["C"] = [@radius1, 180]
    @node["D"] = [@radius2, 90]
    @node["E"] = [@radius2, @angle_mid]
    @node["F"] = [@radius2, 180]
    @node["G"] = [@radius2, 90 + 180]
    @node["H"] = [@radius2, @angle_mid + 180]
    @node["I"] = [@radius2, 180 + 180]
    @node["J"] = [@radius1, 90 + 180]
    @node["K"] = [@radius1, @angle_mid + 180]
    @node["L"] = [@radius1, 180 + 180]
    @node
  end

  def draw_base
    command = "convert -size #{@width.to_i}x#{@height.to_i} xc:#{@bgcolor}"

    command += " -fill none -stroke black -strokewidth #{@circlewidth}"
    command += " -draw \'circle #{@width * 0.5},#{@height * 0.5} #{@width * 0.5 - @radius1},#{@height * 0.5} circle #{@width * 0.5},#{@height * 0.5} #{@width * 0.5 - @radius2},#{@height * 0.5}\'"

    command += " -fill none -stroke black -strokewidth #{@circlewidth * 0.5}"
    s = " -draw \"stroke-dasharray 2 4"
    [0, 90, @angle_mid].each do |angle|
      x1, y1 = poler2xy_image(@radius1, angle)
      x2, y2 = poler2xy_image(@radius1, angle + 180)
      s += " line #{x1},#{y1} #{x2},#{y2}"
    end
    s += "\""
    command += s

    command += " -fill black -stroke none"
    s = " -draw \""
    [@radius1, @radius2].each do |r|
      [0, 90, @angle_mid, 180, 270, @angle_mid + 180].each do |angle|
        x, y = poler2xy_image(r, angle)
        s += " circle #{x},#{y} #{x + @circlewidth * 2},#{y}"
      end
    end
    s += "\""
    command += s

    command += charcode(@node.keys) if @option_allnode

    command += " -quality 92 \"#{@img_base}\""

    puts command if $DEBUG
    system command
  end

  def setup_points
    @point_a = @poly.split(//).map {|c| @node[c] ? ([c] + @node[c]) : nil}
    a = @point_a.compact
    if @point_a.size > a.size
      puts "Warning: one or more character ignored"
      @point_a = a
    end
    a = @point_a.uniq
    if @point_a.size > a.size
      puts "Warning: two or more characters identical"
      @point_a = a
    end
  end

  def setup_lengths
    puts "DEBUG: setup_lengths" if $DEBUG
    @length_a = []
    a = @point_a.map {|item| poler2xy(item[1], item[2])}.flatten
    polysize = @point_a.length
    polysize.times do |i|
      j = (i + 1) % polysize
      x1 = a[i * 2]
      y1 = a[i * 2 + 1]
      x2 = a[j * 2]
      y2 = a[j * 2 + 1]
      len = (x2 - x1) ** 2 + (y2 - y1) ** 2
      @length_a << len
      puts "DEBUG: #{@point_a[i][0]}#{@point_a[j][0]}^2 = #{len}" if $DEBUG
    end
  end

  def setup_angles
    puts "DEBUG: setup_angles" if $DEBUG
    @angle_a = []
    a = @point_a.map {|item| poler2xy(item[1], item[2])}.flatten
    polysize = @point_a.length
    polysize.times do |i|
      j = (i + 1) % polysize
      k = (i + 2) % polysize
      x1 = a[i * 2]
      y1 = a[i * 2 + 1]
      x2 = a[j * 2]
      y2 = a[j * 2 + 1]
      x3 = a[k * 2]
      y3 = a[k * 2 + 1]
      s1 = [x1 - x2, y1 - y2]
      s2 = [x3 - x2, y3 - y2]
      ang = (Math.atan2(*s2) - Math.atan2(*s1)) * 180 / Math::PI
      ang += 360 if ang < 0
      @angle_a << ang
      puts "DEBUG: angle(#{@point_a[i][0]}#{@point_a[j][0]}#{@point_a[k][0]}) = #{ang}" if $DEBUG
    end
  end

  def setup_vectors
    puts "DEBUG: setup_vectors" if $DEBUG
    @vector_a = []
    a = @point_a.map {|item| poler2xy(item[1], item[2])}.flatten
    polysize = @point_a.length
    polysize.times do |i|
      j = (i + 1) % polysize
      x1 = a[i * 2]
      y1 = a[i * 2 + 1]
      x2 = a[j * 2]
      y2 = a[j * 2 + 1]
      vec = [x2 - x1, y2 - y1]
      @vector_a << vec
      puts "DEBUG: #{@point_a[i][0]}#{@point_a[j][0]} = #{vec.inspect}" if $DEBUG
    end
  end

  def equal_length?(len1, len2, eps = 1e-4)
    puts "DEBUG:: equal_length?(#{len1}, #{len2}, #{eps}) => #{(len2 - len1).abs / len1 <= eps}" if $DEBUG
    return true if len1.abs <= eps && len2.abs <= eps
    return true if (len2 - len1).abs / len1 <= eps
    false
  end

  def equal_angle?(ang1, ang2, eps = 1e-2)
    puts "DEBUG:: equal_angle?(#{ang1}, #{ang2}, #{eps}) => #{(ang2 - ang1).abs <= eps}" if $DEBUG
    return true if (ang2 - ang1).abs <= eps
    false
  end

  def parallel_vectors?(vec1, vec2, eps = 1e-4)
    norm = (vec1 + vec2).map {|v| v * v}.inject(:+)
    puts "DEBUG:: parallel_vectors?(#{vec1.inspect}, #{vec2.inspect}, #{eps}) => #{(vec1[0] * vec2[1] - vec2[0] * vec1[1]).abs <= eps * norm}" if $DEBUG
    return true if (vec1[0] * vec2[1] - vec2[0] * vec1[1]).abs <= eps * norm
    false
  end

  def draw_poly
    command = "convert #{@img_base}"

    command += charcode(@point_a.map(&:first).join) if !@option_allnode

    command += " -fill none -stroke #{@quadcolor} -strokewidth #{@quadwidth}"
    command += " -draw \'polygon #{@point_a.map{|item| poler2xy_image(item[1], item[2])}.join(',')}\'"

    command += " -quality 92 \"#{@poly}.png\""

    puts command if $DEBUG
    system command
  end

  def poler2xy(r, angle)
    x = r.to_f * Math.cos(Math::PI * angle / 180.0)
    y = r.to_f * Math.sin(Math::PI * angle / 180.0)
    [x, y]
  end

  def poler2xy_image(r, angle)
    x1, y1 = poler2xy(r, angle)
    x2 = @width * 0.5 + x1
    y2 = @height * 0.5 - y1
    [x2, y2]
  end

  def charcode(c_a, code_pre = nil)
    return "" if c_a.empty?
    c_a = c_a.split(//) if String === c_a

    s = code_pre || " -fill black -stroke none -pointsize #{@pointsize}"
    s += " -draw \""
    c_a.each do |c|
      r, angle = @node[c]
      x, y = poler2xy_image(r, angle)
      if r == @radius1 && angle.to_i % 360 == 0
        f = -0.9
      else
        f = 0.3
      end
      s += " text #{x + @pointsize * f},#{y + @pointsize * 0.5} \'#{c}\'"
    end
    s + "\""
  end

  def intersect?
    a1 = @point_a.map {|item| poler2xy(item[1], item[2])}.flatten
    a2 = a1.rotate(2)
    intersect_lines?(*a1) || intersect_lines?(*a2)
  end

  def intersect_lines?(ax, ay, bx, by, cx, cy, dx, dy)
    # https://qiita.com/ykob/items/ab7f30c43a0ed52d16f2
    ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax)
    tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx)
    tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx)
    td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx)

    # return tc * td < 0 && ta * tb < 0
    return tc * td <= 0 && ta * tb <= 0 # 端点を含む場合
  end

  def colinear?
    a1 = @point_a.map {|item| poler2xy(item[1], item[2])}.flatten
    a2 = a1 + a1[0, 4]
    colinear_3points?(*a2[0, 6]) ||
      colinear_3points?(*a2[2, 6]) ||
      colinear_3points?(*a2[4, 6]) ||
      colinear_3points?(*a2[6, 6])
  end

  def colinear_3points?(ax, ay, bx, by, cx, cy, eps = 1e-4)
    # http://parametron.blogspot.com/2008/04/3.html
    d = ((ax * by + bx * cy + cx * ay) - (ax * cy + bx * ay + cx * by)).abs
    # puts "DEBUG: #{d}" if $DEBUG
    d <= eps
  end

  def judge_square?
    puts "DEBUG:: judge_square?" if $DEBUG
    equal_length?(@length_a[0], @length_a[1]) &&
      equal_length?(@length_a[1], @length_a[2]) &&
      equal_length?(@length_a[2], @length_a[3]) &&
      equal_angle?(@angle_a[0], @angle_a[1])
  end

  def judge_rectangle?
    puts "DEBUG:: judge_rectangle?" if $DEBUG
    equal_angle?(@angle_a[0], @angle_a[1]) &&
      equal_angle?(@angle_a[1], @angle_a[2]) &&
      equal_angle?(@angle_a[2], @angle_a[3])
  end

  def judge_rhombus?
    puts "DEBUG:: judge_rhombus?" if $DEBUG
    equal_length?(@length_a[0], @length_a[1]) &&
      equal_length?(@length_a[1], @length_a[2]) &&
      equal_length?(@length_a[2], @length_a[3])
  end

  def judge_parallelogram?
    puts "DEBUG:: judge_parallelogram?" if $DEBUG
    parallel_vectors?(@vector_a[0], @vector_a[2]) &&
      parallel_vectors?(@vector_a[1], @vector_a[3])
  end

  def judge_trapezoid?
    puts "DEBUG:: judge_trapezoid?" if $DEBUG
    parallel_vectors?(@vector_a[0], @vector_a[2]) ||
      parallel_vectors?(@vector_a[1], @vector_a[3])
  end

  def judge_isosceles_trapezoid?
    puts "DEBUG:: judge_isosceles_trapezoid?" if $DEBUG
    (parallel_vectors?(@vector_a[0], @vector_a[2]) &&
      equal_length?(@length_a[1], @length_a[3])) ||
      (parallel_vectors?(@vector_a[1], @vector_a[3]) &&
      equal_length?(@length_a[0], @length_a[2])) ||
    false
  end

  def judge_kite?
    puts "DEBUG:: judge_kite?" if $DEBUG
    (equal_length?(@length_a[0], @length_a[1]) &&
      equal_length?(@length_a[2], @length_a[3])) ||
      (equal_length?(@length_a[1], @length_a[2]) &&
      equal_length?(@length_a[3], @length_a[0]))
  end

  def find_shape(shape)
    @shape_a.index(shape)
  end

  def square?; find_shape("SQUARE"); end
  def rectangle?; find_shape("RECTANGLE"); end
  def rhombus?; find_shape("RHOMBUS"); end
  def parallelogram?; find_shape("PARALLELOGRAM"); end
  def trapezoid?; find_shape("TRAPEZOID"); end
  def isosceles_trapezoid?; !find_shape("ISOSCELES_TRAPEZOID"); end
  def kite?; find_shape("KITE"); end

  def add_shape(shape)
    @shape_a << shape.to_s
  end
  alias :add :add_shape

  def reduce_shape
    a = []
    @shape_a.each do |shape|
      case shape
      when "RECTANGLE", "RHOMBUS"
        next if find_shape("SQUARE")
      when "PARALLELOGRAM"
        next if find_shape("RECTANGLE") || find_shape("RHOMBUS")
      when "ISOSCELES_TRAPEZOID"
        next if find_shape("PARALLELOGRAM")
      when "TRAPEZOID"
        next if find_shape("PARALLELOGRAM") || find_shape("ISOSCELES_TRAPEZOID")
      when "KITE"
        next if find_shape("RHOMBUS")
      end
      a << shape
    end
    @shape_a = a
  end

  def print_shape
    puts @shape_a.join(', ')
  end
end

if __FILE__ == $0
  if ARGV.first == "sample"
    # 正方形
    QuadrilateralDrawer.new(poly: "ACJL").start
    # ひし形
    QuadrilateralDrawer.new(poly: "DCGL").start
    # 長方形
    QuadrilateralDrawer.new(poly: "ABJK").start
    # 平行四辺形
    QuadrilateralDrawer.new(poly: "AEJH").start
    # 等脚台形
    QuadrilateralDrawer.new(poly: "DCJI").start
    # 台形
    QuadrilateralDrawer.new(poly: "ABEL").start
    # 凧形
    QuadrilateralDrawer.new(poly: "DFJI").start
    # ただの四角形
    QuadrilateralDrawer.new(poly: "ABGK").start
    # すべての頂点名を付けた初期状態
    QuadrilateralDrawer.new(allnode: true).start
  elsif ARGV.first
    opt = {}
    opt[:poly] = ARGV.shift
    # opt[:allnode] = true
    # opt[:nodraw] = true
    QuadrilateralDrawer.new(opt).start
  else
    shape_h = {}
    node_a = "ABCDEFGHIJKL".split(//)
    node_a.permutation(4) do |a|
      poly = a.join
      opt = {}
      opt[:poly] = poly
      opt[:nodraw] = true
      qd = QuadrilateralDrawer.new(opt)
      qd.setup_shape
      shape = qd.shape_a.sort.join("&")
      puts "#{poly}: #{shape}"
      if shape_h.key?(shape)
        shape_h[shape] << poly
      else
        shape_h[shape] = [poly]
      end
    end
    puts "==== RESULTS ===="
    shape_h.each_key do |shape|
      puts "%19s: %4d figures" % [shape, shape_h[shape].length]
    end
  end
end