点三角形说明

Question

我发现只有三角形"命中测试"的算法和实现,如下所示:http://www.emanueleferonato.com/2012/06/18/algorithm-to-determine-if-a-point-is-inside-a -triangle-with-mathematics-no-hit-test-involving /,这个: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中减去y1,从x3和x1减去多个k到减法结果？这个操作怎么办？什么是$ k*($ x3 - $ x1)？$ k是积分$ x1,$ y1和$ x2,$ y2之间的斜率,而不是$ x1,$ y1和$ x3,$ y3之间的斜率.

我对代数几何有一些了解.换句话说,如果主公式(直线方程)是y = kx + b,对于点(x1,我们有0 = y-y1 - (y2-y1)/(x2-x1)*(x-x1) y1)和(x2,y2),然后f(x3,y3)= y3-y1 - (y2-y1)/(x2-x1)*(x3-x1)？

我对吗？

Answer 1

该函数side回答问题"点x和x ₃位于由点x ₁和x ₂形成的线的同一侧".如果对于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);
}

是的,$k是从x ₁到x ₂的线的斜率; $s1并且$s2分别是该线上方的点x ₃和x的高度.

看看第二个条款:

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 ₃正下方(或上方)线上点的y坐标.所以$s1是高度X ₃上方(或下方),该点.