查询位于三角形内的点的数据结构 [英] Data structure to query points which lie inside a triangle
问题描述
图像显示了问题在于白色表示光栅化边缘，红色可视化查询三角形。结果将是位于边界上或红色三角形内的所有白色像素。
-
进一步查看图像时，我们注意到我们有稀疏布尔值数据，这意味着如果我们用0表示黑色像素，将1表示为白色像素，那么数据中的1个数字远低于0。因此，光栅化红色三角形并检查其内部的每个点是否是白色或黑色不是最有效的方法。
-
除了稀疏数据;由于白色像素源于边缘，它们本质上是连接在一起。然而，在与其他线路的交汇处，他们有两个以上的邻居。位于交界处的像素只能返回一次。
-
数据必须以实时处理，但不支持GPU协助。对于不同的三角形内容，将会有多个查询，并且在每个查询之后，可以从数据结构中删除点。但是，在初始填写数据结构之后，新点不会被插入。
-
查询三角形已知
-
比数据边缘有多个查询三角形。
有很多空间数据结构可用。不过我想知道，哪一个是我问题最好的一个。我愿意实施高度优化的数据结构来解决这个问题，因为它将是项目的核心要素。因此，也欢迎数据结构的混合或缩写。
-
R-tree 似乎是迄今为止发现的最好的数据结构，因为它们为矩形查询提供了支持。我将检查查询三角形的AABB中的所有白色像素，然后检查每个返回的像素是否位于查询矩形内。
但是，我是不知道R-tree会如何表现，因为基于边缘的数据将不容易被分组成矩形，因为这些点在狭窄的线上聚集在一起，而不是pread out。
我不知道如果使用关于查询三角形的信息来预先构建R树的结构是有意义的，一旦结构被填充就会产生（如前所述，查询三角形已经是当数据到达时已知）。
-
逆转问题似乎也是一个有效的解决方案，我使用 2维间隔树，为每个白色像素获取包含它的所有三角形列表。然后，它可以存储在所有这些结果集中，并在查询到达时立即返回。但是，我不知道这是如何执行三角形的数量高于边缘数量，但仍然低于白色像素的数量（因为边缘大部分分为〜20-50像素）。 p>
-
将利用白色像素大多数白色像素作为邻居的数据结构似乎是最有效的。但是，到现在为止，我找不到任何关于这样的事情。
将查询三角形分解为n * 3行。对于每一个测试点，您都可以估计每一行的哪一边。其余的是布尔逻辑。
编辑：由于您的点被光栅化，您可以预先计算扫描线进入或留下特定查询三角形的扫描线上的点（= cross上述3n行中的一个位于参与该特定三角形的其他两行的内部中）
更新：由另一个主题（ 如何查明是否为在三角形？）我将添加代码来证明非凸起情况可以表达为每一行的哪一边的位置的术语。既然我很懒，我会用L形的形式。可以类似地处理其他非凸形状。线条与X轴和Y轴平行，但这又是懒惰。
/ *
Y
| + - +
| | |
| | + - +
| | |
| + --- +
|
0 ------ X
线条：
水平：
（x0，y0） - （x2，y0）
（x1，y1） - （x2，y1）
（x0，y2） - （x1，y2）
垂直：
（x0，y0） - （x0，y2）
） - （x1，y2）
（x2，y0） - （x2，y1）
行：
（x == x0）
（x = = x1）
（x == x2）
（y == y0）
（y == y1）
（x == y2）
组合它们：
** /
#define x0 2
#define x1 4
#define x2 6
#define y0 2
#define y1 4
#define y2 6
#include< stdio.h>
int（int x，int y）
{
开关（（x
+（x
+（y< y1？0：16）
+（y
案例1 + 8：
案例1 + 2 + 8：
案例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\\\
，xx，yy，res）;
}
return 0;
}
I have some 2D data which contains edges which were rasterized into pixels. I want to implement an efficient data structure which returns all edge pixels which lie in a non-axis-aligned 2D triangle.
The image shows a visualization of the problem where white denotes the rasterized edges, and red visualizes the query triangle. The result would be all white pixels which lie on the boundary or inside the red triangle.
When further looking at the image, one notices that we have sparse boolean data, meaning that if we denote black pixels with a 0 and white pixels with a 1, that the number of 1s in the data is much lower than the number of 0s. Therefore, rasterizing the red triangle and checking for each point on it's inside whether it is white or black is not the most efficient approach.
Besides the sparseness of the data; since the white pixels origin from edges, it is in their nature to be connected together. However, at junctions with other lines, they have more than two neighbors. Pixels which are at a junction should only be returned once.
The data must be processed in realtime, but with no GPU assistance. There will be multiple queries for different triangle contents, and after each one, points may be removed from the data structure. However, new points won't be inserted anymore after the initial filling of the data structure.
The query triangles are already known when the rasterized edges arrive.
There are more query triangles than data edges.
There are many spatial data structures available. However I'm wondering, which one is the best one for my problem. I'm willing to implement a highly optimized data structure to solve this problem, as it will be a core element of the project. Therefore, also mixes or abbreviations of data structures are welcome!
R-trees seem to be the best data structure which I found for this problem until now as they provide support for rectangle-based queries. I would check for all white pixels within an AABB of the query triangle, then would check for each returned pixel if it lies within the query rectangle.
However, I'm not sure how well R-trees will behave since edge-based data will not be easily groupable into rectangles, as the points are clumped together on narrow lines and not pread out.
I'm alo not sure if it would make sense to pre-build the structure of the R-tree using information about the query triangles which will be made as soon as the structure is filled (as mentioned before, the query triangles are already known when the data arrives).
Reversing the problem seems also to be a valid solution, where I use a 2-dimensional interval tree to get for each white pixel a list of all triangles which contain it. Then, it can already be stored within all those result sets and be returned instantly when the query arrives. However, I'm not sure how this performs a the number of triangles is higher than the number of edges, but still lower than the number of white pixels (as an edge is mostly split up into ~20-50 pixels).
A data structure which would exploit that white pixels have most often white pixels as neighbors would seem to be most efficient. However, I could not find anything about such a thing until now.
Decompose the query triangle(s) into n*3 lines. For every point under test you can estimate at which side of every line it is. The rest is boolean logic.
EDIT: since your points are rasterised, you could precompute the points on the scanlines where the scanline enters or leaves a particular query triangle (=crosses one of the 3n lines above && is on the "inside" of the other two lines that participate in that particular triangle)
UPDATE: Triggered by another topic ( How can I find out if point is in triangle? ) I'll add code to prove that a non-convex case can be expressed en terms of "which side of every line a point is on". Since I am lazy, I'll use an L-shaped form. IMHO other Non-convex shapes can be processed similarly. The lines are parallel to the X- and Y- axes, but that again is laziness.
/*
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;
}
这篇关于查询位于三角形内的点的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
