优化给定任意平面上嘈杂数据点的圆心。

huangapple go评论117阅读模式
英文:

Optimize Center of Circle given noisy data points on arbitrary Plane

问题

我似乎找不到一种算法来计算在3D空间的任意平面上给定一组噪点数据(在圆周上)的圆心。我尝试过不同的方法,例如一次只取3个点然后对圆心求平均值,但我相信应该有更好的解决方案,通过最小化到所有点的距离来优化圆心。有人有什么想法吗?

任何想法或方法都将非常赞赏!

英文:

I don't seem to find an algorithm to calculate the center of a circle given a set of noisy data (on the circumference of the circle) on an arbitrary Plane in 3D.
I did try different approached as to calculating the center by only taking 3 points at a time and then averaging the centers, yet I believe there must be a better solution to optimize the center by minimizing the distance to all points.
Does anyone have an Idea?

Any Ideas or approaches would be highly appreciated!

优化给定任意平面上嘈杂数据点的圆心。

答案1

得分: 1

终于,我找到了几种调整我的搜索词汇的解决方案:

<https://de.mathworks.com/matlabcentral/answers/475212-circle-least-squares-fit-for-3d-data>

<https://jekel.me/2015/Least-Squares-Sphere-Fit/>

这两种方法都非常有效。在第二个链接中,您首先需要计算平面,可以使用奇异值分解(SVD)来完成。基本上,我认为这两种方法非常相似,基本上产生相同的结果。

英文:

Finally I found several Solutions adjusting my search terms:

<https://de.mathworks.com/matlabcentral/answers/475212-circle-least-squares-fit-for-3d-data>

<https://jekel.me/2015/Least-Squares-Sphere-Fit/>

Both Approaches work very well. In the second link you have to calculate the plane first, which can be done using SVD. Basically I think both approaches are very similar and produce basically the same results.

答案2

得分: 0

以下是翻译好的部分,代码部分未翻译:

这是我的方法:

我有一个辅助结构(称为Aprox),其中包含中心、半径(为了速度优化我使用其平方)和边界点(两个或三个)。

我有以下函数:

CircumscribedCircle_2Points(P1, P2):Aprox(3D线段的中心)

CircumscribedCircle_3Points(P1, P2, P3):Aprox(绘制的圆的中心),由https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_from_cross-_and-dot-products编程

CircumscribedCircle_IsIn($Aprox, $Pnt):boolean(它是否在给定的Approx中)

我从前两个点计算Aprox,然后遍历其他点。如果在圆内,我什么也不做;如果在圆外,我计算一个新的Aprox并再次遍历(所有点)。
规则是:如果平面上有4个点,其中一个总是在其他三个点构成的圆内。

  1. function CircumscribedCircle_2Points($P1, $P2, $Aprox=[])
  2. {
  3. $Aprox = as_New('Borders', [$P1, $P2]);
  4. $Aprox['Center'] = v3d_AvgV3($P1, $P2);
  5. $Aprox['RadSq'] = v3d_mV3AbsKv($Aprox['Center'], $P1);
  6. $Aprox['RadSq'] = $Aprox['RadSq'] + 0.0001; //浮点数舍入误差
  7. return $Aprox;
  8. }
  9. function CircumscribedCircle_3Points($P1, $P2, $P3, $Aprox=[], $JmP=0, $Jm=0, $u1=0, $u2=0, $u3=0)
  10. {
  11. $Aprox = as_New('Borders', [$P1, $P2, $P3]);
  12. $JmP = v3d_Abs(v3d_vxV3(v3d_mV3($P1, $P2), v3d_mV3($P2, $P3)));
  13. $Jm = 2 * $JmP**2;
  14. $u1 = v3d_mV3AbsKv($P2, $P3) * v3d_sxV3(v3d_mV3($P1, $P2), v3d_mV3($P1, $P3)) / $Jm;
  15. $u2 = v3d_mV3AbsKv($P1, $P3) * v3d_sxV3(v3d_mV3($P2, $P1), v3d_mV3($P2, $P3)) / $Jm;
  16. $u3 = v3d_mV3AbsKv($P1, $P2) * v3d_sxV3(v3d_mV3($P3, $P1), v3d_mV3($P3, $P2)) / $Jm;
  17. $Aprox['Center'] = v3d_pV3pV3(v3d_xSkl($P1, $u1), v3d_xSkl($P2, $u2), v3d_xSkl($P3, $u3));
  18. $Aprox['RadSq'] = v3d_mV3AbsKv($P1, $P2) * v3d_mV3AbsKv($P2, $P3) * v3d_mV3AbsKv($P3, $P1) / (2*$JmP)**2;
  19. $Aprox['RadSq'] = $Aprox['RadSq'] + 0.0001; //浮点数舍入误差
  20. return $Aprox;
  21. }
  22. function CircumscribedCircle_IsIn($Aprox, $Pnt)
  23. {
  24. return v3d_mV3AbsKv($Aprox['Center'], $Pnt) <= $Aprox['RadSq'];
  25. }
  26. // 更多代码...

这段代码是通用的,可以在PHP和Javascript中使用。我将辅助变量声明为可选参数(以避免使用var关键字)。

as_*函数与关联数组相关,ar_*函数与数值数组相关,nm_*函数与数值相关,其功能从函数名称中就可以看出来。v3d_*函数与3D向量相关,并在脚注中列出。

这段代码已经翻译完毕,如果你需要更多帮助,请告诉我。

英文:

Here's how I do it:

I have an auxiliary structure (called Aprox) that contains Center, Radius (I use its square for speed optimization) and Boundary points (two or three).

I have the following functions:

CircumscribedCircle_2Points(P1, P2):Aprox (center of the line segment in 3D)

CircumscribedCircle_3Points(P1, P2, P3):Aprox (center of the circle traced ), programmed by https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_from_cross-_and_dot-products

CircumscribedCircle_IsIn($Aprox, $Pnt):boolean (It is in the given Approx)

I compute Aprox from the first two points and then run through the other points. If it's in circle I do nothing, if it's out I calculate a new Aprox and run through again (all points).
The rule is: If there are 4 points in the plane, one of them is always inside the circle given by the other three.

  1. function CircumscribedCircle_2Points($P1, $P2,
  2. $Aprox=[])
  3. {
  4. $Aprox = as_New(&#39;Borders&#39;, [$P1, $P2]);
  5. $Aprox[&#39;Center&#39;] = v3d_AvgV3($P1, $P2);
  6. $Aprox[&#39;RadSq&#39;] = v3d_mV3AbsKv($Aprox[&#39;Center&#39;], $P1);
  7. $Aprox[&#39;RadSq&#39;] = $Aprox[&#39;RadSq&#39;] + 0.0001; //Float rounding errors
  8. return $Aprox;
  9. }
  10. function CircumscribedCircle_3Points($P1, $P2, $P3,
  11. $Aprox=[],$JmP=0,$Jm=0,$u1=0,$u2=0,$u3=0)
  12. //https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_from_cross-_and_dot-products
  13. {
  14. $Aprox = as_New(&#39;Borders&#39;, [$P1, $P2, $P3]);
  15. $JmP = v3d_Abs(v3d_vxV3(v3d_mV3($P1,$P2),v3d_mV3($P2,$P3)));
  16. $Jm = 2 * $JmP**2;
  17. $u1 = v3d_mV3AbsKv($P2,$P3) * v3d_sxV3(v3d_mV3($P1,$P2),v3d_mV3($P1,$P3)) / $Jm;
  18. $u2 = v3d_mV3AbsKv($P1,$P3) * v3d_sxV3(v3d_mV3($P2,$P1),v3d_mV3($P2,$P3)) / $Jm;
  19. $u3 = v3d_mV3AbsKv($P1,$P2) * v3d_sxV3(v3d_mV3($P3,$P1),v3d_mV3($P3,$P2)) / $Jm;
  20. $Aprox[&#39;Center&#39;] = v3d_pV3pV3(v3d_xSkl($P1,$u1), v3d_xSkl($P2,$u2), v3d_xSkl($P3,$u3));
  21. $Aprox[&#39;RadSq&#39;] = v3d_mV3AbsKv($P1,$P2) * v3d_mV3AbsKv($P2,$P3) * v3d_mV3AbsKv($P3,$P1) / (2*$JmP)**2;
  22. $Aprox[&#39;RadSq&#39;] = $Aprox[&#39;RadSq&#39;] + 0.0001; //Float rounding errors
  23. return $Aprox;
  24. }
  25. function CircumscribedCircle_IsIn($Aprox, $Pnt)
  26. {
  27. return v3d_mV3AbsKv($Aprox[&#39;Center&#39;], $Pnt) &lt;= $Aprox[&#39;RadSq&#39;];
  28. }
  29. function CircumscribedCircle_SetAprox($Aprox, $Pnt,
  30. $HrLen=0,$i=0,$TestAprox=[],$Ok=true,$j=0, $TestRet=[])
  31. {
  32. $HrLen=ar_Count($Aprox[&#39;Borders&#39;]); //2 or 3
  33. for ($i=0; $i&lt;$HrLen; $i++)
  34. {
  35. $TestAprox = CircumscribedCircle_2Points($Aprox[&#39;Borders&#39;][$i], $Pnt);
  36. $Ok = true;
  37. for ($j=0; $j&lt;$HrLen; $j++)
  38. {
  39. if ($i==$j) continue;
  40. if (CircumscribedCircle_IsIn($TestAprox, $Aprox[&#39;Borders&#39;][$j])) continue;
  41. $Ok = false;
  42. break;
  43. }
  44. if ($Ok) return $TestAprox;
  45. }
  46. if ($HrLen==2)
  47. {
  48. return CircumscribedCircle_3Points($Aprox[&#39;Borders&#39;][0], $Aprox[&#39;Borders&#39;][1], $Pnt);
  49. }
  50. $TestRet = ar_New();
  51. $TestAprox = CircumscribedCircle_3Points($Aprox[&#39;Borders&#39;][0], $Aprox[&#39;Borders&#39;][1], $Pnt);
  52. if (CircumscribedCircle_IsIn($TestAprox, $Aprox[&#39;Borders&#39;][2])) ar_Push($TestRet, $TestAprox);
  53. $TestAprox = CircumscribedCircle_3Points($Aprox[&#39;Borders&#39;][0], $Aprox[&#39;Borders&#39;][2], $Pnt);
  54. if (CircumscribedCircle_IsIn($TestAprox, $Aprox[&#39;Borders&#39;][1])) ar_Push($TestRet, $TestAprox);
  55. $TestAprox = CircumscribedCircle_3Points($Aprox[&#39;Borders&#39;][1], $Aprox[&#39;Borders&#39;][2], $Pnt);
  56. if (CircumscribedCircle_IsIn($TestAprox, $Aprox[&#39;Borders&#39;][0])) ar_Push($TestRet, $TestAprox);
  57. ar_Sort($TestRet, function($a, $b){return $a[&#39;RadSq&#39;]-$b[&#39;RadSq&#39;];});
  58. return $TestRet[0];
  59. }
  60. function CircumscribedCircle($Arr,
  61. $Aprox=[], $i=0, $l=0, $max=0)
  62. {
  63. $Aprox = CircumscribedCircle_2Points($Arr[0], $Arr[1]);
  64. for ($i=0, $l=ar_Count($Arr); $i&lt;$l; $i++)
  65. {
  66. if (CircumscribedCircle_IsIn($Aprox, $Arr[$i])) continue;
  67. $Aprox = CircumscribedCircle_SetAprox($Aprox, $Arr[$i]);
  68. if (!$Aprox) return false;
  69. $i=-1;
  70. }
  71. return as_New(&#39;Center&#39;,$Aprox[&#39;Center&#39;], &#39;Radius&#39;, nm_Sqrt($Aprox[&#39;RadSq&#39;]));
  72. }
  73. //-------------------------
  74. in JS
  75. const x = 0;
  76. const y = 1;
  77. const z = 2;
  78. in PHP
  79. define(&#39;x&#39;, 0);
  80. define(&#39;y&#39;, 1);
  81. define(&#39;z&#39;, 2);
  82. function v3d_AvgV3($v, $w)
  83. //Diameter of two vectors (center of the line segment)
  84. {
  85. return ar_New(($v[x]+$w[x])/2, ($v[y]+$w[y])/2, ($v[z]+$w[z])/2);
  86. }
  87. function v3d_Abs($v)
  88. //Absolute vector size
  89. {
  90. return nm_Sqrt($v[x]**2 + $v[y]**2 + $v[z]**2);
  91. }
  92. function v3d_vxV3($v,$w)
  93. //Vector product
  94. {
  95. return ar_New($v[y]*$w[z]-$w[y]*$v[z], $v[z]*$w[x]-$w[z]*$v[x], $v[x]*$w[y]-$w[x]*$v[y]);
  96. }
  97. function v3d_mV3Abs($v, $w)
  98. //Vector difference
  99. {
  100. return nm_Sqrt(($v[x]-$w[x])**2 + ($v[y]-$w[y])**2 + ($v[z]-$w[z])**2);
  101. }
  102. function v3d_mV3AbsKv($v, $w)
  103. //Square of vector difference
  104. {
  105. return ($v[x]-$w[x])**2 + ($v[y]-$w[y])**2 + ($v[z]-$w[z])**2;
  106. }
  107. function v3d_sxV3($v,$w)
  108. //Scalar product
  109. {
  110. return $v[x]*$w[x] + $v[y]*$w[y] + $v[z]*$w[z];
  111. }
  112. function v3d_pV3pV3($v,$w,$u)
  113. //Sum 3 3D vect
  114. {
  115. return ar_New($v[x]+$w[x]+$u[x], $v[y]+$w[y]+$u[y], $v[z]+$w[z]+$u[z]);
  116. }
  117. function v3d_xSkl($v,$k)
  118. //3D vect multiple scalar
  119. {
  120. return ar_New($v[x]*$k, $v[y]*$k, $v[z]*$k);
  121. }

The code is universal and works both in PHP and Javascript 优化给定任意平面上嘈杂数据点的圆心。 I declare auxiliary variables as optional parameters (to avoid using var keyword)

as_* are functions related to associative arrays, ar_* are functions related to numeric arrays, nm_* is numeric and their function is clear from their name. v3d_* are functions related to 3d vectors and are listed in the footnote.

Translated with www.DeepL.com/Translator (free version)

huangapple
  • 本文由 发表于 2023年2月23日 22:31:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/75546221.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定