0

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

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

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

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

4

1 回答 1

0

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

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

第二种解决方案扩展了第一种解决方案:除了上述点的坐标之外,您还可以存储线的法线与 x 轴形成的角度。因此,您将用有序的三元组 (x, y, theta) 表示每一行。您可以将这些三元组存储在 3d 点的 rtree 中并查询该树。

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

更新:

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

于 2020-11-10T00:21:09.290 回答