计算无向线段平均方向的算法

Question

我有一组二维无向线段，由两个端点组成。据统计，它们中的大多数都或多或少地位于同一方向。

我想计算的是分段集的平均方向(例如，如果该集是全局 N/S，它会返回一些东西 ~ 0°，等等...) .请注意，我不关心返回哪个实际方向(0° 或 180° 都一样)。

将每个段的方向固定在 [0..180°[ 范围内并取平均值是行不通的(例如，两个段，一个 1°，另一个 -1°:第二个将固定到 179° 并且平均值是错误的，这里是 90°，应该是 0°)。

我也在考虑将“归一化段”端点聚类成两组，并计算由 2 个簇中点组成的段的方向，但这对于任务来说似乎有点复杂。 “归一化线段”是指在单位圆上具有两个端点且在原点处具有中点的线段。

是否有已知的算法/公式？

Answer 1

据我所知，段的位置并不重要，重要的是它们的方向。

所以我们可以稍微改变一下问题:我们有一组向量，我们想在它们上面画一条线。

我们可以对此采取不同的标准。常用的一种是最小二乘法。

对于这个标准，解决方案是:

double dvx=0,dvy=0;
for(const auto &direction:directions)
{
    dvx+=2*direction.dx*direction.dy;
    dvy+=squared(directions.dx)-squared(directions.dy);
}
return std::atan2(dvx,dvy)/2;//or may be +pi/2

注意:对于此实现，方向将按其长度加权，如果要分配相同的权重，则方向向量应归一化。

此方法有时用于确定指纹识别中的线条方向:http://jmit.us.edu.pl/cms/jmitjrn/22/28_Wieclaw_4.pdf

有几种方法可以理解这个方法。其中之一是几何的:

我们有一组与 X 轴成 alpha[i] 角度的向量。我们不对这些向量进行平均。相反，我们构建具有角度 2*alpha[i] 的向量，对它们进行平均并取所得角度的一半。诀窍在于，如果相反的方向相差 pi，并且在加倍后它们将相差 2*pi，这根本没有区别。