3

Scala Javaコードに適応したブレゼンハムのアルゴリズムの次のコードがありました。

def bresenham(x0: Int, y0: Int, x1: Int, y1: Int) = {
    import scala.math.abs

    val dx = abs(x1 - x0)
    val dy = abs(y1 - y0)

    val sx = if (x0 < x1) 1 else -1
    val sy = if (y0 < y1) 1 else -1

    new Iterator[(Int, Int)] {
      var (x, y) = (x0, y0)
      var err = dx - dy

      def next = {
        val omitted = (x, y)
        val e2 = 2 * err
        if (e2 > -dy) {
          err -= dy
          x += sx
        }
        if (e2 < dx) {
          err += dx
          y += sy
        }
        omitted
      }

      def hasNext = (x <= x1 && y <= y1)
    }
  }

ほとんどすべての行ですべてうまくいきますが、上から下への垂直線を計算しようとすると (つまり(0,3) -> (0,0) )、何も得られません。
問題はそれほど難しくなく、上記のケースではノーと言うところにあるので、私は自分自身について愚かだと感じていhasNextます）。 ポイントを交換することで対処しましたが、明らかに悪い解決策です。アルゴリズムを一般化するのを手伝ってくれる人はいますか?

4

2 に答える 2

4

y0 = 3失敗した場合は、 からに移動しようとしていますy1 = 0。したがって、ステップは負になりsy = -1ます。で続行するための条件は、何を書いたかではなくhasNext、依存する必要があります ( )。y >= y1y <= y1

hasNextどちらの方向にも対応できるように一般化する必要があります。賢い方法は、

def hasNext = (sx*x <= sx*x1 && sy*y <= sy*y1)

sxとsyが非ゼロであり、その符号がステップの方向を決定するため、これは機能します。

于 2011-08-16T18:49:12.063 に答える
2

ウィキペディアコードのかなり直訳は次のようになります。

def hasNext = (!(x==x1 && y==y1))
于 2011-08-16T19:00:59.470 に答える