无需双精度即可有效地确定一个点是在三角形内还是在边缘上

Question

如何有效地确定一个点是在三角形内部还是边缘上，如果可能的话，时间恒定。没有双精度

上下文：

平面是二维的
根据三个坐标对设置三角形Coord(int x, int y)
坐标范围是：[-2,000,000 , 2,000,000 ]
三角形坐标假定为有效的三角形网格
测试点也是整数

视觉示例： Image link

格式示例：

Triangle a(Coord(50000,50000),Coord(-4000,2000), Coord(300000,150000));

                               // Point  Result
a.test_point( 60000,  45000)   // G      true
a.test_point( 289500, 145500)  // F      true
a.test_point( 292000, 146000)  // E      false
a.test_point(-292000,-146000)  //-E      false
a.test_point( 260000, 134000)  // D      true

Answer 1

顶点为(x1, y1)、(x2, y2) 和(x3, y3) 的三角形内的任何点都可以表示为((αx1 + βx2 + γx3), (αy1 + βy2 + γy3))这样

α + β + γ = 1;

由于给定了点 (x, y)，因此您会得到另外两个方程式：

(αx1 + βx2 + γx3) = x

(αy1 + βy2 + γy3) = y

你要检查这样的(α, β, γ)是否存在。如果是，则该点位于三角形内部，否则位于外部。使用任何标准方法对此进行检查。

编辑：我假设在三角形内部你的意思也是在周边。如果你想让它完全在里面，那么用类似的想法来做线并检查它是否有解决方案。

Answer 2

首先请注意，您无法逃避以某种形式计算边的方程，这与经典的 "orientation test" (https://www.cs.cmu.edu/~quake/robust.html) 直接相关。

在您的情况下，64 位整数将避免溢出。而如果最大delta不超过46340，32位就够了。

如果 64 位算法本身不可用，我想你可以实现一个两阶段过程，在可能的情况下使用 32 位做出决定，并在不可避免时切换到 64 位仿真。

三方位测return同号时，一个点在三角形内部。当一个测试 returns 0 和另外两个内部条件时，它在轮廓上。两次测试时在一个顶点上 return 0.

您也可以考虑这个答案，但它必须适应整数运算，具有与上述相同的限制。

另请注意，如果要在三角形网格中定位很多点，答案将大不相同。

无需双精度即可有效地确定一个点是在三角形内还是在边缘上

Efficiently determining whether a point is inside a triangle or on the edge WITHOUT DOUBLE PRECISION

geometry

integer

point-in-polygon