数据结构要查询的谎言一个三角形内点 [英] Data structure to query points which lie inside a triangle

问题描述

我有一个包含了被光栅化为像素边缘部分的二维数据。我想实现一个高效的数据结构，返回其位于一个无轴对准 2D的三角形的所有边缘像素。

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.

• 在进一步观察图像，人注意到我们有疏布尔数据，这意味着如果我们定义的黑色像素，0和白色像素，1，是数量1秒中的数据比0的个数要低得多。因此，栅格化的红色三角形，并检查它的每一点里面无论是白色或黑色是不是最有效的方法。

• 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.

中的数据必须在实时处理，但没有GPU的援助。将有多个查​​询作为不同的三角形的内容，各一个，点可以从数据结构删除。然而，新的积分将不再被所述数据结构的初始填充后插入

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 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树似乎是，我找到了最好的数据结构对于这个问题到现在为止，因为他们提供的矩形为基础的查询的支持。我会检查所有白色像素查询三角形的AABB内，然后将检查每个返回的像素，如果它坐落在查询矩形内。

• 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.

不过，我不知道有多好R树的行为，因为基于边缘的数据不会被轻易groupable成长方形，作为点成群一起在窄线，而不是$ P $垫了。

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.

我ALO不知道这是否将是有意义的pre-建立使用哪些将尽快为结构填充进行的查询信息的三角形R树的结构（如前面提到的，当数据到达查询三角形是已知的）。

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

倒车问题似乎也是一个有效的解决方案，在这里我使用 2-三维间隔树以获取每个白色像素包含其所有三角形的列表。然后，它可以已经被存储所有这些结果集内，并且可以立即返回的查询到达时。然而，我不知道这是如何进行的三角形的数量比边缘的数目更高，但比的白色像素数仍然较低（为边缘大多分成〜20-50像素）。

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.

推荐答案

分解查询三角形（S）为n * 3线。对于测试的每一个点，你可以估算在每一行是哪一方。剩下的就是布尔逻辑。

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.

编辑：因为你的点被光栅化，则可以precompute上，其中扫描线进入或离开特定查询三角形（=跨过上述＆安培的3n个线之一的扫描线的点;＆安培;是对内另外两条线参与该特定三角形）的

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)

更新：另一个话题触发（<一href="http://stackoverflow.com/questions/8332732/how-can-i-find-out-if-point-is-in-triangle/8333191#8333191">How我可以找出点是三角形？）我会加code证明一个非凸的情况下的可以是前pressed 的连接，其中条款每边线上的点上。因为我懒，我将使用一个L形的形式。 IMHO其他非凸形状可以类似被处理。该线平行于X轴和Y轴，但是这又是懒惰

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屋！