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.
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?
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
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.
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
Answer author Tasos-papastylianou
Tickanswer.com is providing the only single recommended solution of the question All subsets of collinear points - Prolog under the categories i.e prolog , backtracking , points , . Our team of experts filter the best solution for you.