10

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

私は簡単なアプローチを試みました。三角形の面積が、一度に三角形の2つの点とチェックする点をとって形成された3つの三角形の面積の合計に等しい場合、その内側です。面積を求めるために 2 で除算しないため、これには精度エラーはありません。

しかし、もっと速いものが必要です。目標はスピードです。何らかの基準などに基づいていくつかのポイントを無視して、ある種の前処理によって高速化できますか?

編集：重要な詳細を追加するのを忘れました。一度付与されたポイントは固定されます。次に、ポイントは静的であり、最大 100 万個の三角形をチェックする必要があります...

EDIT 2：それを行うための良い（おそらく最適な）方法は、ラインスイープを使用していたことがわかりました。それでも、あなたの答えをありがとう！

4

5 に答える 5

8

計算幾何学の弱点によると、これを行う最も速い方法は、重心座標変換によるものです。固定三角形と多くのテスト ポイントがある場合、三角形の 3 点の重心座標を計算すると、ほとんどの作業が完了しているため、このアプローチは特に高速です。ABC が三角形で、P がテスト対象の点である完全なアルゴリズムを次に示します。

// 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)

ここでは、重心座標は A に対して計算されますが、B または C も同様に機能します。

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

于 2013-02-07T18:56:04.860 に答える
8

すべての辺の左 (右) にある場合、点は三角形の内側にあります。テストするポイントと、三角形の頂点の 1 つ、および三角形の辺にある 3 つのベクトル (すべて時計回りまたはすべて反時計回り）。3 つすべての計算されたコンポーネントが同じ符号 (3 つすべて負または 3 つすべて正) を持っているかどうかを確認します。それはポイントが入っていることを示しています。タスクに整数を使用する場合、少なくとも精度に問題はありません。

三角形の辺の 1 つの間違った側にあることがわかったら、すべての点のそれ以上の計算を停止できます。

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------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
于 2013-02-07T18:12:00.753 に答える
4

単純なプレフィルターは、座標が明らかに三角形の角の境界の外側にあるポイントを排除することです。例えば

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

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

これで、B と C はテスト用に残ります。

于 2013-02-07T18:10:49.220 に答える
3

四分木を使用して計算を高速化することもできます。

三角形 (任意の解像度で停止) の四分木を計算し、ノード (正方形) ごとに、ノードが完全に三角形の内側にあるか、完全に外側にあるか、部分的に内側にあるかを示すフラグを格納します。部分的に三角形の内側にあるノードは、子を持つ可能性があります (深さによって異なります)。

ポイントごとに、四分木をトラバースします。三角形の完全に外側または内側にあるノードにアクセスすると、準備完了です。三角形の中にいるかどうか (ノードが部分的に三角形の内側にある) が不明で、現在のノードに子がある場合は、その子に対して再帰的にテストします。部分的に三角形の内側にあるリーフ ノードにヒットした場合は、分析ポイント - 三角形の包含チェックを行います。

于 2013-02-07T18:31:46.950 に答える
1

まず、リストにあるポイントをy座標で並べ替え、y座標x座標で並べ替えます。次に、最も低いy座標（x軸に平行な線を考えてください）の下から開始し、それを1単位上に移動すると、三角形の端点によって形成される線分の方程式も得られます。ここで、Marc Bによって提案されたように、いくつかの明らかな点を削除します。そして、x軸への想像上の平行線と同じy座標を持つ残りの点については、置くたびに単位ステップずつ上に移動します。三角形の端点を結ぶ線の方程式で。以前にy座標に従ってソートした座標のリストで二分探索を行うことにより、同じy座標を持つそのような点を簡単に見つけることができます。このようにして、アルゴリズムはクエリごとにO（Yrangeoftriangle * nlogn）を取ります。また、この質問はcodecheflongでかなりよく聞かれます。

于 2013-02-07T20:47:37.127 に答える