寻找图形中的共线点

hbghlyj

算法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

以下面这组点为例:
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

算法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

算法3.其中用了这帖的FindDuplicates函数.

2. AbsoluteTiming[Module[{}, S = {}; g[{x_, y_}] = y/x;
3.   For[i = 1, i <= Length[p] - 2, i++, pi = p[[i]];
4.    dup = FindDuplicates[
5.      Table[Round[g[p[[j]] - pi], 10^(-3)], {j, i + 1, Length[p]}]];
6.    If[dup == {}, , S = S~Join~(Prepend[i] /@ (i + dup))]];
7.   S /. Thread[{1, 2, 3, 4, 5, 6, 7, 8, 9} -> {"a", "b", "c", "d", "e",
8.        "f", "g", "h", "i"}]]]

复制代码

输出为
{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

结论:算法3是最快的