三角形内の任意の点を見つける最速の方法2D

2Dの三角形（辺ではない）内の任意の点を見つけるための最も速い方法が必要です。どんな助け？三角形内の任意の点を見つける最速の方法2D

2012-04-03 EOG

あなたは：点A、B、Cと点Dを持つ三角形を与えますか？点Dは三角形A、B、Cの中にありますか？他のすべては簡単です。 – knivil

三角形はどのように表現されていますか？平面上の点、ベクトルのペアなどとして？ – Kaganar

Nitpickingですが、*最も速い*方法はおそらくポイントを事前計算し、それを計算する必要はありません。 – Flexo

あなたの三角形をポイントで表現すると、 Steve Jessopの答えはほぼ最適です。

実際に行う必要があるのは、ある時点から開始し、限られた量の他の2つの方向に向かって起動することだけです。それが平均化が達成するものですが、非常に特殊な方法です。

追加が高速です。プラットフォームとコンパイラによっては、分割が遅くなることがあります。例えば、最近のARMコア上で、私は平均の上に任意の日、このバージョンを選択したい

：

xm = (x0 + (x1 + x2)/2)/2 
ym = (y0 + (y1 + y2)/2)/2

を変数は、コンパイラが整数している場合は、正しくスケジュールた場合、ビットシフトに部門を最適化する必要があり、ありますARMではほとんど無料です。変数が浮動小数点または倍精度の場合、コンパイラは単純な指数のデクリメントに最適化する必要があります。浮動小数点の除算は比較的遅いことが知られています。

最終的に、テストして参照してください。比較的低レベルのコード最適化を行っていない限り、違いは見られません。一方、これを内側のループで使用している場合は、可能性があります。

これがなぜ機能するのかについての直感を提供する：最初に、(x1, y1)と(x2, y2)によって形成される線分の中点を見つける。次に、によって形成される線分と点と(x0, y0)との間の中点を見つける。三角形の図を描いてこれを行うと、すぐにこれが機能することが明らかになります。

2012-04-03 16:06:39 Kaganar

3つの頂点（重心）の「平均」は、三角形の内側の点であり、おそらく他のどの頂点よりも速く計算されます。

頂点が同一直線上にある縮退したケースの端にしかありません。その場合、三角形内のすべての点が辺にあるので、解決策はありません。

2012-04-03 15:57:25

+1。一般に、v1、v2およびv3が頂点である場合、w1 + w2 + w3 = 1,0 ElKamina

または：まず、三角形のサーフェスを計算することができます。次に、三角形を他の3つの三角形に分ける第2の計算を行います。これら3つのサブ三角形のサーフェスが大きければ、あなたのポイントは三角形の領域外です。私の言いたいことを見て？

2012-04-03 16:00:08 Rps

頂点A、B、C

ベクトル

AB = BA

AC = CA

P = A + T * AB + U * AC

t、u - 範囲[0..1]の任意の数字（ランダム？）、t + u < = 1

2012-04-03 16:01:39 MBo

答えて