10

我需要找到给定列表中三角形内的点数。这里的问题是，最多可以有一百万个点。

我尝试了一个简单的方法：如果三角形的面积等于一次取 2 个三角形点和要检查的点形成的 3 个三角形的面积之和，则它的内部。这没有任何精度误差，因为我没有除以二来找到该区域。

但我需要更快的东西。目标是速度。是否可以通过某种预处理使其更快，忽略基于某些标准或类似的某些点？

编辑：忘记添加关键细节。一旦给出的分数是固定的。然后这些点是静态的，需要检查多达一百万个三角形......

编辑2：事实证明，一个好的（也许也是最佳的）方法是使用线扫描。不过，感谢您的回答！

4

5 回答 5

8

如果一个点在每条边的左侧（右侧），则该点位于三角形内部。您可以计算由要测试的点和三角形顶点之一以及位于三角形两侧的 3 个矢量构成的矢量的叉积（实际上只是其中的一个分量）（全部按顺时针方向或全部逆时针方向）。查看所有 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------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
于 2013-02-07T18:12:00.753 回答
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 回答
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 坐标的其余点，每次向上移动一个单位步长，检查它们是在三角形内部还是外部，通过 put在连接三角形端点的线方程中。您可以通过在您之前根据 y 坐标排序的坐标列表上进行二进制搜索来轻松地使这些点具有相同的 y 坐标。这样，您的算法对每个查询都采用 O(Yrangeoftriangle*nlogn) 。ALSO 这个问题在 codechef long 上问得很好。

于 2013-02-07T20:47:37.127 回答