algorithm - 对称 DDA 是什么意思？

Question

我已阅读有关DDA的信息。但我刚刚遇到了对称 DDA一词。它是什么 ？它与DDA有何不同？

Answer 1

DDA（数字差分分析仪）算法用于线性（即直线）找出任何给定两点之间的插值点。现在，由于这是在数字计算机上完成的 - 速度是一个重要因素。

直线方程由 m=Δx/Δy eq(i) 给出，其中 Δx = x(2)-x(1) & Δy = y(2)-y(1)，
现在使用这个方程我们可以计算位于线上的连续点。但这是光栅图形的离散世界——所以我们需要积分坐标。

在简单的 DDA 中，eq(i) 被转换为 m=eΔx/eΔy，其中e，称为增量因子，是一个正实数。因为在分子和分母中放入相同的数字不会改变任何东西 - 但如果选择合适 - 它可以帮助我们生成离散点，从而减少必须四舍五入结果点的过载。

基本上我们需要做的是：将坐标增加一个固定的小量，从起点开始，每次我们有一个新点向终点前进。

在简单的 DDA 中 - e被选为 1/max(|Δx|,|Δy|) 使得其中一个坐标是整数，而只有另一个坐标必须是四舍五入的。即 P(i+1) = P(i)+(1,Round(e*Δy)) 这里一个坐标递增 1，另一个坐标递增 e*Δy

在对称 DDA 中 - e的选择使得虽然结果点的两个坐标都必须四舍五入，但它可以非常有效地完成，因此很快。

具体来说， e被选为 1/2^n，其中 2^(n-1) <= max(|Δx|,|Δy|) < 2^n。换句话说，线的长度被认为是 2^n 对齐的。两个坐标的增量为 e*Δx 和 e*Δy。With suitably chosen initial fraction part of the beginning coordinates: this causes the points to be generated as mixed fractions whose fractional parts are in a cyclic series , ie they repeat over a small length. 因此，可以根据两个固定长度的查找表轻松对结果坐标进行四舍五入，每个坐标一个。

有关示例，请参阅http://w3.msi.vxu.se/~gsu/DAB726-Ht06/Symm-DDA.pdf 。
注意结果坐标的小数部分的循环重复。