c++ - 有时等边有时不等边的三角形？

Question

我正在尝试在控制台屏幕上生成随机的等边三角形。

我使用的方法是为三角形创建一个中心点(随机定位)，将中心点移动到原点 (0,0)，然后从中心创建 3 个点(添加半径(随机数)三角形到每个点的 Y 轴)。然后我旋转 2 个点，一个旋转 120 度，另一个旋转 240 度，形成一个等边三角形，然后在这些点之间画线。然后将点带回与质心相关的原始绘图。

这在过去的大部分时间都有效，我得到了一个等边三角形，但其他时候我并没有完全得到一个等边三角形，我完全不知道为什么。

我正在使用 Brensenham 的线算法在点之间画线。

工作三角形的图像:http://imgur.com/GpF406O

splinter 三角形的图像:http://imgur.com/Oa2BYun

这是绘制三角形坐标的代码:

void Triangle::createVertex(Vertex cent)
{
// angle of 120 in radians
double s120 = sin(2.0943951024);
double c120 = cos(2.0943951024);
// angle of 240 in radians
double s240 = sin(4.1887902048);
double c240 = cos(4.1887902048);

// bringing centroid to the origin and saving old pos to move later on
int x = cent.getX();
int y = cent.getY();
cent.setX(0);
cent.setY(0);

// creating the points all equal distance from the centroid
Vertex v1(cent.getX(), cent.getY() + radius);
Vertex v2(cent.getX(), cent.getY() + radius);
Vertex v3(cent.getX(), cent.getY() + radius);

// rotate points
double newx = v1.getX() * c120 - v1.getY() * s120;
double newy = v1.getY() * c120 + v1.getX() * s120;

double xnew = v2.getX() * c240 - v2.getY() * s240;
double ynew = v2.getY() * c240 + v2.getX() * s240;

// giving the points the actual location in relation the the old pos of the centroid
v1.setX(newx + x);
v1.setY(newy + y);

v2.setX(xnew + x);
v2.setY(ynew + y);

v3.setX(x);
v3.setY(y + radius);

// adding the to a list (list is used in a function to draw the lines)
vertices.push_back(v1);
vertices.push_back(v2);
vertices.push_back(v3);
}

Answer 1

查看两个三角形的图像(并查看线条绘制算法)，您将线条绘制为一系列离散像素。这意味着一个顶点必须落在一个像素中(它不能在边界上)，就像这个 image .

那么，如果您的顶点落在*像素之间的边界上会怎样？您的画线算法必须决定将顶点放入哪个像素。

查看wikipedia上的算法描述和页面上的 C++ 实现 www.cs.helsinki.fi我看到两个列表实现都使用整数算术**，在这种情况下，考虑到您有谨慎的像素行，这并不是不合理的。这意味着如果您的浮点计算将一个顶点放在下一行像素的整数标签阈值之上，当 floor(从 float 转换为整数)完成时，但另一个顶点低于该阈值，那么这两个顶点将放在不同的行上。

想想 v1.y = 5.00000000000000000001 和 v2.y = 4.9999999999999999999 这导致 v1 被放置在第 5 行，v2 被放置在第 4 行。

这解释了为什么您只是偶尔看到问题发生，您只是偶尔让您的顶点落在这样的边界上。

为了解决一些问题:

在为顶点赋值时修复它，y 值无论如何都是相同的。

给出:

v1.getX() = v2.getX() = 0 (defined by your code)
v1.getY() = v2.getY() = radius (defined by your code)
cos(120 degrees) = cos(240 degrees) ('tis true)

这会将您的两个 y 值减少为

double newy = v1.getY() * c120
double ynew = v1.getY() * c120

因此:

v1.setY(newy + y);
v2.setY(newy + y);

如果您编写了自己的 Brensenham 算法实现，您可以在该代码中添加一个检查以确保您的顶点处于相同的高度，但是由于端点的高度，这似乎是放置这种检查的一个非常糟糕的地方特定于您的问题，而不是笼统地画线。

---

*或不完全正确，但足够接近，在考虑浮点错误后您无法分辨差异

**该算法不限于整数运算，但我怀疑考虑到您的问题的不规则性和算法的呈现方式，以及您对图像中的行使用谨慎字符的事实整数算术是个问题。