algorithm - 列出三角形内的积分平面点

Question

给定平面点 p,q,r 你如何确定三角形是否包含积分点？我想列出所有这些要点。

它有一个子问题：给定第四个点 s。如何判断 s 是否在三角形内？

标签： algorithmgeometry

Answer 1

你需要三角形光栅化。

可能的方法：按 Y 坐标对顶点进行排序，为顶点之间的每个垂直间隔确定边方程，并为该间隔中的每个整数 Y 获取左右整数点，然后填充内部点的整个水平扫描线。

例如，三角形的“左上角”边有2.2*y - x + 1.5 = 0y-range中的方程3.14..17.3。第一个整数 Y 是 4，代入得到10.3 - x = 0，所以最左边的整数 x 的值为 11。右边缘的类似过程给出最右边的值（比如 p），所以我们输出点(11,4), (12,4)...(p,4)

随意找到的文章

subproblem- 这是完全不同的问题。检索所有积分点不需要它。
如果你真的需要它 -用向量到点 ( )计算边的叉积符号AB x AP, BC x BP, CA x CP