查询三角形内部的点的数据结构

Question

查询三角形内部的点的数据结构

algorithmoptimizationgraphicsdata-structuresspatial-query

3

我有一些包含被光栅化成像素的边缘的2D数据。我想实现一个高效的数据结构，以返回所有位于非轴对齐2D三角形中的边缘像素。

Spatial query for sparse data

图像显示了一个问题的可视化，其中白色表示光栅化边缘，红色可视化查询三角形。结果将是所有位于红色三角形边界或内部的白色像素。

当进一步查看图像时，人们会注意到我们有稀疏的布尔数据，这意味着如果我们用0表示黑色像素，用1表示白色像素，则数据中1的数量远低于0的数量。因此，对红色三角形进行光栅化，并检查其内部每个点是白色还是黑色并不是最有效的方法。

除了数据的稀疏性之外；由于白色像素源自边缘，它们天生就是相互连接在一起的。然而，在与其他线条的交点处，它们有多于两个邻居。在交汇处的像素应该只返回一次。

数据必须实时处理，但没有GPU的帮助。将为不同的三角形内容提出多个查询，并在每个查询后从数据结构中删除点。然而，在填充数据结构后，不会再插入新点。

当栅格化边缘到达时，已知查询三角形。

查询三角形比数据边缘更多。

现在有很多空间数据结构可供选择。然而，我想知道，哪一个是最适合我的问题的。我愿意实现一个高度优化的数据结构来解决这个问题，因为它将成为项目的核心要素。因此，也欢迎使用混合或缩写的数据结构！

R-trees 看起来是我目前为止找到的最适合这个问题的数据结构，因为它们提供了基于矩形的查询支持。我将检查查询三角形 AABB 中的所有白色像素，然后将检查每个返回的像素是否位于查询矩形内。

然而，我不确定 R 树的表现会如何，因为基于边缘的数据不容易分组成矩形，因为点在狭窄的线上聚集在一起而不是散布开来。

我也不确定是否有意义使用关于查询三角形的信息预先构建 R 树的结构，这些信息将在填充结构时立即生成（如前所述，当数据到达时已经知道查询三角形）。
反向解决问题似乎也是一个有效的解决方案，其中我使用二维区间树为每个白色像素获取包含它的所有三角形的列表。然后，它可以已经存储在所有这些结果集中，并在查询到达时立即返回。但是，我不确定当三角形数量高于边数但仍低于白色像素数量时，它的性能如何（因为一个边通常会分成约20-50个像素）。
利用白色像素通常有白色像素作为邻居的数据结构似乎最有效。但是，到目前为止我还没有找到任何关于这样的东西的信息。

- Etan

2个回答

0

有几个计算几何算法，我认为一起使用会得到很好的结果。

计算包含所有三角形边缘的平面细分。（这比计算所有三角形边缘的交点要复杂一些。）对于每个面，列出包含该面的三角形列表。这显然是最坏情况下的立方级别，但只有当三角形重叠很多时才会出现（我不禁想到有一种方法可以将其压缩到二次方程度）。
定位细分中的每个像素（即找出它属于哪个面）。每条边上的第一个像素成本为O(log n)，但如果之后有局部性，可能有一种方法可以将计算捷径到平均为O(1)。（例如，如果您使用梯形法，并且如果您存储了包含上一个点的梯形列表，则可以沿着列表向上遍历，直到找到包含当前点的梯形并向下工作。与通过传递插入点附近的迭代器来给出C++ STL set插入提示进行比较。）

- Per

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wildplasser · Accepted Answer

将查询三角形分解为n * 3条线。对于每个测试点，您可以估计它在每条线的哪一侧。其余部分是布尔逻辑。

编辑：由于您的点是光栅化的，因此您可以预先计算扫描线上的点，其中扫描线进入或离开特定查询三角形（=穿过上述3n条线之一&&位于参与该特定三角形的另外两条线的“内部”）

更新：受到另一个主题的触发（如何确定点是否在3D三角形内？），我将添加代码以证明非凸情况可以用“点在每条线的哪一侧”来表示。由于我很懒，所以我会使用L形状。我认为其他非凸形状可以类似地处理。这些线是平行于X和Y轴的，但这又是懒惰。

/*

Y
| +-+
| | |
| | +-+
| |   |
| +---+
|
0------ X
the line pieces:
Horizontal:
(x0,y0) - (x2,y0)
(x1,y1) - (x2,y1)
(x0,y2) - (x1,y2)
Vertical:
(x0,y0) - (x0,y2)
(x1,y1) - (x1,y2)
(x2,y0) - (x2,y1)

The lines:
(x==x0)
(x==x1)
(x==x2)
(y==y0)
(y==y1)
(x==y2)

Combine them:
**/

#define x0 2
#define x1 4
#define x2 6

#define y0 2
#define y1 4
#define y2 6

#include <stdio.h>

int inside(int x, int y)
{   

switch(  (x<x0 ?0:1)
    +(x<x1 ?0:2)
    +(x<x2 ?0:4)
    +(y<y0 ?0:8)
    +(y<y1 ?0:16)
    +(y<y2 ?0:32) ) {

case 1+8:
case 1+2+8:
case 1+8+16:
    return 1;
default: return 0;
    }
}

int main(void)
{
int xx,yy,res;
while (1) {
     res = scanf("%d %d", &xx, &yy);
     if (res < 2) continue;
     res = inside(xx, yy);
     printf("(%d,%d) := %d\n", xx, yy,res);
    }
return 0;
}