Все подмножества коллинеарных точек - Prolog

Я пытаюсь сделать программу возврата в Prolog для определения всех подмножеств коллинеарных точек. Проблема: заданы n точек в плане (представлены с использованием его координат). Напишите предикат для определения всех подмножеств коллинеарных точек.Все подмножества коллинеарных точек - Prolog

Пример:

Входной сигнал: [[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 точки являются коллинеарными?

источник

2016-12-09 GritcoAndreea

То, что вы описали, не совсем понятно! Вы должны дать хотя бы простой пример ввода и ожидаемого вывода ... Из того, что я понял. Если у вас есть список точек, вы можете рекурсивно проверить их в группе из 3, чтобы увидеть, являются ли они коллинеарными и как базовый случай последние 3 балла .... – coder

@coder, я привел здесь пример. Извините за это, я полностью забыл. И да, мне нужно рекурсивно найти все подмножества из 3 точек, которые являются коллинеарными. – GritcoAndreea

, что вход не имеет смысла в качестве прологового стартового запроса ... но в целом у вас есть правильная идея. Три точки a, b, c являются колинеарными, если наклон a, b и b, c один и тот же (но для любого порядка входов). –

Я предполагаю, что запрос программы будет что-то вроде:

?- 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 предикатов.

источник

2016-12-09 20:58:21

Большое спасибо @ Tasos! – GritcoAndreea

- Cu placere :) –

Все подмножества коллинеарных точек - Prolog

ответ

Смежные вопросы