1

我只发现三角形中“命中测试”的算法和实现，如下所示：http ://www.emanueleferonato.com/2012/06/18/algorithm-to-determine-if-a-point-is-inside-a -triangle-with-mathematics-no-hit-test-involved/，这个： http: //www.blackpawn.com/texts/pointinpoly/default.html

但在我工作的项目中，我发现了这段代码：

public static function pointInTriangle($x, $y, $x1, $y1, $x2, $y2, $x3, $y3)
{   
    return self::side($x, $y, $x1, $y1, $x2, $y2, $x3, $y3) &&
           self::side($x, $y, $x1, $y1, $x3, $y3, $x2, $y2) &&
           self::side($x, $y, $x3, $y3, $x2, $y2, $x1, $y1);
}

private static function side($x, $y, $x1, $y1, $x2, $y2, $x3, $y3)
{
    if ($x1 - $x2 != 0) {
        $k    = ($y1 - $y2) / ($x1 - $x2);
        $s1   = $y3 - $y1 - $k * ($x3 - $x1);
        $s2   = $y - $y1 - $k * ($x - $x1);
    }
    else {
        $s1   = $x3 - $x1;
        $s2   = $x - $x1;
    }
    return ($s1 * $s2) >= 0;
}

你能向我解释一下这是如何工作的吗？为什么我们需要计算 $k（这是 x1, y1 和 x2, y2 点之间的斜率，不是吗？）？

我在理解第一个子句时遇到问题。为什么我们需要从 y3 和多个 k 中减去例如 y1 来得到 x3 和 x1 的减法结果？这个操作会做什么？$k * ($x3 - $x1) 是什么？$k 是点 $x1,$y1 和 $x2,$y2 之间的斜率，而不是 $x1,$y1 和 $x3,$y3 之间的斜率。

我有一些代数几何的知识。换句话说，如果主公式（直线方程）是 y = kx + b，对于点 (x1, y1) 和 (x2, y2)，然后 f(x3, y3) = y3 - y1 - (y2 - y1) / (x2 - x1) * (x3 - x1)？

我对吗？

4

1 回答 1

5

该函数side回答了“点x和x 3是否位于由点x 1和x 2形成的直线的同一侧”的问题。如果x 3的所有三个选项的答案都是“是” ，那么点x在三角形内。

的实现side有点笨拙。看第一条：

if ($x1 - $x2 != 0) {
    $k    = ($y1 - $y2) / ($x1 - $x2);
    $s1   = $y3 - $y1 - $k * ($x3 - $x1);
    $s2   = $y - $y1 - $k * ($x - $x1);
}

是的，是从x 1到x 2$k的线的斜率；和分别是这条线上方点x 3和x的高度。$s1$s2

看第二条：

else {
    $s1   = $x3 - $x1;
    $s2   = $x - $x1;
}

在这里，$s1又$s2有着不同的含义。它们是两点在垂直线右侧的距离。

无论哪种方式，这：

return ($s1 * $s2) >= 0;

给出正确答案。（如果你对矢量代数感到满意，你会遇到一条几乎垂直的线 - 有一种更清洁，更安全的方式）。

编辑：

让我们从第一个子句改写一行：

$s1 = $y3 - $y1 - $k * ($x3 - $x1);
$s1 = $y3 - $k * ($x3 - $x1) - $y1;
$s1 = $y3 - ($k * ($x3 - $x1) + $y1) ;

粗体部分是点x 3正下方（或上方）线上的点的 y 坐标。x 3在该点上方（或下方）$s1的高度也是如此。

于 2012-09-26T12:20:33.450 回答