优化三角网格以加速可见区域计算，提升查询效率12%-16%。
Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions
- 设计新三角网格结构，减少查询时的边扩展次数。
- 在真实场景模拟数据上，平均查询时间提升12%-16%。
- 适合需处理百万级查询的离线应用，预处理开销可接受。
本文针对三角展开算法（TEA）在计算多边形环境中可见区域时的查询性能问题，提出通过优化三角网格这一预处理结构来改进。TEA在遍历网格时递归追踪可见区域，我们发现查询时间近似正比于三角形边扩展次数。为此，提出一种新型三角网格，在已知查询点分布的前提下，最小化期望扩展次数。设计启发式方法近似该网格，并在多个类真实环境实例上评估。实验表明，相比基准的约束Delaunay三角剖分，所提方法使平均查询时间提升12%-16%。该方法适用于需处理百万级查询的离线任务，预处理时间可忽略。代码已公开，可供复现与使用。
原文摘要 · Abstract (English)
This paper addresses the problem of improving the query performance of the triangular expansion algorithm (TEA) for computing visibility regions by finding the most advantageous instance of the triangular mesh, the preprocessing structure. The TEA recursively traverses the mesh while keeping track of the visible region, the set of all points visible from a query point in a polygonal world. We show that the measured query time is approximately proportional to the number of triangle edge expansions during the mesh traversal. We propose a new type of triangular mesh that minimizes the expected number of expansions assuming the query points are drawn from a known probability distribution. We design a heuristic method to approximate the mesh and evaluate the approach on many challenging instances that resemble real-world environments. The proposed mesh improves the mean query times by 12-16% compared to the reference constrained Delaunay triangulation. The approach is suitable to boost offline applications that require computing millions of queries without addressing the preprocessing time. The implementation is publicly available to replicate our experiments and serve the community.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。