如何使用2D无限行作为关联容器的键，该关联容器可以通过邻近度进行查询？

Question

我有数以千计的线段，我想按共线性对它们进行聚类。要做到这一点，一种方法是创建一个具有无限行的键的关联容器。有了这样的容器，我可以使用线段的集合作为值，并通过确定作为线段的无限行并将其插入到相应的bin中来添加线段。

给定这样的设置，描述无限行的最佳方式是什么，以支持查询给定行附近的行键的数据结构的能力？

例如，我正在考虑使用点的R树(在这个项目的其他地方，我已经在使用Boost.Geometry R树)，其中每个点都是无限直线的x-截距和y-截距。但是，这只适用于非垂直和非水平线。我可以将垂直线和水平线作为特例来处理，但这样我就不能像通过在R-tree中对截点执行2D范围查询来查询靠近非轴对齐线的线那样，轻松地查询垂直线或水平线附近的线。

我想知道是否有一些优雅的方法来处理这个问题。如何将无限的二维线表示为点，使水平线和垂直线与任何其他类型的线没有区别，并且使彼此接近的线映射到彼此接近的点？

Answer 1

我有两个解决方案。第一个是一个简单的，但有一些限制：

对于每条无限长直线，可以计算直线上从原点绘制的垂线与直线相交处的点。您可以将该点的坐标存储为该线的“签名”。此解决方案将适用于所有线路，但通过原点的线路除外。这是因为当直线通过原点时，无论直线的斜率如何，“签名”点始终是原点。

第二个解决方案扩展了第一个解决方案来解决这个问题:除了上面描述的点的坐标之外，您还可以存储直线的法线与x轴的夹角。所以你可以用一个有序的三元组(x，y，theta)来表示每一行。您可以将这些三元组存储在三维点的rtree中，并查询该树。

通过原点的两条线的theta值可能分别为pi/4弧度和5*pi/4。它们是一致的，但是它们存储在rtree中的方式并不能反映这一点。所以对于通过原点的线，你可以强制执行一个约定，比如说- theta必须在0和pi之间。这样的约定可以解决这个问题。此约定仅适用于通过原点的线路。

更新：

提出一个更适合您的用例的解决方案将需要一个清晰的定义，即如何测量两条无限长的线之间的“接近度”。