[street85]

Добрый день!

вобщем есть задача:

например есть "модель-1":

1 2
*--------*
| |
| |
*--------*
3 4

состоит из 4-х точек
связи:
1->3 , 1->2 , 2->4 , 3->4

например пользователь вводит:

3 2 1 4
*---------*-----------*-----------*

также у фигуры 4-е точки
и связи:
1->3, 3->2, 2->4, 1->4

Сравнивая все модели в "библиотеке(файлах)" и введенные данные программа должна вывести что введенные данные по определению является "модель-1". причём точек и связей может быть неограниченно.

Массивы связей и точек:

Код:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Type DotRec = record  id:integer;  x:integer;  y:integer;  z:integer; end;   Type LinkRec = record  id:integer;  first:integer;  last:integer; end;   var  DotArr: array of DotRec;  LinkArr: array of LinkRec;

у точек: id - уникальный номер, x,y,z - координаты
у связей: id - уникальный номер, first - начальная точка, last-конечная точка
first и last выбирается выберется из массива точек по уникальному номеру.

Заранее спасибо!

[AlexSku]

Пример ввода что-то подозрительно неправилен (напр., у модели 1 нет связи 3-2).

[street85]

Пример ввода что-то подозрительно неправилен (напр., у модели 1 нет связи 3-2).

это просто съехало при редактировании.
вот например "эталон-1":
(2.5 кб)
Точки

Код:

1 2 3 4

id:0 x:3 y:3 z:0 id:1 x:3 y:6 z:0 id:2 x:6 y:6 z:0 id:3 x:6 y:3 z:0

Связи

Код:

1 2 3 4

id:0 first:0 last:1 id:1 first:2 last:1 id:2 first:2 last:3 id:3 first:0 last:3

а вот ввод пользователя:
(2.5 кб)
Точки

Код:

1 2 3 4

id:0 x:7 y:7 z:0 id:1 x:4 y:5 z:0 id:2 x:3 y:6 z:0 id:3 x:7 y:3 z:0

Связи

Код:

1 2 3 4

id:0 first:1 last:2 id:1 first:1 last:0 id:2 first:3 last:0 id:3 first:3 last:2

и программа проанализировав эталоны должна вывести что ввод пользователя это "эталон-1".

[lmikle]

Какие критерии соответсвия шаблону?

[street85]

Какие критерии соответсвия шаблону?

По связи - вышеописанный пример тоесть необязательно пользователь ввёл квадрат но если связи соответсвуют квадрату то программа выдаст что это квадрат.

[lmikle]

Ну так и пиши сравнение по связям - кол-во и наличие нужных связей.
Я бы сначала проверял по кол-ву точек, потом по кол-ву связей, а уже если по первым 2м критериям сошлось, то проверяешь нужные связи, при этом проверяешь прямые и обратные связи, т.е. связь 2-3 соответсвует также связи 3-2 (если связи двунаправленные).

[street85]

Да это то понятно, но ведь пользователь необязательно введёт в таком порядке точки м связи например вот тоже "квадрат":
точки

id:0 x:7 y:3 z:0
id:1 x:2 y:7 z:0
id:2 x:8 y:9 z:0
id:3 x:3 y:3 z:0

связи

id:0 first:1 last:2
id:1 first:2 last:0
id:2 first:3 last:0
id:3 first:3 last:1

И если по такому методу сравнивать с эталоном описанном в 3-м посте то
ничего не получится , хотя должно...

[lmikle]

тогда еще перед сравнением сортируй точки с переименованием.
Иначе далее - распознавание образов, а это гораздо более сложная задача.

[street85]

Спасибо! Нет это всё заведёт в тупик... распознавание образов? так ведь квадрат может быть представлен в линию или в "песочные часы", тут скорее нужно всё представлять в матрице смежности и их уже сравнивать только как?

[AlexSku]

Песочные часы получатся, если поставить жёсткое ограничение, что четыре точки в одной плоскости. Но если хотя бы одна точка отклонится от этой плоскости хотя бы на чуть-чуть, то это будет уже обычная пространственная фигура без пересечений.

[street85]

Вобщем нужно установить изоморфизм неориентированных графов.