Search code examples
prologbacktrackingpoints

All subsets of collinear points - Prolog

I am trying to make a backtracking program in Prolog to determine all subsets of collinear points. The problem: Are given n points in a plan (represented using its coordinates). Write a predicate to determine all subsets of collinear points.

Example :

Input: [ [1,1] , [2,2] , [3,3] , [0,0] , [4,8], [1,2], [6,7] , [8,9] , [10,11] ]

Output: [ [ [1,1] , [2,2] , [3,3] ] , [ [1,1] , [2,2], [0,0] ] , [ [2,2], [3,3], [0,0] ] , [ [1,1] , [3,3], [0,0] ] , ...]

So far I thaught at checking if 3 points are collinear by checking this formula :
(Xc - Xa)/ (Xb - Xa) = (Yc - Ya)/ (Yb - Ya).

But, I don't think this will work because I need to solve the problem using backtracking. I should take one candidate at each function call to see if it matches with the rest .

Could you suggest me a proper way of checking if 3 points are collinear?

Solution

  • I'm assuming your program query will be something like:

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

    Obviously I won't provide code to solve the whole problem for you, but in general a top-down approach could involve predicates like the following:

    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].

    You could then use these to find all possible Triplet unifications.
    Of course, some triplets are equivalent (e.g. [p(1,1), p(2,2), p(3,3)] and [p(3,3), p(1,1), p(2,2)]). Also, some will be repeated. If you want unique triplets, you'll have to manually build such a unique list from all non-unique triplets collected.

    Your final findColinears predicate for instance, might look something like:

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

    for appropriately defined convertToPoints and discardDuplicates predicates.