三角内のカウントポイントが速く

Question

三角形の中にあるリスト内のポイントの数を見つける必要があります。ここで問題となるのは、最大で100万ポイントある可能性があるということです。

私は簡単なアプローチを試しました：三角形の面積が、一度に三角形の点の2つをチェックして形成された三角形の面積の合計と等しい場合、その内部。これは、2つに分割して領域を見つけることはないので、精度誤差はありません。

しかし、私はより速いものが必要です。目標はスピードです。何らかの基準やそれに類するものに基づいていくつかの点を無視して、何らかの前処理によってより速く作ることができますか？

編集： 重要な詳細を追加するのを忘れました。与えられたポイントは固定されています。ポイントは静止しており、最大百万の三角形をチェックする必要があります。

EDIT 2：良い（多分最適すぎる）方法は、ラインスイープを使用していたことが分かります。それでも、あなたの答えをありがとう！

Answer 1

計算幾何学によれば、これを行うための最速の方法は、重心座標変換によるものです。固定された三角形と多くのテストポイントがある場合、このアプローチは、あなたが大部分の作業を行った三角形の3つの点の重心座標を計算すると、特に高速になります。ここでABCは三角形であり、完全なアルゴリズムであり、Pは、試験下の点である：重心座標がAに対して計算され、ここで

// Compute vectors   
v0 = C - A 
v1 = B - A 
v2 = P - A 

// Compute dot products 
dot00 = dot(v0, v0) 
dot01 = dot(v0, v1) 
dot02 = dot(v0, v2) 
dot11 = dot(v1, v1) 
dot12 = dot(v1, v2) 

// Compute barycentric coordinates 
invDenom = 1/(dot00 * dot11 - dot01 * dot01) 
u = (dot11 * dot02 - dot01 * dot12) * invDenom 
v = (dot00 * dot12 - dot01 * dot02) * invDenom 

// Check if point is in triangle 
return (u >= 0) && (v >= 0) && (u + v < 1) 

が、BまたはCは、同様に働いていることになります。

追加ポイントをテストするには、v2、dot02、dot12、u、およびvを再計算するだけです。invDenomなどの数量は同じままです。

Answer 2

シンプルなプレフィルタは、座標が明らかに三角形の角の境界の外側にある点を削除することです。例えば

a 
+ 
|\ 
| \ b 
|c \ 
+---+ d 

AおよびDは明らかに外にある。 AのY座標は三角形の最大Yをはるかに超えており、Dは明らかに三角形の最大Xを超えています。

これはテストのためにBとCを残します。

Answer 3

各辺の左（右）にある点は三角形の内側にあります。テスト対象の点と三角形の頂点の1つと三角形の辺にある3つのベクトルのいずれかのクロスベクトル積（実際にはその1つの要素）を計算することができます（すべてクロック単位またはすべて反時計方向に）。すべての3の計算されたコンポーネントが同じ符号を持つかどうかを確認します（3つすべて負または3つすべて正）。これは、ポイントが入っていることを教えてくれるでしょう。速く、精度を問題なく、少なくとも、整数をタスクに使用する場合は問題ありません。

三角形のいずれかの辺が間違っていることがわかると、すべての点の計算を停止することがあります。 Cで

サンプルコード：

#include <stdio.h> 

#define SCREEN_HEIGHT 22 
#define SCREEN_WIDTH 78 

// Simulated frame buffer 
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH]; 

void SetPixel(int x, int y, char color) 
{ 
    if ((x < 0) || (x >= SCREEN_WIDTH) || 
     (y < 0) || (y >= SCREEN_HEIGHT)) 
    return; 

    Screen[y][x] = color; 
} 

void Visualize(void) 
{ 
    int x, y; 

    for (y = 0; y < SCREEN_HEIGHT; y++) 
    { 
    for (x = 0; x < SCREEN_WIDTH; x++) 
     printf("%c", Screen[y][x]); 

    printf("\n"); 
    } 
} 

typedef struct 
{ 
    int x, y; 
} Point2D; 

int main(void) 
{ 
    // triangle vertices 
    Point2D vx0 = { SCREEN_WIDTH/2, SCREEN_HEIGHT/7 }; 
    Point2D vx1 = { SCREEN_WIDTH * 6/7, SCREEN_HEIGHT * 2/3 }; 
    Point2D vx2 = { SCREEN_WIDTH/7, SCREEN_HEIGHT * 6/7 }; 
    // vectors lying on triangle sides 
    Point2D v0, v1, v2; 
    // current point coordinates 
    int x, y; 

    // calculate side vectors 

    v0.x = vx1.x - vx0.x; 
    v0.y = vx1.y - vx0.y; 

    v1.x = vx2.x - vx1.x; 
    v1.y = vx2.y - vx1.y; 

    v2.x = vx0.x - vx2.x; 
    v2.y = vx0.y - vx2.y; 

    // process all points 

    for (y = 0; y < SCREEN_HEIGHT; y++) 
    for (x = 0; x < SCREEN_WIDTH; x++) 
    { 
     int z1 = (x - vx0.x) * v0.y - (y - vx0.y) * v0.x; 
     int z2 = (x - vx1.x) * v1.y - (y - vx1.y) * v1.x; 
     int z3 = (x - vx2.x) * v2.y - (y - vx2.y) * v2.x; 

     if ((z1 * z2 > 0) && (z1 * z3 > 0)) 
     SetPixel(x, y, '+'); // point is to the right (left) of all vectors 
     else 
     SetPixel(x, y, '-'); 
    } 

    // draw triangle vertices 

    SetPixel(vx0.x, vx0.y, '0'); 
    SetPixel(vx1.x, vx1.y, '1'); 
    SetPixel(vx2.x, vx2.y, '2'); 

    // visualize the result 

    Visualize(); 

    return 0; 
} 

出力（ideone）：

------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
---------------------------------------0-------------------------------------- 
--------------------------------------++++------------------------------------ 
------------------------------------++++++++---------------------------------- 
----------------------------------+++++++++++++------------------------------- 
--------------------------------+++++++++++++++++----------------------------- 
------------------------------++++++++++++++++++++++-------------------------- 
----------------------------++++++++++++++++++++++++++------------------------ 
--------------------------+++++++++++++++++++++++++++++++--------------------- 
-------------------------++++++++++++++++++++++++++++++++++------------------- 
-----------------------+++++++++++++++++++++++++++++++++++++++---------------- 
---------------------+++++++++++++++++++++++++++++++++++++++++++-------------- 
-------------------+++++++++++++++++++++++++++++++++++++++++++++++1----------- 
-----------------++++++++++++++++++++++++++++++++++++------------------------- 
---------------++++++++++++++++++++++++--------------------------------------- 
-------------++++++++++++----------------------------------------------------- 
-----------2------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 
------------------------------------------------------------------------------ 

Answer 4

あなたはまた、計算を加速するquadtreeを使用することができます。

任意の解像度で停止し、任意の解像度で停止するクォードツリーを計算し、各ノード（四角形）に対して、ノードが完全に内側にあるか、完全に外側にあるか、または部分的に内側にあるかを示すフラグを格納します。部分的に三角形の内側にあるノードは潜在的に子供を持つことができます（深さに依存します）

各点について、四分木を走査します。三角形の外側または内側にあるノードにアクセスすると、すべてが設定されます。三角形内にあるかどうか（ノードが部分的に三角形の内側にあるかどうか）、現在のノードに子があるかどうかがわからない場合は、その子に対して再帰的にテストします。部分的に三角形の内側にあるリーフノードにヒットしたら、解析的な三角形の包含チェックを行います。

Answer 5

まず、y座標とy座標x座標のリストで与えられた点を並べ替えます。今度はあなたの下からy座標（平行線をx軸と考える）から始まり、1単位上に移動すると、三角形の端点によって形成される線分の等式も得られます。 Marc Bの示唆しているようないくつかの明白な点を取り除いてください。残りの点については、x軸への仮想平行線と同じy座標を持ち、単位ステップごとに上方向に移動し、三角形の内側か外側かをチェックします三角形の端点を結ぶ線の方程式に含まれる。以前のy座標に基づいてソートした座標リストをバイナリ検索することで、同じy座標を持つポイントを簡単に作成できます。このようにして、あなたのalgoは各クエリに対してO（Yrangeoftriangle * nlogn）をとります。また、長い間codechefについてよく質問されています。