algorithm - 如何使用 R-tree 检测二维形状是否包含另一个形状？

Question

我有一个程序，其中 2D 形状由 R 树表示。我希望能够有效地检测一个形状是否完全包含在另一个形状中。这可能与 R-tree 吗？

Answer 1

如果形状是子元素，则表示它包含在父元素下。如果您在检测另一个多边形内的多边形时遇到问题，可以查看此链接。

检查多边形是否在多边形内

Answer 2

R-trees 作用于边界框。所以对于多边形内多边形测试，它可以作为一个有效的过滤步骤，但不能回答确切的查询。它产生候选人，并有效地跳过某些失误。