共线点的所有子集 - Prolog

Question

我正在尝试在 Prolog 中制作回溯程序以确定共线点的所有子集。问题：在计划中给定 n 个点（使用其坐标表示）。写一个谓词来确定共线点的所有子集。

示例：

输入：[ [1,1] , [2,2] , [3,3] , [0,0] , [4,8], [1,2], [6,7] , [8,9] , [10,11] ]

输出：[ [ [1,1] , [2,2] , [3,3] ] , [ [1,1] , [2,2], [0,0] ] , [ [ 2,2], [3,3], [0,0] ] , [ [1,1] , [3,3], [0,0] ] , ...]

到目前为止，我想通过检查这个公式来检查 3 个点是否共线：
(Xc - Xa)/ (Xb - Xa) = (Yc - Ya)/ (Yb - Ya).

但是，我认为这行不通，因为我需要使用回溯来解决问题。我应该在每次函数调用时选择一个候选者，看看它是否与其余的匹配。

你能给我一个检查 3 个点是否共线的正确方法吗？

Answer 1

我假设您的程序查询类似于：

?- findColinears([[1,1],[2,2],[3,3],[0,0],[4,8],[1,2],[6,7],[8,9],[10,11]], Out).

显然我不会提供代码来为您解决整个问题，但通常自上而下的方法可能涉及如下谓词：

colinear( P1, P2, P3 ) :- slope( P1, P2, S ), slope( P1, P3, S ).
colinear( P1, P2, P3 ) :- slope( P1, P2, S ), slope( P2, P3, S ).
colinear( P1, P2, P3 ) :- slope( P1, P3, S ), slope( P2, P3, S ).

slope( P1, P2, S ) :-
  P1 = p( X1, Y1 ),
  P2 = p( X2, Y2 ),
  S is ((Y2-Y1)/(X2-X1)).

findColinearTriplet( ListOfPoints, Triplet ) :-
  member( P1, ListOfPoints ),
  member( P2, ListOfPoints ), dif(P1, P2),
  member( P3, ListOfPoints ), dif(P1, P3), dif(P2, P3),
  colinear(P1, P2, P3),
  Triplet = [P1, P2, P3].

然后您可以使用这些来找到所有可能的 Triplet 统一。
当然，有些三元组是等价的（例如 [p(1,1), p(2,2), p(3,3)] 和 [p(3,3), p(1,1), p(2,2)]）。另外，有些会重复。如果您想要独特的三胞胎，您必须从收集的所有非独特三胞胎中手动构建这样一个独特的列表。

例如，您的最终 findColinears 谓词可能类似于：

findColinears( ListOfPairs, Out ) :-
  convertToPoints( ListOfPairs, ListOfPts ),
  findall( Triplet, findColinearTriplet(ListOfPts, Triplet), ListOfTriplets),
  discardDuplicates( ListOfTriplets, Out ).

对于适当定义的 convertToPoints 和 discardDuplicates 谓词。

共线点的所有子集 - Prolog

All subsets of collinear points - Prolog

prolog

backtracking

points