Prolog查询数据库点构成的等边三角形返回同点重复结果问题

问题根因 #

• 谓词未约束三个点的唯一性：equilateral_triangles/1中匹配point/3事实时，没有限制P1、P2、P3必须为不同的点，Prolog回溯时会将三个变量绑定到同一个点上，此时计算出的三个边长均为0，天然满足相等条件，因此最先返回的全是三个顶点完全相同的无效三角形。
• 浮点数运算存在精度风险：直接调用sqrt计算边长再做严格相等判断，即便三个点构成合法等边三角形，浮点数计算的微小误差也可能导致相等判断失败，漏过有效结果。
• 存在重复返回问题：即便补充了点不重复的约束，同一个三角形会因为三个顶点的排列顺序不同（共6种排列方式）被重复返回多次，产生冗余结果。

修复后代码 #

:- dynamic
 point/3.
% ?Point_Sign, ?Abscissa, ?Ordinate
db_filling:-
    point(_,_,_),!.
db_filling:-
    assert(point(a,1,1)),
    assert(point(b,1,2)),
    assert(point(c,1,3)),
    assert(point(d,2,2)),
    assert(point(e,3,3)),
    assert(point(f,-1,1)),
    assert(point(g,-2,1)),
    assert(point(h,-2,2)),
    assert(point(i,-3,3)),
    assert(point(j,-3,-1)),
    assert(point(k,-3,-2)),
    assert(point(l,-3,-3)),
    assert(point(n,-1,-1)),
    assert(point(m,-3,0)),
    assert(point(o,3,0)),
    assert(point(p,0,3)).

% +List
points_main(Xs):-
    db_filling,
    findall(Xs1,equilateral_triangles(Xs1),Xs).

% +Points
equilateral_triangles([P1,P2,P3]):-
    point(P1,X1,Y1),
    point(P2,X2,Y2),
    % 约束P1在排序上小于P2，排除同点、减少重复排列
    P1 @< P2,
    point(P3,X3,Y3),
    % 约束P2在排序上小于P3，保证三个点互不相同、固定排列顺序
    P2 @< P3,
    % 直接计算边长平方，省略开方步骤减少浮点数误差
    D1 is (X2 - X1)^2 + (Y2 - Y1)^2,
    D2 is (X3 - X2)^2 + (Y3 - Y2)^2,
    D3 is (X1 - X3)^2 + (Y1 - Y3)^2,
    % 带误差容忍的相等判断，规避浮点数精度问题
    abs(D1 - D2) < 1e-6,
    abs(D2 - D3) < 1e-6.

修复逻辑说明 #

• 加入P1 @< P2、P2 @< P3的项比较约束：一方面直接排除两个或三个点为同一个点的无效情况，从根源上解决返回全同顶点三角形的问题；另一方面固定三个顶点的选取顺序，每个三角形仅会被匹配一次，不会出现同一三角形重复返回的冗余问题。
• 移除sqrt开方计算：等边三角形的判定等价于三边边长的平方相等，省略开方步骤既可以减少计算量，又能降低浮点数运算的精度损失。
• 替换严格相等判断为误差容忍判断：浮点数运算存在固有精度误差，当两个边长平方的差值小于1e-6时即判定为边长相等，避免有效三角形因为极小的计算误差被漏判。

运行修复后的代码可以正确过滤无效的同点三角形，返回数据库中符合要求的等边三角形结果。

内容的提问来源于stack exchange，提问作者annd