0

Advertisement

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?

Question author Gritcoandreea | Source

# Answer

1

Advertisement

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.

Answer author Tasos-papastylianou

Advertisement

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.