algorithm - 从多个 2D 点构造线并测量这些线之间的距离
问题描述
给出了二维平面上的多个点。它们代表了一个主要为矩形的窗框,并带有一些可能的变化。不保证作为每一边一部分的点形成一条完美的线。应测量窗口的每一侧。
安装在窗户上的旋转电子设备可测量各个方向的距离,提供 360 度测量。通过使用旋转角度和距离,一组点被绘制在二维坐标系上。到目前为止,一切都很好。
现在来了更难的部分。测量的窗框可能有一些变化。这些点应转换为直线,并应测量每条线的长度。
我想需要以下步骤:
- 将不同的点组合成直线。这意味着逼近形成它的点“之间”的每条线。
- 绘制这些线,摆脱用于构造线的单独点。
- 找到每两条线相交的点。
- 测量这些点之间的距离。然而,并非所有点之间的所有距离都是有趣的。例如,框架内的对角线是不相关的。
任何可以解决问题的处理几何的 Java 库都是可以接受的。我将用 Kotlin/Java 编写解决方案,但欢迎使用任何其他语言或伪代码的任何算法见解或代码示例和想法。
先感谢您!
新图片
解决方案
我将分两个阶段解决这个问题:
- 数据清洗:将每个点的位置(X,Y)四舍五入到其最接近的 N 倍数(根据不同的精度改变 N)
- 应用礼品包装算法(也称为 Jarvis March)
- 您现在只有那些不共线的点,它们之间的线,以及它们需要遍历以形成周长的顺序。
- 依次遍历点,取点Px和P(x+1),计算它们之间的距离。