悠闲数学娱乐论坛(第2版)'s Archiver

hbghlyj 发表于 2021-6-30 15:53

寻找图形中的共线点

[i=s] 本帖最后由 hbghlyj 于 2021-6-30 16:01 编辑 [/i]

算法1.对i,j,k循环,$\begin{vmatrix}x_1&y_1&1\\x_2&y_2&1\\x_3&y_3&1\end{vmatrix}=0$
算法2.对i,j,k循环,$(y_j-y_i)(x_k-x_i)-(x_j-x_i)(y_k-y_i)$
算法3.对i,j循环,计算通过第i,j点的直线的斜率(并且舍入到$10^{-3}$),排序,如果$j_1,\cdots,j_n$所对应的斜率相等,就记下$(i,j_1),\cdots(i,j_n)$

hbghlyj 发表于 2021-6-30 16:05

[i=s] 本帖最后由 hbghlyj 于 2021-6-30 16:09 编辑 [/i]

以下面这组点为例:
p ={{1.34837, 0.86741}, {3.69674, 1.57346}, {1.07977, -0.60608}, {3.59698, -1.45794}, {2.01771,-0.92349}, {2.51764, 1.21895}, {1.63547, 0.09925}, {2.01779,0.17515}, {2.87027, 0.34438}}
----------
算法1.
AbsoluteTiming[Module[{}, S = {};
  For[i = 1, i <= Length[p] - 2, i++,
   For[j = i + 1, j <= Length[p] - 1, j++,
    f[{x_, y_}] = Det[{p[[i]]~Join~{1}, p[[j]]~Join~{1}, {x, y, 1}}];
    For[k = j + 1, k <= Length[p], k++,
     If[Abs[f[p[[k]]]] < 10^(-4), AppendTo[S, {i, j, k}]]]]];
  S /. Thread[{1, 2, 3, 4, 5, 6, 7, 8, 9} -> {"a", "b", "c", "d", "e",
       "f", "g", "h", "i"}]]]
输出为
{0.0007876, {{"a", "b", "f"}, {"a", "d", "h"}, {"a", "e", "g"}, {"b",
   "c", "h"}, {"b", "e", "i"}, {"c", "d", "e"}, {"c", "f", "g"}, {"d",
    "f", "i"}, {"g", "h", "i"}}}
测试多次,实际用时0.0007~0.0008秒

hbghlyj 发表于 2021-6-30 16:08

算法2.
AbsoluteTiming[Module[{}, S = {};
  For[i = 1, i <= Length[p] - 2, i++,
   For[j = i + 1, j <= Length[p] - 1, j++,
    f[{x_, y_}] = (p[[j, 2]] - p[[i, 2]]) (x -
         p[[i, 1]]) - (p[[j, 1]] - p[[i, 1]]) (y - p[[i, 2]]);
    For[k = j + 1, k <= Length[p], k++,
     If[Abs[f[p[[k]]]] < 10^(-4), AppendTo[S, {i, j, k}]]]]];
  S /. Thread[{1, 2, 3, 4, 5, 6, 7, 8, 9} -> {"a", "b", "c", "d", "e",
       "f", "g", "h", "i"}]]]
输出为
{0.0006969, {{"a", "b", "f"}, {"a", "d", "h"}, {"a", "e", "g"}, {"b",
   "c", "h"}, {"b", "e", "i"}, {"c", "d", "e"}, {"c", "f", "g"}, {"d",
    "f", "i"}, {"g", "h", "i"}}}
测试多次,实际用时0.0006~0.0007秒

hbghlyj 发表于 2021-6-30 18:18

算法3.其中用了[url=http://kuing.orzweb.net/viewthread.php?tid=8037&extra=]这帖[/url]的FindDuplicates函数.[code]
AbsoluteTiming[Module[{}, S = {}; g[{x_, y_}] = y/x;
  For[i = 1, i <= Length[p] - 2, i++, pi = p[[i]];
   dup = FindDuplicates[
     Table[Round[g[p[[j]] - pi], 10^(-3)], {j, i + 1, Length[p]}]];
   If[dup == {}, , S = S~Join~(Prepend[i] /@ (i + dup))]];
  S /. Thread[{1, 2, 3, 4, 5, 6, 7, 8, 9} -> {"a", "b", "c", "d", "e",
       "f", "g", "h", "i"}]]]
[/code]输出为
{0.0007199, {{"a", "b", "f"}, {"a", "d", "h"}, {"a", "e", "g"}, {"b",
   "c", "h"}, {"b", "e", "i"}, {"c", "d", "e"}, {"c", "f", "g"}, {"d",
    "f", "i"}, {"g", "h", "i"}}}
测试多次,实际用时0.0003~0.0004秒

hbghlyj 发表于 2021-6-30 18:20

结论:算法3是最快的

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.