我有一組2D無向片段，由兩個端點組成。統計上大多數人都在或多或少地處於相同的方向。計算無向片段的平均方向的算法
我想要計算的是段集合的平均值方向（例如，如果集合是全局N/S，它會返回〜0°等等......）。請注意，我不關心返回哪個實際方向（0°或180°將同樣）。
將[0..180°]範圍內的每個段的方向夾緊，並取平均值不起作用（例如兩個段，一個1°，另一個-1°：第二個夾緊到179°平均值是錯誤的，這裏是90°，應該是0°）。
我也在考慮對兩組中的「歸一化段」終點進行聚類，並計算由兩個聚類中點組成的段的方向，但這對於任務似乎有點複雜。所謂「標準化段」，是指在單位圓上具有兩個端點並且在原點上具有中點的部分。
是否有已知的算法/公式？
據我瞭解段的位置並不重要，只有他們的方向。
所以我們可以稍微改變一下問題：我們有一組向量，我們想在它們上面放一條線。
我們可以爲此採取不同的標準。常用的是最小二乘。
對於這個標準的解決方案是：
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這是沒有任何區別。
有is method找到角度的平均（在全圓形範圍）
MeanAngle = ArcTan2(Sum{i=1..n}(Sin(Alpha[i])), Sum{i}(Cos(Alpha[i])))
看來爲你情況下，可以計算平均方向矢量的餘弦（因爲餘弦（-alpha）= cos（阿爾法）），並獲得ARCCOS（在範圍0..Pi）
MeanAngleWithoutDir = ArcCos(1/n * Sum{i=1..n}(Cos(Alpha[i])))
大概角應鉗位到（0..Pi）或（-Pi/2..Pi/2）的範圍內，以避免混淆。
這是行不通的。對於兩段的簡單情況，一個在10°，另一個在-10°，則公式給出10°的平均值，而預期的解爲0°。 –
@LaurentGrégoire我再次懷疑問題形式：「平均（-10.10）= 0」。但爲了你的目的'-10 = 170'。 「平均值（170,10）= 90'。矛盾......這個問題是否可以解決？ – MBo
這個問題是明確可解的，請參閱我的答案。訣竅確實是處理模180°井。平均180°模數的角度顯然是錯誤的（-10°和10°是預期回答爲0°而不是90°的簡單示例）。 –
元注意：此答案計算給定行的「位數」。 MBo的other answer計算給定線的「平均值」。
讓我們以下面的方式來形式化問題。 我們給出了一系列線條，並且我們希望找到一條線p，使得p與所有給定線之間的角度之和是最小可能的。 這裏，兩條直線之間的角度是交叉點處角度的最小值，如果它們平行或重合，則爲0。因此，兩條線之間的角度總是從0度到90度。
爲了讓事情變得更簡單，請翻譯這些句子，以便它們全都通過原點。 顯然，這不會影響答案。
爲了解決這個問題，讓我們研究所述和的導數。 假設我們有一個答案行p。 要有X線，從p順時針0-90度，和ÿ線，是0-90度逆時針從p（X + Y = N，總數給出的線條）。
現在，由一個小的角度α按順時針方向旋轉p。 答案將減少x * α並增加y * α。 因此，如果x> y，答案會減少，如果x < y，它會增加。
有兩種情況，其中數量x和y更改。
線p與給定線中的一條相重合。
該行q與給定行之一正交。
圓上的任何兩個這樣的連續點之間，我們的總和的衍生物將是恆定說明X - Y。 因此，最小值將在「角度」之一：或者與某些給定線平行或正交。 這導致爲O（n^2）算法：對於每一個所述爲O（n）感興趣的角度，只是計算在爲O（n）總和，並選擇其給出的最小和的角度。
這可以進一步加速至爲O（n log n）的。
生成感興趣的2 n個角度在爲O（n）。
將它們排序在O（n log n）。
計算了答案，並且還X和ÿ，在爲O（n）第一個這樣的角度。
沿圓周移動，保持目前的答案和值X和ÿ。 在O（n）步驟的每一箇中，可以在O（1）中完成計算。
低於O(n)解決方案，也可以容納每個分段的可選重量。
我們通過它與X軸的角度（a）用權重（w）對每個段進行建模。分段方向在這一點上並不重要，任何180°的模值都可以。這個想法是爲每個分段循環並跟蹤到目前爲止計算的平均方向;並用平均值更接近平均值180的方向調整此平均值。
的僞代碼（以度爲單位的所有角度）：
aa = 0
ww = 0
for a, w in segments:
// Compute delta between angles in range [-180°..+180°[
da = a - aa
if da < -180:
da += 360
if da >= 180:
da -= 360
// Optional direction swap, delta in [-90°..+90°[
if da < -90:
da += 180
if da >= 90:
da -= 180
// The following formula also make sure aa = a mod 180
// when ww = 0 (first iteration).
aa += da * w/(w + ww)
ww += w
// Clamp result to [0°..+360°[
if aa >= 360:
aa -= 360
if aa < 0:
aa += 360
// Clamp final result aa to [0..+180°[ (optional step)
if aa > 180:
aa -= 180
沒表明，結果獨立於迭代順序，但在算法的乍一看是應該的。
對於性能良好的輸入數據，算法無論迭代順序的非常穩定。然而，只要輸入數據沒有明確的主方向，該算法的這個結果在很難預測混沌模式下將強烈依賴於迭代順序。數值模擬表明，對於標準偏差爲小於20°的中心的隨機方向（中值附近），算法似乎總是穩定的。標準偏差大於20°時，數值不穩定性開始出現，並且結果強烈依賴於迭代次序（20°至30°之間的差異可能足夠小以至於忽略30°以上的大差異開始出現）。
我並沒有準確計算出確切的混沌/穩定標準偏差截止值，因此以此20°值作爲初始猜測值。一個確切的數學解決方案留給讀者作爲練習。在數值模擬的結果下（對於0到45°的每個標準偏差，對給定標準偏差的各種隨機數據運行1000次算法，並測量10次運行之間的平均增量）。
因此，最好的結果，如果輸入的數據是不能保證有一個小的標準差，它可能是最好的，訂單中的穩定鍵輸入數據（重量更大第一，或任何其他關鍵取決於你的輸入）。
統計上大部分都在或多或少相同的 方向。
這個關鍵信息將在您的算法設計中至關重要。如果您知道您所有的矢量躺在90度錐內，你可以使用一個非常簡單的方法：
如果您需要處理更廣泛的銷售，你可以稍微修改此：
這是一個串行算法，但如果你需要更高的性能這可以很容易地配製成平行下降：
這些方法中的任何可以很容易地ONL加權爲你y關心點積的標誌。
不幸的是，它們中的所有*都不在90°錐體內。但其中的大部分可能會圍繞平均值進行分組。我的數據集在均值附近確實具有高斯分佈，我的標準偏差是10-20°。 –
據我所知，這將平均*矢量*。我有*無向段*，所以段和他的對面（兩端交換）應該被認爲是相同的。 –
@LaurentGrégoire，請參閱我已添加到最後的解釋 – maxim1000
非常好，實際上訣竅是將軸承的平均值乘以2，然後將此平均值減半。 Btw爲我的需要，我使用了正弦和餘弦的簡單加權平均值。 –