3

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

稀疏数据的空间查询

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

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

  • 除了数据的稀疏性；由于白色像素来自边缘，因此它们本质上是连接在一起的。但是，在与其他线路的交汇处，它们有两个以上的邻居。位于交界处的像素只能返回一次。

  • 数据必须实时处理，但没有 GPU 帮助。对于不同的三角形内容会有多次查询，每次查询后，可能会从数据结构中删除点。但是，在数据结构初始填充后，将不再插入新点。

  • 当光栅化边缘到达时，查询三角形是已知的。

  • 查询三角形比数据边多。

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

  • R-trees似乎是迄今为止我为这个问题找到的最好的数据结构，因为它们支持基于矩形的查询。我将检查查询三角形的 AABB 内的所有白色像素，然后检查每个返回的像素是否位于查询矩形内。

    但是，我不确定 R-tree 的表现如何，因为基于边缘的数据不容易分组为矩形，因为这些点在窄线上聚集在一起而不是导出。

    我也不确定使用有关查询三角形的信息预先构建 R-tree 的结构是否有意义，这些信息将在结构填充后立即生成（如前所述，查询三角形是已知的当数据到达时）。

  • 扭转问题似乎也是一个有效的解决方案，我使用二维间隔树为每个白色像素获取包含它的所有三角形的列表。然后，它可以存储在所有这些结果集中，并在查询到达时立即返回。但是，我不确定这是如何执行的，三角形的数量高于边缘的数量，但仍低于白色像素的数量（因为边缘主要分为 ~20-50 像素）。

  • 一种利用白色像素最常见的白色像素作为邻居的数据结构似乎是最有效的。但是，直到现在我还没有找到任何关于这种事情的信息。

4

2 回答 2

1

将查询三角形分解为 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;
}
于 2011-11-30T15:44:46.397 回答
0

我认为有几种计算几何算法会产生很好的结果。

  1. 计算包含所有三角形边的平面细分。（这比计算三角形边的所有交点要复杂一些。）对于每个面，列出包含该面的三角形。诚然，这是最坏情况的三次方，但只有当三角形重叠很多时（我不禁认为有一种方法可以将其压缩为二次方）。

  2. 定位细分中的每个像素（即，找出它属于哪个面）。每条边的第一个将花费 O(log n)，但如果您此后有局部性，则可能有一种方法可以将计算平均缩短到 O(1) 之类的值。（例如，如果您使用梯形方法并且如果您存储包含最后一个点的梯形列表，您可以向上遍历列表，直到找到包含当前点的梯形并返回。比较给 C++ 的提示STL 通过在插入点附近传递一个迭代器来设置插入。）

于 2011-11-30T23:56:28.193 回答