1

次のように、三角形の「ヒット テスト」のアルゴリズムと実装のみを見つけました。 -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 から y1 を減算し、x3 と x1 の減算結果に倍数の k を減算する必要があるのはなぜですか? この操作は何をしますか？$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

この関数は、「点xとx 3は、点x1とx2によって形成される線の同じ側にありますsideか」という質問に答えます。x 3の3つの選択肢すべてに対して答えが「はい」の場合、点xは三角形の内側にあります。

の実装sideはちょっと不器用です。最初の節を見てください：

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

はい、x1からx2まで$kの線の傾きです。とは、それぞれこの線の上の点x3とxの高度です。$s1$s2

2番目の節を見てください。

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

ここで、$s1そして$s2別の意味を持っています。これらは、2つのポイントが垂直線の右側にどれだけ離れているかです。

いずれにせよ、これ：

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

正解です。（ほぼ垂直な線で問題が発生します。ベクトル代数に慣れている場合は、よりクリーンで安全な方法があります）。

編集：

最初の句から1行を書き直してみましょう。

$ s1 = $ y3-$ y1-$ k *（$ x3-$ x1）;
$ s1 = $ y3-$ k *（$ x3-$ x1）-$ y1;
$ s1 = $ y3- （$ k *（$ x3-$ x1）+ $ y1） ;

太字の部分は、点x 3の真下（または上）の線上の点のy座標です。その点の上の（または下の）x3$s1の高さも同様です。

于 2012-09-26T12:20:33.450 に答える