假设我有一个三角形，其三个整数顶点为(x1,y1)，(x2,y2)和(x3,y3)。我可以使用什么样的算法来返回所有在三角形内的(x,y)整数对的全面列表。
在IT技术中，如何获取一个三角形内位置的列表，其形式为x,y坐标？
4
- CodeGuy
4
那将是无限多的点，除非你加上某种约束条件，例如坐标为整数？ - Paul R
请具体说明。如果@PaulR是正确的，那么解决方案与我在答案中提出的非常不同。 - Alexandre C.
2你强调想要所有的二元组，但显然有无数个。你是指整数对吗？如果是这样，那么这就是光栅化问题，关于这个主题有广泛的文献资料。这是一个不错的教程：http://joshbeam.com/articles/triangle_rasterization/你可能需要根据“内部”的含义进行微调，因为我不知道你是否想包括边界。 - sigfpe
现在问题已经更新，指定结果的x，y坐标必须是整数，那么知道顶点的坐标是否也是整数可能会很有用？ - Paul R
5个回答
4
这个问题的正式名称是三角形光栅化rasterization。
这是一个经过充分研究的问题，有各种各样的方法可以解决它。两种流行的方法是：
逐行扫描。
对于每条扫描线，您需要一些基本几何知识来重新计算线的起点和终点。请参见Bresenham的直线绘制算法。
测试边界框中的每个像素是否在三角形内。
这通常是通过使用重心坐标来完成的。
描述如何使用方法2）的原始论文是由Juan Pineda在1988年撰写的，名为“多边形光栅化的并行算法”。
对于三角形而言，在概念上非常简单（如果您学习了重心坐标）。如果将每个像素转换为三角形重心坐标alpha、beta和gamma，则简单的测试是alpha、beta和gamma必须介于0和1之间。
- Tim Gee
2
以下算法应该是适当的：
Sort the triangle vertices by x coordinate in increasing order. Now we have two segments (1-2 and 2-3) on the one side (top or bottom), and one segment from the other one (1-3).
Compute coefficients of equations of lines (which contain the segments):
A * x + B * y + C = 0 A = y2 - y1 B = x1 - x2 C = x2 * y1 - x1 * y2There (x1, y1) and (x2, y2) are two points of the line.
For each of ranges [x1, x2), (x2, x3], and x2 (special case) iterate over integer points in ranges and do the following for every x:
- Find top bound as y_top = (- A1 * x - C1) div B1.
- Find bottom bound as y_bottom = (- A2 * y - C2 - 1) div B2 + 1.
- Add all points between (x, y_bottom) and (x, y_top) to the result.
- citxx
0
我喜欢光线投射，这在维基百科文章中有很好的描述。我在我的项目中使用了它来达到同样的目的。该方法也适用于其他多边形，包括凹多边形。不确定其性能如何，但编码很容易，所以你可以自己尝试（在我的项目中没有性能问题）。
- Dmitry Polyanitsa
0
如果你正在处理光栅化填充，那么我们可以跳过更复杂的算法，比如Bresenham线算法，因为我们不关心如何获得“1像素粗线的最佳光栅化”，我们想要所有坐标位于三角形边界内部，并且能够控制边界上的坐标应该怎样处理（我们是排除所有这些坐标吗？还是全部包含？如果它们至少有50%在三角形内部，我们只包含它们吗？）。
这简化了很多事情。
我们可以构建一系列x间隔（而不是y方向），这样我们就可以在2D数组中按行读取连续的值段，或者在1D压缩数组中读取简单的值段，唯一的挑战是“找到每个坐标值段的正确起始和结束点”：
将你的三个坐标按y坐标排序。称顶点为P1，底部点为P3，中间点为P2。
计算三条线P1--P3、P1--P2和P2--P3的表达式。
P1--P3作为y的函数为x = P1.x + (P3.x-P1.x)/(P3.y-P1.y) * (y - P1.y)P1--P2作为y的函数为x = P1.x + (P2.x-P1.x)/(P2.y-P1.y) * (y - P1.y)P2--P3作为y的函数为x = P2.x + (P3.x-P2.x)/(P3.y-P2.y) * (y - P2.y)
P1添加到您的集合中。
对于每一个i=1到i=(P3.y - P1.y)，执行以下操作：
- 设置
y=P1.y+i - 计算当前
y在P1--P3上的x1 - 计算
x2：- 如果
i < (P2.y - P1.y)，则为当前y在P1--P2上计算x2 - 否则，计算
x2时应该在P2--P3上使用当前的y
- 如果
- 将从
min(x1,x2)到max(x1,x2)的所有坐标添加到您的集合中。
当然，我们需要将那些min和max值转换为整数而不是浮点数，并根据我们对边界像素的包含/排除策略，有不同的选择：
- 对于“在三角形内部的任何程度”的点，使用
floor(min(x1,x2))和ceil(max(x1,x2))， - 对于“完全在三角形内部”的点，使用
ceil(min(x1,x2))和floor(max(x1,x2))，以及 - 对于“至少一半在三角形内部”的点，使用
round(min(x1,x2))和round(max(x1,x2))。
const { random, PI, min, max, floor, ceil } = Math;
const cvs = document.querySelector(`canvas`);
const w = (cvs.width = 400);
const h = (cvs.height = 180);
const ctx = cvs.getContext(`2d`);
const pts = [
{ x: random() * w, y: random() * h },
{ x: random() * w, y: random() * h },
{ x: random() * w, y: random() * h },
];
const [P1, P2, P3] = pts.sort((a, b) => a.y - b.y);
const f12 = (y) => P1.x + ((P2.x - P1.x) / (P2.y - P1.y)) * (y - P1.y);
const f13 = (y) => P1.x + ((P3.x - P1.x) / (P3.y - P1.y)) * (y - P1.y);
const f23 = (y) => P2.x + ((P3.x - P2.x) / (P3.y - P2.y)) * (y - P2.y);
// Let's gather up our points!
const allPoints = [P1];
// We're skipping by 5, instead of 1, because otherwise we'll
// just end up coloring every pixel, which is not as useful
// as illustrative code example.
for (let i = 1; i < P3.y - P1.y; i += 4) {
const y = P1.y + i;
const x1 = f13(y);
const f = i < P2.y - P1.y ? f12 : f23;
const x2 = f(y);
const x = floor(min(x1, x2));
const X = ceil(max(x1, x2));
// Same here, we're skipping by 5, rather than 1, purely
// for illustrative purposes.
for (let j = 0; j < X - x; j += 5) {
allPoints.push({ x: x + j, y });
}
}
// And then let's draw them out to see how we did.
ctx.strokeStyle = `#C00`;
ctx.beginPath();
ctx.moveTo(P1.x, P1.y);
allPoints.forEach((p) => {
const { x, y } = p;
ctx.moveTo(x, y);
ctx.arc(x, y, 0.1, 0, 2 * PI);
});
ctx.stroke();
ctx.strokeStyle = `#F3F6`;
ctx.beginPath();
ctx.moveTo(P1.x, P1.y);
ctx.lineTo(P2.x, P2.y);
ctx.lineTo(P3.x, P3.y);
ctx.lineTo(P1.x, P1.y);
ctx.stroke();canvas {
border: 1px solid black;
}<canvas></canvas>当然：记得考虑边缘情况：如果P1和P2在同一行，或者如果P2和P3在同一行，则算法简化为不基于哪个值i拆分“要使用哪个函数”：我们只需始终使用另一个线条计算x2 =)
- Mike 'Pomax' Kamermans
0
我猜你有一堆要测试的成对数据（如果这不是你问题所在，请明确你的问题）。首先，你应该将这些成对数据存储到四叉树或kd-tree结构中，以便有一个足够小的候选集。如果你只有几个点，这可能不值得麻烦（但如果不这样做，它就不能很好地扩展）。
你还可以通过针对三角形的边界框进一步缩小候选范围。
然后，对于每个候选对(x, y)，在a，b，c中解决系统问题。
a + b + c = 1
a x1 + b x2 + c x3 = x
a y2 + b y2 + c y3 = y
（我让你自己解决这个问题），如果a、b和c都是正数，那么点就在三角形内部。
- Alexandre C.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接