ヒットテストで使用するための、高速な2D ポイント内部ポリゴン アルゴリズムを作成しようとしています(例Polygon.contains(p:Point)
)。効果的なテクニックの提案をいただければ幸いです。
ベストアンサー1
グラフィックスに関しては、整数は好まないと思います。多くのシステムでは UI の描画に整数を使用します (ピクセルは結局 int です) が、たとえば macOS ではすべてに float を使用します。macOS はポイントのみを認識し、ポイントは 1 ピクセルに変換できますが、モニターの解像度によっては別のものに変換される可能性があります。Retina スクリーンでは、ポイントの半分 (0.5/0.5) がピクセルです。それでも、macOS UI が他の UI よりも大幅に遅いことに気付いたことはありません。結局のところ、3D API (OpenGL または Direct3D) も float で動作し、最新のグラフィックス ライブラリは GPU アクセラレーションを利用することがよくあります。
速度が主な関心事だとおっしゃったので、速度を追求しましょう。高度なアルゴリズムを実行する前に、まず簡単なテストを行ってください。ポリゴンの周囲に軸に沿った境界ボックスを作成します。これは非常に簡単で高速であり、すでに多くの計算を節約できます。これはどのように機能するのでしょうか? ポリゴンのすべてのポイントを反復処理し、X と Y の最小値と最大値を見つけます。
たとえば、点 があるとします(9/1), (4/3), (2/7), (8/2), (3/6)
。これは、Xmin が 2、Xmax が 9、Ymin が 1、Ymax が 7 であることを意味します。2 つの辺 (2/1) と (9/7) を持つ長方形の外側の点は、多角形内には存在できません。
// p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
// Definitely not within the polygon!
}
これは、任意のポイントに対して実行される最初のテストです。ご覧のとおり、このテストは超高速ですが、非常に粗いものです。境界矩形内のポイントを処理するには、より高度なアルゴリズムが必要です。これを計算する方法はいくつかあります。どの方法が機能するかは、ポリゴンに穴があるか、常にソリッドであるかによっても異なります。ソリッドの例を以下に示します (1 つは凸型、もう 1 つは凹型)。
穴の開いたものがこちらです:
緑色の方は真ん中に穴が開いています!
最も簡単で、上記の 3 つのケースすべてに対応でき、しかもかなり高速なアルゴリズムは、レイ キャスティングと呼ばれます。このアルゴリズムの考え方は非常に単純です。ポリゴンの外側の任意の場所からポイントまで仮想光線を描き、その光線がポリゴンの辺に当たる頻度を数えます。当たる回数が偶数の場合はポリゴンの外側、奇数の場合は内側です。
ワインディング数アルゴリズムは代替案になります。これは、ポイントがポリゴン ラインに非常に近い場合に精度が高くなりますが、速度も大幅に遅くなります。レイ キャスティングは、浮動小数点の精度の制限と丸めの問題により、ポイントがポリゴンの辺に近すぎる場合に失敗する可能性がありますが、実際にはほとんど問題にはなりません。ポイントが辺に非常に近い場合、そのポイントがすでにポリゴンの内側にあるか外側にあるかを視覚的に認識できないことがよくあります。
上記の境界ボックスはまだ残っていますね。覚えていますか? 境界ボックスの外側の点を選択し、それをレイの開始点として使用します。たとえば、点は(Xmin - e/p.y)
確実にポリゴンの外側にあります。
しかし、 とは何でしょうかe
? そうですね、e
(実際にはイプシロン) は境界ボックスにいくらかのパディングを与えます。 前に述べたように、ポリゴンの線に近すぎるとレイ トレーシングは失敗します。 境界ボックスがポリゴンと等しくなる可能性があるので (ポリゴンが軸に沿った長方形の場合、境界ボックスはポリゴン自体と等しくなります!)、これを安全に行うにはいくらかのパディングが必要です。それだけです。 はどのくらいの大きさを選択すればよいでしょうかe
? 大きすぎてはいけません。 描画に使用する座標系のスケールによって異なります。 ピクセル ステップ幅が 1.0 の場合は、1.0 を選択します (0.1 でも機能します)。
開始座標と終了座標を持つ光線が得られたので、問題は「ポリゴン内の点」から「光線がポリゴンの辺と交差する頻度」に移ります。したがって、以前のようにポリゴンの点だけで作業することはできず、実際の辺が必要になります。辺は常に 2 つの点によって定義されます。
side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:
光線をすべての面に対してテストする必要があります。光線をベクトル、すべての面をベクトルとみなします。光線は各面に 1 回だけ当たるか、まったく当たらないかのどちらかです。同じ面に 2 回当たることはできません。2D 空間の 2 本の線は、平行でない限り、常に 1 回だけ交差します。平行の場合は、交差することはありません。ただし、ベクトルの長さには制限があるため、2 つのベクトルは平行ではなく、短すぎて互いに出会うことがないため、交差しない可能性があります。
// Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
// Test if current side intersects with ray.
// If yes, intersections++;
}
if ((intersections & 1) == 1) {
// Inside of polygon
} else {
// Outside of polygon
}
ここまでは順調ですが、2 つのベクトルが交差するかどうかをどのようにテストするのでしょうか? 次は、目的の C コード (テストされていません) です。
#define NO 0
#define YES 1
#define COLLINEAR 2
int areIntersecting(
float v1x1, float v1y1, float v1x2, float v1y2,
float v2x1, float v2y1, float v2x2, float v2y2
) {
float d1, d2;
float a1, a2, b1, b2, c1, c2;
// Convert vector 1 to a line (line 1) of infinite length.
// We want the line in linear equation standard form: A*x + B*y + C = 0
// See: http://en.wikipedia.org/wiki/Linear_equation
a1 = v1y2 - v1y1;
b1 = v1x1 - v1x2;
c1 = (v1x2 * v1y1) - (v1x1 * v1y2);
// Every point (x,y), that solves the equation above, is on the line,
// every point that does not solve it, is not. The equation will have a
// positive result if it is on one side of the line and a negative one
// if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
// 2 into the equation above.
d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
d2 = (a1 * v2x2) + (b1 * v2y2) + c1;
// If d1 and d2 both have the same sign, they are both on the same side
// of our line 1 and in that case no intersection is possible. Careful,
// 0 is a special case, that's why we don't test ">=" and "<=",
// but "<" and ">".
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// The fact that vector 2 intersected the infinite line 1 above doesn't
// mean it also intersects the vector 1. Vector 1 is only a subset of that
// infinite line 1, so it may have intersected that line before the vector
// started or after it ended. To know for sure, we have to repeat the
// the same test the other way round. We start by calculating the
// infinite line 2 in linear equation standard form.
a2 = v2y2 - v2y1;
b2 = v2x1 - v2x2;
c2 = (v2x2 * v2y1) - (v2x1 * v2y2);
// Calculate d1 and d2 again, this time using points of vector 1.
d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
d2 = (a2 * v1x2) + (b2 * v1y2) + c2;
// Again, if both have the same sign (and neither one is 0),
// no intersection is possible.
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// If we get here, only two possibilities are left. Either the two
// vectors intersect in exactly one point or they are collinear, which
// means they intersect in any number of points from zero to infinite.
if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;
// If they are not collinear, they must intersect in exactly one point.
return YES;
}
入力値は、ベクトル 1 (および) とベクトル 2 (および) の2 つの端点です。したがって、2 つのベクトル、4 つの点、8 つの座標があります。およびは明確です。交差を増やしますが、何もしません。v1x1/v1y1
v1x2/v1y2
v2x1/v2y1
v2x2/v2y2
YES
NO
YES
NO
COLLINEAR はどうでしょうか? これは、両方のベクトルが同じ無限の直線上にあることを意味します。位置と長さに応じて、まったく交差しないか、無限の数の点で交差します。このケースをどのように処理するかは完全にはわかりませんが、どちらにしても交差としてカウントしません。まあ、このケースは実際には浮動小数点の丸め誤差のため、どちらにして== 0.0f
もまれです。より良いコードでは、 をテストするのではなく、 のようなものをテストします< epsilon
。ここで、イプシロンはかなり小さな数です。
より多くのポイントをテストする必要がある場合、ポリゴンの辺の線形方程式の標準形式をメモリに保存して、毎回再計算しなくても済むようにすることで、全体の処理速度を確かに少し上げることができます。これにより、ポリゴンの辺ごとに 3 つの浮動小数点値をメモリに保存する代わりに、テストごとに 2 回の浮動小数点乗算と 3 回の浮動小数点減算を節約できます。これは、メモリと計算時間の典型的なトレードオフです。
最後になりましたが、3D ハードウェアを使用してこの問題を解決できる場合は、興味深い代替手段があります。GPU にすべての作業を任せましょう。画面外のペイント サーフェスを作成します。それを完全に黒色で塗りつぶします。次に、OpenGL または Direct3D でポリゴン (ポイントがポリゴンのいずれかにあるかどうかをテストしたいだけで、どのポリゴンかは気にしない場合は、すべてのポリゴン) をペイントし、ポリゴンを別の色 (たとえば白) で塗りつぶします。ポイントがポリゴン内にあるかどうかを確認するには、描画サーフェスからそのポイントの色を取得します。これは、O(1) のメモリ フェッチで済みます。
もちろん、この方法は描画面が巨大である必要がない場合にのみ使用できます。描画面が GPU メモリに収まらない場合、この方法は CPU で実行するよりも遅くなります。描画面が巨大になる必要があり、GPU が最新のシェーダーをサポートしている場合は、上記のレイ キャスティングを GPU シェーダーとして実装することで GPU を使用できます。これは絶対に可能です。テストするポリゴンやポイントの数が多い場合は、この方法が効果的です。一部の GPU では、64 ~ 256 ポイントを並行してテストできます。ただし、CPU から GPU へのデータ転送とその逆の転送は常にコストがかかることに注意してください。そのため、ポイントまたはポリゴンのいずれかが動的で頻繁に変更される、いくつかのポイントをいくつかの単純なポリゴンに対してテストするだけでは、GPU アプローチが効果的になることはほとんどありません。