1

我得到了这些代表方格纸的数组，或者如果你愿意，也可以是像素。为了在这个线程中保持一致性，让“1”代表一个黑色单元格，“0”代表一个白色单元格。

现在，我想从 A 点到 B 点画一条（黑色）直线。我不能只使用普通的http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm，因为我需要将每个单元格变黑如果它是一张方格纸，并且从正方形 A 的中心到正方形 B 的中心画一条线，那将会被击中。

所以这些应该如下工作：

+—+—+—+    +—+—+—+
|A| | |    |█| | |
+—+—+—+    +—+—+—+
| | | |    |█|█| |
+—+—+—+    +—+—+—+
| | | | →  | |█|█|
+—+—+—+    +—+—+—+
| | |B|    | | |█|
+—+—+—+    +—+—+—+

+—+—+—+    +—+—+—+
|A| | |    |█| | |
+—+—+—+    +—+—+—+
| | | | →  | |█| |
+—+—+—+    +—+—+—+
| | |B|    | | |█|
+—+—+—+    +—+—+—+

+—+—+—+    +—+—+—+
|A| | | →  |█|█| |
+—+—+—+    +—+—+—+
| | |B|    | |█|█|
+—+—+—+    +—+—+—+

随意想象这些草图更像方形，或者在一张方格纸上实际绘制它！它可能会澄清一些事情。

和往常一样，随时发布任何可能有帮助的内容。谢谢！

（一个解法

也使用这个例子。并使用我的框架使用的索引，因此它看起来与答案中的索引略有不同。

 X 0 1 2      X 0 1 2
Y +—+—+—+ →  Y +—+—+—+
0 |A| | | →  0 |█| | |
  +—+—+—+ →    +—+—+—+
1 | | | | →  1 |█|█| |
  +—+—+—+ →    +—+—+—+
2 | | | | →  2 | |█|█|
  +—+—+—+ →    +—+—+—+
3 | | |B| →  3 | | |█|
  +—+—+—+ →    +—+—+—+

A 是 (0,0) =: (a1,a2), B 是 (2,3) =: (b1,b2)，所以期望的点集是 {(0,0), (0,1), (1,1), (1,2), (2,2), (2,3)}

首先，我们将在实际纸上绘制的直线形式化。

Therefore first define constant m which holds our slope:

    (b2 - a2)
m = —————————
    (b1 - a1)

For arbitrary (A, B), the straight is now defined by:
g: y = (x - a1) · m + a2

and inverted:
ǵ: x = (y - a2) / m + a1

Note that for m = 0, the whole thing does fail. But a straight-to-the-right line does not only sound like a straightforward thing.

在这个例子中，直道是

m = 3/2
g: y = x * 3/2
ǵ: x = y * 2/3

我们将在我们的边界框中为这些函数提供“线值”（正好在 2 个整数 x 和 x+1 之间，广泛称为“x 和一半”）。所以首先我们将在 a1 和 b1 之间（饲料 g），然后在 a2 和 b2 之间（饲料 ǵ）：

g(0.5) = 1/2 * 3/2 = 0.75 // 1 < g(0.5) + 0.5 < 2
g(1.5) = 3/2 * 3/2 = 2.25 // 2 < g(1.5) + 0.5 < 3

ǵ(0.5) = 1/2 * 2/3 = 0.33 // 0 < ǵ(0.5) + 0.5 < 1
ǵ(1.5) = 3/2 * 2/3 = 1    // 1 < ǵ(1.5) + 0.5 < 2
ǵ(2.5) = 5/2 * 2/3 = 1.66 // 2 < ǵ(2.5) + 0.5 < 3
  1. 首先是指直线穿过第一条水平线上方（显示为“下方”）的第一条垂直线。变黑点：（0,1），（1,1）。
  2. 第二是指直线在第二条水平线上方穿过第二条垂直线。黑点：(1,2), (2,2)。
  3. 第三表示直线穿过第 0 条垂直线之后（显示为“右侧”）的第一条水平线。变黑点：（0,0），（0,1）。
  4. 第四是指直线在第一条垂直线之后穿过第二条水平线。黑点：（1,1），（1,2）。
  5. 第五是指直线在第二条垂直线之后穿过第三条水平线。黑点：(2,2), (2,3)。

所有点：{(0,1), (1,1), (1,2), (2,2), (0,0), (0,1) , (1,1) , (1,2 ) , (2,2) , (2,3)}

没有重复：{(0,0), (0,1), (1,1), (1,2), (2,2), (2,3)} （完全符合预期）

  • 因此，对于与第 x 条水平线上方的第 y 条垂直线相交的线，我们将 (x-1,y) 和 (x,y) 涂成黑色。
  • 而对于在第 y 条垂直线之后穿过第 x 条水平线的线，我们绘制 (x,y-1) 和 (x,y)。
  • （这里从不正确）对于在第 y 条垂直线上穿过第 x 条水平线的线，我们绘制 m > 0 (x-1,y-1) 和 (x,y)。如果 m < 0，则为 (x-1,y) 和 (x,y-1)

感觉差不多，这是我的想法。

有什么想法吗？请评论！

〜LDer〜

4

2 回答 2

2

假设我们正在使用这个示例：

+—+—+—+    +—+—+—+
|A| | |    |█| | |
+—+—+—+    +—+—+—+
| | | |    |█|█| |
+—+—+—+    +—+—+—+
| | | | →  | |█|█|
+—+—+—+    +—+—+—+
| | |B|    | | |█|
+—+—+—+    +—+—+—+

这是一个矩形3x4。

我们需要定义两个函数：
y(x) = 4 * (1 - x/3)
x(y) = 3 * (1 - y/4).

现在让我们在我们的矩形内x将所有整数传递给它们。 在每一步中，我们都用坐标和绘制黑色像素：y

[x; ceil(y(x)) - 1][ceil(x(y)) - 1; y - 1]

y(0) == 4      # paint 0;3
y(1) == 2.(6)  # paint 1;2
y(2) == 1.(3)  # paint 2;1

x(0) == 3      # paint 2;-1 (-1 is not a valid pixel coordinate, 
               # so we may just throw away this, as there are no pixels below y=0)
x(1) == 2.25   # paint 2;0
x(2) == 1.5    # paint 1;1
x(3) == 0.75   # paint 0;2

x(y)和函数都y(x)为您提供对角线上点的第二个坐标，当我们将整数值传递给它们时，我们会找到对角线与网格的交点。
-y函数将为我们提供所有垂直线的正确像素和x- 函数 - 在每个水平线下方（这就是为什么y - 1）。唯一的问题是拐角交叉点，可以通过另外一个条件来解决。

于 2013-07-30T12:27:40.137 回答
1

初始化 给出你的“正方形”坐标的顶点(x,y)。对于每个正方形，v1是左上角，v2是右上角，v3是右下角，v4是左下角。计算你的直线方程y = a*x + b。

算法

For each square do
    for each vertex of the square do
        calculate valueOfVertex = y - a*x - b
    if two valueOfVertex have an opposite sign
    then cellColor == 1
    else cellcolor == 0

输出应该是您所期望的。唯一的问题可能是一个valueOfVertex = 0和所有其他的都是严格的正面或负面的。但这很容易处理。

说明如果直线穿过正方形（或像素），您可以找到两个不在直线同一侧的顶点。所以一个位于正半平面，另一个位于负半平面。

改进一些简单的技巧会阻止您测试边界框的每个正方形。如果你发现一个完全在半平面的正方形，你可以丢弃一些正方形。在您的示例中，如果测试的正方形在线上方，您可以丢弃上方和右侧的所有正方形。

于 2013-07-30T12:17:01.763 回答