我有一些包含被光栅化成像素的边缘的2D数据。我想实现一个高效的数据结构,以返回所有位于非轴对齐2D三角形中的边缘像素。
当进一步查看图像时,人们会注意到我们有稀疏的布尔数据,这意味着如果我们用0表示黑色像素,用1表示白色像素,则数据中1的数量远低于0的数量。因此,对红色三角形进行光栅化,并检查其内部每个点是白色还是黑色并不是最有效的方法。
除了数据的稀疏性之外;由于白色像素源自边缘,它们天生就是相互连接在一起的。然而,在与其他线条的交点处,它们有多于两个邻居。在交汇处的像素应该只返回一次。
数据必须实时处理,但没有GPU的帮助。将为不同的三角形内容提出多个查询,并在每个查询后从数据结构中删除点。然而,在填充数据结构后,不会再插入新点。
当栅格化边缘到达时,已知查询三角形。
查询三角形比数据边缘更多。
现在有很多空间数据结构可供选择。然而,我想知道,哪一个是最适合我的问题的。我愿意实现一个高度优化的数据结构来解决这个问题,因为它将成为项目的核心要素。因此,也欢迎使用混合或缩写的数据结构!
R-trees 看起来是我目前为止找到的最适合这个问题的数据结构,因为它们提供了基于矩形的查询支持。我将检查查询三角形 AABB 中的所有白色像素,然后将检查每个返回的像素是否位于查询矩形内。
然而,我不确定 R 树的表现会如何,因为基于边缘的数据不容易分组成矩形,因为点在狭窄的线上聚集在一起而不是散布开来。
我也不确定是否有意义使用关于查询三角形的信息预先构建 R 树的结构,这些信息将在填充结构时立即生成(如前所述,当数据到达时已经知道查询三角形)。
反向解决问题似乎也是一个有效的解决方案,其中我使用二维区间树为每个白色像素获取包含它的所有三角形的列表。然后,它可以已经存储在所有这些结果集中,并在查询到达时立即返回。但是,我不确定当三角形数量高于边数但仍低于白色像素数量时,它的性能如何(因为一个边通常会分成约20-50个像素)。
利用白色像素通常有白色像素作为邻居的数据结构似乎最有效。但是,到目前为止我还没有找到任何关于这样的东西的信息。