ポリゴンの走査変換

概要

ポリゴンを直線の走査線ベクトルに変換するrubyスクリプトを作りました。こんな感じになります。ポリゴンをピクセル塗りつぶしする（ラスター変換）サンプルコードはすぐ見つかるのですが、ベクトル変換するものはありそうで見つからなかったのでシェアします。

想定シーン

CADでよく使われるDXFデータを走査型の加工機に流し込むためのデータに変換をする場合など。なお、DXFはポリゴン(POLYLINEとかLWPOLYLINE)は頂点リスト(VERTEX)で表現されています。この辺のスクリプトを使ってDXFから頂点リストを出力させることができます。

コード

scanner.rb

# coding: utf-8
require 'optparse'
# Generate scan lines with pitch = _pitch_ and total = _total_
class Scanner
  # initialize _Scanner_ class
  # - pitch: pitch of scan lines
  # - total: total number of scan lines
  def initialize(pitch, total)
    @pitch = pitch
    @total = total
    @scanlines = []
  end

  # return Array of _scanline_ Objects from _polylines_ object
  def scan(polylines)
    @total.times do |n|
      scanline = Scanline.new(0, [])
      polylines.shape.each do |shape|
        shape.entity.each do |entity|
          scanline.cross_point(entity.vec, n * @pitch)
        end
        scanline.amend!
      end
      scanline.cp.sort_by!(&:last)
      @scanlines << scanline
    end
    @scanlines
  end
end

# Polylines object
# - composed of _Shape_
class Polylines < Struct.new(:shape)
  # Shape object
  # - comprising _Polylines_
  # - composed of _Entity_
  class Shape < Struct.new(:entity)
    # Entity object
    # - comprising _Shape_
    # - composed of _vec_
    class Entity < Struct.new(:vec)
      # convert [x1,y1,x2,y2] to [x1, y1, dx, dy]
      # where dx = x2 - x1 and dy = y2 - y1
      def to_v
        [vec[0], vec[1], vec[2] - vec[0], vec[3] - vec[1]]
      end
    end
  end
end

# Scanline object that stores vertices of a scanning line.
class Scanline < Struct.new(:checksum, :cp)
  # Find and store vertices of each scanline
  # * vec: an _Array_ of 4 elements.
  # * npx: the x position of the scanning line.
  #  scanline.cross_point([x1,y1,x2,y2], x)
  def cross_point(vec, npx)
    x1, y1, x2, y2 = vec
    if x1 == x2 # vertical line entity
    # self.cp << [x1,y1]
    # self.cp << [x2,y2]
    # self.checksum += 2
    elsif y1 == y2 # horizontal line entity
      if npx.between?([x1, x2].minmax[0], [x1, x2].minmax[1])
        cp << [npx, y1]
        self.checksum += 1
      end
    else # incline line entity
      y = (npx - x1) * (y1 - y2) / (x1 - x2) + y1
      if  y.between?([y1, y2].minmax[0], [y1, y2].minmax[1])
        cp << [npx, y]
        self.checksum += 1
      end
    end
  end

  # Ensure consistency by checking checksum
  def amend!
    original_size = cp.size
    if self.checksum.odd?
      cp.uniq!
      self.checksum -= (original_size - cp.size)
    end
  end
end

if __FILE__ == $PROGRAM_NAME
  # usage: ruby scanner.rb -f polyline.csv -p 1 -t 100 > scanline.csv
  params = ARGV.getopts('f:p:t:', 'file', 'pitch:1', 'total:100')

  # Load polyline data
  # format: x1, y1, x2, y2
  # where x1, y1, x2 and y2 are the vertices of polylines.
  # each set of polylines should be separated by a blank line.
  polylines = Polylines.new([])
  shape = Polylines::Shape.new([])
  fp = File.open(params['f'])
  fp.each_line do |line|
    if line == "\n"
      polylines.shape << shape
      shape = Polylines::Shape.new([])
    else
      shape.entity << Polylines::Shape::Entity.new(line.split(' ').map(&:to_f))
    end
  end

  # Generate scan lines
  scanner = Scanner.new(params['p'].to_f, params['t'].to_i)
  scanlines = scanner.scan(polylines)

  #-----------#
  # output #
  #-----------#

  # Polygon Data
  polylines.shape.each do |shape|
    shape.entity.each do |entity|
      puts entity.to_v.join(' ')
    end
  end

  puts "\n\n"

  # Scan Line Data
  scanlines.each do |line|
    line.cp.each_slice(2) do |cp1, cp2|
      vec = Polylines::Shape::Entity.new([cp1, cp2].flatten).to_v
      puts vec.join(' ')
    end
  end

  puts "\n\n"

  # Scan Cross Point Data
  scanlines.each do |line|
    line.cp.each do |point|
      puts point.join(' ')
    end
  end

end

実行

必要な情報としては、ポリゴンデータ、走査線のピッチ、走査線の総数があります。ポリゴンデータをpolyline.csv、走査線のピッチを1、走査線の総数を100とした場合の実行例は下記の通り。

 ruby scanner.rb -f polyline.csv -p 0.5 -t 200 > scanline.csv

読み込ませるポリゴンデータは頂点リストではなく、ポリゴンの各辺(edge)の始点(x1,y1)と終点(x2,y2)のデータになります。スペース区切りです。各ポリゴンは空行で区切ります。例えば上の画像は以下のデータから生成されています。

polyline.csv

56.213203 49.142136 49.142136 56.213203
49.142136 56.213203 38.535534 38.535534
38.535534 38.535534 56.213203 49.142136
56.213203 49.142136 56.213203 49.142136

40.000000 60.000000 30.000000 60.000000
30.000000 60.000000 35.000000 40.000000
35.000000 40.000000 40.000000 60.000000
40.000000 60.000000 40.000000 60.000000

49.142136 13.786797 56.213203 20.857864
56.213203 20.857864 38.535534 31.464466
38.535534 31.464466 49.142136 13.786797
49.142136 13.786797 49.142136 13.786797

20.857864 56.213203 13.786797 49.142136
13.786797 49.142136 31.464466 38.535534
31.464466 38.535534 20.857864 56.213203
20.857864 56.213203 20.857864 56.213203

77.000000 37.000000 83.000000 37.000000
83.000000 37.000000 83.000000 43.000000
83.000000 43.000000 77.000000 43.000000
77.000000 43.000000 77.000000 37.000000
77.000000 37.000000 77.000000 37.000000

70.000000 50.000000 90.000000 50.000000
90.000000 50.000000 90.000000 10.000000
90.000000 10.000000 70.000000 10.000000
70.000000 10.000000 70.000000 50.000000
70.000000 50.000000 70.000000 50.000000

75.000000 15.000000 85.000000 15.000000
85.000000 15.000000 85.000000 45.000000
85.000000 45.000000 75.000000 45.000000
75.000000 45.000000 75.000000 15.000000
75.000000 15.000000 75.000000 15.000000

10.000000 40.000000 10.000000 30.000000
10.000000 30.000000 30.000000 35.000000
30.000000 35.000000 10.000000 40.000000
10.000000 40.000000 10.000000 40.000000

35.000000 65.000000 65.000000 65.000000
65.000000 65.000000 65.000000 5.000000
65.000000 5.000000 35.000000 5.000000
35.000000 5.000000 35.000000 65.000000
35.000000 65.000000 35.000000 65.000000

13.786797 20.857864 20.857864 13.786797
20.857864 13.786797 31.464466 31.464466
31.464466 31.464466 13.786797 20.857864
13.786797 20.857864 13.786797 20.857864

37.000000 83.000000 37.000000 77.000000
37.000000 77.000000 43.000000 77.000000
43.000000 77.000000 43.000000 83.000000
43.000000 83.000000 37.000000 83.000000
37.000000 83.000000 37.000000 83.000000

30.000000 10.000000 40.000000 10.000000
40.000000 10.000000 35.000000 30.000000
35.000000 30.000000 30.000000 10.000000
30.000000 10.000000 30.000000 10.000000

50.000000 90.000000 50.000000 70.000000
50.000000 70.000000 10.000000 70.000000
10.000000 70.000000 10.000000 90.000000
10.000000 90.000000 50.000000 90.000000
50.000000 90.000000 50.000000 90.000000

60.000000 30.000000 60.000000 40.000000
60.000000 40.000000 40.000000 35.000000
40.000000 35.000000 60.000000 30.000000
60.000000 30.000000 60.000000 30.000000

15.000000 85.000000 15.000000 75.000000
15.000000 75.000000 45.000000 75.000000
45.000000 75.000000 45.000000 85.000000
45.000000 85.000000 15.000000 85.000000
15.000000 85.000000 15.000000 85.000000

コードの説明

読み込んだ各辺のデータをEntityクラス、各ポリゴンをEntitityクラスの配列からなるShapeクラス、すべてのポリゴンをShapeクラスの配列からなるPolylinesクラスのインスタンスとして生成しています。一方、出力される走査線の各ベクトルはScanlineオブジェクトに貯め込まれます。

PolylinesオブジェクトからScanlineオブジェクトの生成はScannerクラスが担当しています。ただScanline自体が、辺(Entity)との交点を見つけるcross_pointメソッドを持っています。なんか美しくないので後で修正するかも。

バグがあったらコメントもらえると嬉しいです。

参考

DXF

Autodesk
DXFの活用
DXF memo
DXF読み出し

Scan Line Algorithm

Scan-Line Fill Scan-Line Algorithm
走査変換