如何使用 2D 无限线作为可以按接近度查询的关联容器的键?

How can I use 2D infinite lines as keys of an associative container that can be queried by proximity?

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

鉴于这样的设置,什么是表征无限线以支持查询数据结构以查找给定线附近的线键的能力的最佳方式?

例如,我正在考虑使用点的 R 树(在这个项目的其他地方我已经在使用 Boost.Geometry R 树),其中每个点都是一个点的 x 截距和 y 截距无限线。但是,这仅适用于非垂直和非水平线。我可以将垂直线和水平线作为特殊情况处理,但是我将无法像查询非轴附近的线那样轻松查询“靠近”垂直线或水平线的线通过对 R 树中的截取点进行二维范围查询来对齐线。

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

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

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

第二个解决方案扩展了第一个解决该问题的方法: 除了上述点的坐标外,您还可以存储线的法线与 x-axis 的角度。所以你会用一个有序的三元组 (x, y, theta) 来表示每一行。您可以将这些三元组存储在 rtree 中以获得 3d 点并查询该树。

通过原点的两条直线的 theta 值分别为 pi/4 弧度和 5*pi/4。它们是巧合的,但它们在 rtree 中的存储方式并没有反映出这一点。因此,对于通过原点的直线,您可以强制执行一个约定,例如 - theta 必须介于 0 和 pi 之间。这样的约定将解决问题。此约定应仅对通过原点的线强制执行。

更新:

想出一个更适合您的 use-case 的解决方案将需要明确定义如何测量两条无限直线之间的“接近度”。