angle.rb

#!/usr/local/bin/ruby -Ks -w
# -*- mode: ruby; tab-width: 2;  -*-

#
#  自動ラベリングエンジン
#

require 'geometory'
require 'angle_parm'
require 'util'

class RangeSet
  def initialize
    @ranges = []
  end

  def add(range)
    min = range[0]
    max = range[1]
    _add(min, max)
    @ranges = @ranges.select {|r| r}
  end

  def _delete_subset(i, max)
    while i < @ranges.size and @ranges[i].last <= max do
      @ranges[i] = nil
      i = i + 1
    end

    if i < @ranges.size and @ranges[i].first <= max then
      newmax = @ranges[i].last
      @ranges[i] = nil
      newmax
    else
      max
    end
  end

  def _delete_subset2(i, min)
    while 0 <= i and @ranges[i].first >= min do
      @ranges[i] = nil
      i = i - 1
    end

    if 0 <= i and @ranges[i].last >= min then
      newmin = @ranges[i].first
      @ranges[i] = nil
      newmin
    else
      min
    end
  end


  def _add(min, max)
    @ranges.each_with_index do |r, i|
      if r.first <= min then
        if r.last >= min then
          if r.last < max
            newmax = _delete_subset(i + 1, max)
            @ranges[i] = Range.new(r.first, newmax)
          end

          return
        end
      else
        if r.last <= min then
          if r.last < max then
            newmax = _delete_subset(i + 1, max)
            @ranges[i] = Range.new(min, newmax)
          elsif r.first != min then
            newmin = _delete_subset2(i - 1, min)
            @ranges[i] = Range.new(newmin, r.last)
          end

          return
        end
      end
    end

    @ranges.push(Range.new(min, max))
    @ranges.sort! {|a, b| a.first <=> b.first}
  end

  def neg(min, max)
    cmin = min
    ocmin = cmin
    cmax = min
    res = []
    @ranges.each do |r|
      if r.last > max then
        if ocmin != cmax then
          res.push(Range.new(ocmin, cmax))
        end

        return res
      end

      if r.first > cmax then
        cmax = r.first
      end

      if r.last > cmin then
        cmin = r.last
      end

      if ocmin != cmax then
        res.push(Range.new(ocmin, cmax))
      end

      ocmin = cmin
    end

    if ocmin != max then
      res.push(Range.new(ocmin, max))
    end

    return res
  end

  def to_s
    @ranges
  end
end

class VectorBagInternal
  include AngleParameter

  def initialize
    @bag = []
    @matrix_index = nil
    @other_index = nil
    @tlen = 0
    @vnum = 0
    @mtsize = 0
  end

  def push(v)
    @bag.push v
    @tlen = @tlen + v.size
    if @other_index then
      add(v)
    end
  end

  def arign_matrix(p)
    if @mtsize != 0 then
#     printf("(%d, %d)\n", (p.x / @mtsize).to_i, (p.y / @mtsize).to_i)
      [(p.x / @mtsize).to_i, (p.y / @mtsize).to_i]
    else
      [0, 0]
    end
  end

  def add(v)
    each_line_internal(v[0], v[1]) do |x, y|
      if @matrix_index[x] == nil then
        @matrix_index[x] = {}
      end
      if @matrix_index[x][y] == nil then
        @matrix_index[x][y] = []
      end 
      @matrix_index[x][y].push v
    end
  end

  def make_index
    @matrix_index = {}
    @other_index = []
    if @bag.size != 0 then
      @mtsize = (@tlen / @bag.size) / VECTOR_AREA_SIZE
#     @mtsize = (@tlen / @bag.size)  # オリジナルoriginal
      @bag.each do |v|
        add(v)
      end
    else
      @mtsize = 0
    end
  end
  
  def each_line_internal(st, ed)
    stx, sty = arign_matrix(st)
    edx, edy = arign_matrix(ed)
    x = stx
    y = sty
    sgnx = (stx < edx) ? 1 : -1
    sgny = (sty < edy) ? 1 : -1
    dx = (edx - stx).abs + 1
    dy = (edy - sty).abs + 1
    cnt = 0
    xcnt = dx
    while xcnt > 0 do
      yield(x, y)
      cnt += dy
      while cnt > dx do
        cnt -= dx
        y += sgny
        yield(x, y)
      end

      if cnt == dx then
        cnt = 0
        y += sgny
        yield(x, y)
      end
      x += sgnx
      xcnt -= 1
    end          
  end

  def each(cp0 = nil, cp1 = nil)
    if @other_index == nil then
      make_index
    end

    if cp0 == nil then
      @bag.each do |v|
        yield v
      end
    else
      if cp1 == nil then
        raise "Illgal argument"
      end

      @other_index.each do |v|
        yield v
      end

      each_line_internal(cp0, cp1) do |x, y|
        if @matrix_index[x] and @matrix_index[x][y] != nil then
          @matrix_index[x][y].each do |v|
            yield v
          end
        end
      end
    end
  end

  def each_with_limit(org, dis)
    if @other_index == nil then
      make_index
    end
    dissq = dis + @mtsize * 1.42
    dissq = dissq * dissq
    
    @matrix_index.each do |xi, xarr|
      xarr.each do |yi, yarr|
        x  = xi * @mtsize
        y  = yi * @mtsize
        dx = org.x - x
        dy = org.y - y
        if (dx * dx + dy * dy) > dissq then
          break
        end
        yarr.each do |v|
          yield v
        end
      end
    end
  end

  def each_line(cp0, cp1)
    if @other_index == nil then
      make_index
    end

    each_line_internal(cp0, cp1) do |x, y|
      if @matrix_index[x] and @matrix_index[x][y] != nil then
        @matrix_index[x][y].each do |v|
          yield v
        end
      end
    end
  end
end

class VectorBag
  def initialize
    @bag = {:parm => VectorBagInternal.new, 
            :temp => VectorBagInternal.new, 
            :none => VectorBagInternal.new, }
  end

  def [](cate)
    @bag[cate]
  end

  def parm_add(vec)
    @bag[:parm].push vec
  end

  def temp_add(vec)
    @bag[:temp].push vec
  end

  def add(vec, place)
    @bag[place].push vec
  end
  
  def temp_clear
    @bag[:temp] = []
  end

  def temp_pop
    @bag[:temp].pop
  end

  def filter(point, maxlen, minlen, plist)
    res = []
    plist.each do |pl|
      @bag[pl].each_with_limit(point, maxlen) do |v|
        p12 = v[1] - v[0]
        pc1 = point - v[0]
        t = pc1.inner_product(p12) / p12.inner_product(p12)
        if t > 1 then
          t = 1
        end
        if t < 0 then
          t = 0
        end

        pl = GeoPoint.new(v[0].x + p12.x * t, v[0].y + p12.y * t)

        dis = point.distance(pl)
        if  dis <= maxlen and dis >= minlen then
          res.push v
        end

=begin
        pf = false
        if point.distance(v[0]) < len or
           point.distance(v[1]) < len then
          res.push v
          pf = true
        end
        if pf and (point.distance(v[0]) > len or
           point.distance(v[1]) > len) then
#         print "**** foo ****"
        end
=end
      end
    end

    res
  end
end

class Vector
  def initialize(p0, p1)
    @points = [p0, p1]
  end

  def [](n)
    @points[n]
  end

  def size
    @points[0].distance(@points[1])
  end

  def angle_range(pt)
    res = []
    [0, 1].each do |i|
      tv = @points[i] - pt
      tvl = Math.sqrt(tv.x * tv.x + tv.y * tv.y)
      if tvl != 0 then
        res.push((Math.atan2(tv.y, tv.x) * 180 / Math::PI) % 360)
      end
    end

    if res.size == 1 then
      res = [res[0], res[0]]
    end

    if res.size == 0 then
      return []
    end

    if res[0] > res[1] then
      res[0], res[1] = res[1], res[0]
    end

    if res[1] - res[0] > 180 then
      res = [[0, res[0]], [res[1], 360]]
    elsif res[1] - res[0] == 180
      # ある直線の中に基準点が入っている
      res = []
    else
      res = [[res[0], res[1]]]
    end

    res
  end
end

class AvoidPointTable
  def initialize
    @table = {}
  end

  def table_pos(p)
    x = p.x
    y = p.y
    xpos = (x / 3).to_i
    ypos = (y / 3).to_i

    [xpos, ypos]
  end

  def add(pt, m)
    xpos, ypos = table_pos(pt)
    if @table[xpos] == nil then
      @table[xpos] = {}
    end
    if @table[xpos][ypos] == nil then
      @table[xpos][ypos] = {}
    end
    @table[xpos][ypos][pt] = m
  end

  def inspect
    res = ""
    xmax = @table.keys.inject(0) {|max, item| (max < item) ? item : max}
    (0..xmax).each do |x|
      if @table[x] then
        ymax = @table[x].keys.inject(0) {|max, item| (max < item) ? item : max}
        (0..ymax).each do |y|
          if n = @table[x][y] then
            res += sprintf("%-3d ", n.size)
          else
            res += "    "
          end
        end
      end
      res += "\n"
    end

    res
  end

  def each(pt)
    xpos, ypos = table_pos(pt)
    [0, 1, -1].each do |xoff|
      [0, 1, -1].each do |yoff|
        if defined?(@table[xpos + xoff][ypos + yoff]) and
           @table[xpos + xoff][ypos + yoff] then
          @table[xpos + xoff][ypos + yoff].each do |p, m|
            yield(p, m)
          end
        end
      end
    end
  end
end

class AngleResolver
  include MessageUtil
  include VectorUtil
  include AngleParameter

  def initialize(scale)
    @vector_bag = VectorBag.new
    @scale = scale
    @avoid_point_table = AvoidPointTable.new
  end

  def add_vector(st, ed, pl = :parm)
    @vector_bag.add(Vector.new(st, ed), pl)
=begin
    device = VISIO::VisioDevice.instance
    sh = device.draw_line(st.scalex, st.scaley, ed.scalex, ed.scaley)
    device.set_line_attribute(sh, 0.25, 1, 2)
=end
  end

  def add_tmp_vector(st, ed)
    @vector_bag.temp_add(Vector.new(st, ed))
  end

  def add_avoid_point(pt, m = 1.0)
    @avoid_point_table.add(pt, m)
  end

  def compute_avoid_distance(p, cutp)
    res = 0.0
    if cutp then
      @avoid_point_table.each(p) do |ap, m|
        dis = ap.distance(p)
        dis = Math.sqrt(dis)
        if dis != 0.0 then
          res += (m / dis)
        else
          res = 0
        end

        if cutp < res then
=begin
           print "#{cutp} #{res} #{p}\n"
=end
          return res
        end
      end
    else
      @avoid_point_table.each(p) do |ap, m|
        dis = ap.distance2(p)
        if dis != 0.0 then
          res += (m / dis)
        else
          res = 0
        end
      end
    end

    res
  end

  def compute_label_pos(origin, message)
    width, height = text_size(message)
    hlen = height + MIN_LABEL_LINE
#    hlen = height
    lang = nil

    tmplabpos = nil
    labpos = nil
    wang = nil
    tmptextrect = nil
    textrect = nil
    minapoint = nil
  
    donep = false
    begin
      lrng = compute_label_angle(origin, hlen, hlen * MIN_DISTANCE)
#      lrng = compute_label_angle(origin, hlen, 0)
      lrng.each do |erng|
        lang = erng.first + ANGLE_MARGIN
        while lang < (erng.last - ANGLE_MARGIN) do
          tmplabpos = origin.move(hlen, lang)
          tmpwang, tmptextrect = compute_textrect(width, height, lang, tmplabpos)
          if !check_cross(tmptextrect[1], tmptextrect[3], [:parm, :temp]) and
             !check_cross(tmptextrect[2], tmptextrect[3], [:parm, :temp]) and
             !check_cross(tmptextrect[0], tmptextrect[2], [:parm, :temp]) and
             !check_cross(tmptextrect[0], tmptextrect[1], [:parm, :temp]) then

            nminap = 0.0
            crossw = LINE_CROSS_RATE * check_cross_num(origin, tmplabpos, [:parm])
            cutp = nil
            if minapoint then
              cutp = minapoint / (1.0 + crossw)
            end
#           (10..10).each do |n|
#           end
            nminap += compute_avoid_distance(origin.move(hlen, lang), cutp)
            nminap += (crossw * nminap.abs)
            if minapoint == nil or nminap < minapoint then
#             p check_cross_num(origin, tmplabpos, [:parm])
              minapoint = nminap
              labpos = tmplabpos
              textrect = tmptextrect
              wang = tmpwang
              donep = true
            end
          end
          lang = lang + ANGLE_STEP
        end
      end
      hlen = (hlen + LABEL_GROTH_STEP) * 1.0
    end until donep == true or hlen > MAX_LABEL_LINE

    if donep == false then
      lrng = compute_label_angle(origin, hlen, 0, [[:parm]])
      erng = lrng[0]
      lang = (erng.first + erng.last) / 2 + 1
      labpos = origin.move(hlen, lang)
      wang, textrect = compute_textrect(width, height, lang, labpos)
      p "Give Up"
    end

#   p @avoid_point_table

    [labpos, wang, textrect, minapoint]
  end

  def check_cross(c0, c1, place)
      place.each do |pl|
        va = @vector_bag[pl]
        va.each_line(c0, c1) do |p|
          if cross_vectorp(c0, c1, p[0], p[1]) then
            return true
          end
        end
      end

      return false
  end

  def check_cross_num(c0, c1, place)
      num = 0
      place.each do |pl|
        va = @vector_bag[pl]
        va.each_line(c0, c1) do |p|
          if cross_vectorp(c0, c1, p[0], p[1]) then
            num = num + 1
          end
        end
      end

      return num
  end

  def compute_label_angle(pos, reqlenmax, reqlenmin, catelst = [[:parm, :temp], [:parm]])
    labang_range = []
    catelst.each do |cate|
      disang = collect_disable_angle(pos, cate, reqlenmax, reqlenmin)
      labang_range = search_free_angle(disang, pos, reqlenmax)

      if labang_range.size != 0 then
        break
      end
    end

    if labang_range.size == 0 then
      labang_range = [Range.new(0, 0)]
    end

    labang_range
  end

  def collect_disable_angle(pos, place, maxlen, minlen)
      maxlen = maxlen * (@scale / 100)
      minlen = minlen * (@scale / 100)
      va = @vector_bag.filter(pos, maxlen, minlen, place)
      range_set = RangeSet.new
      va.each do |n|
        ang = n.angle_range(pos)
        ang.each do |a|
          range_set.add(a)
        end
      end

      range_set
  end

  def search_free_angle(range_set, pos, len)
    sz = 0
    wr = nil
    free = range_set.neg(0, 360)
#   free = free.sort {|a, b| (b.last - b.first) <=> (a.last - a.first)}

    free
  end
end