| Вопрос: Алгоритм построения многоугольника | Добавлено: 14.01.07 10:01 |
Автор вопроса:  Tur | ICQ: 201446364 |
|
В Excele есть всевозможные причудливые формы из единиц
11111 111111 111111 111111 11111 1111111 111111 111111111111 111111 111111111111111111111111 11111111111111111111111 111111111111111111 11111 111111 111 1111 111111 Требуется предложить алгоритм получения координат вершин огибающего многоугольника (для любых подобных форм) 11111 111111 1 1111 1 11 1 1 111 11 11 11 1 1111 1 111111 1 1111111 11 1 1111 1 11111 1 1 1 1 1 1 1 1111 111111 При этом форма считается связной если соседние единицы находятся не по диагонали, а только либо справа, либо слева, либо сверху, либо снизу. Это связная форма 1 111 1 Или эта 1 1 1111111111 1 111 1 1111 1 11 111111 А эта нет (здесь две формы) 1 11 11 1 |
| Ответы | Всего ответов: 13 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 14.01.07 19:46 |
| Любого огибающего или обязательно минимального? | ||
|
Номер ответа: 2 Автор ответа: Tur ICQ: 201446364 Вопросов: 22 Ответов: 72 |
Профиль | | #2 | Добавлено: 14.01.07 20:23 |
|
обязательно минимального
Положение отягчается тем что эти формы уложены в структуры: Type Section beg As Byte ena As Byte End Type Type OneByteLine row As Long ' строки нумеруются снизу вверх k As Byte ' число участков в строке k = Ubound(s) s() As Section End Type В массиве s() лежат начало и конец каждого участка, по строчно. Т.е. если в какой то строке идут единицы, затем прерываются, затем снова идут, то в s(1) будет начало и конец первого участка, в s(2) - второго итд |
||
|
Номер ответа: 3 Автор ответа: TurICQ: 201446364 Вопросов: 22 Ответов: 72 |
Профиль | | #3 | Добавлено: 14.01.07 20:33 |
|
Любая, абсолютно любая загагулина должна работать
111111111111111 11111111111 1 1 1 1 1 1 1111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 111111111 1111111 1 1 1 редактор этот все искажает, зараза |
||
|
Номер ответа: 4 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #4 | Добавлено: 14.01.07 20:47 |
| Используй тег CODE. Вроде бы твоя задача заключается в выделении компонент связности, соединению их пачкой вершин и затем удалении лишних с помощью алгоритма выделения наименьшего остовного дерева. | ||
|
Номер ответа: 5 Автор ответа: TurICQ: 201446364 Вопросов: 22 Ответов: 72 |
Профиль | | #5 | Добавлено: 14.01.07 21:53 |
|
Эти структуры мне вроде бы удалось разбить на формы:
Type OneForma id As Long r() As OneByteLine rows As Long par As Parameters ' 6 - Killed 1 - Just created Suspicious ( First line ) ' 2 - The section(or row) is added Continuous The row is already added ' 3 - Incorporated 4 - False 5 - Completed status As Byte End Type Сейчас речь идет о том чтобы построить огибающую для каждой формы В Excele есть всевозможные причудливые формы из единиц 11111 111111 111111 1 111111 11111 1111111 1111111 111111 1 111111111111 111111 1111 1 111111111111111111111111 1 11111 11111111111111111111111 1 111111111111111111 111 11111 111111 1 111 1111 111111 Требуется предложить алгоритм получения координат вершин огибающего многоугольника (для любых подобных форм) 11111 111111 1 1111 1 11 1 1 111 11 11 11 1 1111 1 111111 1 1111111 11 1 1111 1 11111 1 1 1 1 1 1 1 1111 111111 |
||
|
Номер ответа: 6 Автор ответа: TurICQ: 201446364 Вопросов: 22 Ответов: 72 |
Профиль | | #6 | Добавлено: 14.01.07 21:58 |
|
Лишние можно и не удалять, это мелочи.
Связность пока задана ближайшим соседством но не по диагонали. В дальнейшем это понятие м.б. изменено. |
||
|
Номер ответа: 7 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #7 | Добавлено: 14.01.07 23:08 |
|
11111
111111 1 1111 1 11 1 1 111 11 11 11 1 1111 1 111111 1 1111111 11 1 1111 1 11111 1 1 1 1 1 1 1 1111 111111 А почему в указанных жирным местах по две единицы, а не по одной например? |
||
|
Номер ответа: 8 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #8 | Добавлено: 14.01.07 23:10 |
блин CODE выделять неразрешает, а QUOTE пробелы не сохраняет 
Вообщем на диагоналях некотрых стенка состоит из двух единиц, а на некоторых их одной... |
||
|
Номер ответа: 9 Автор ответа: TurICQ: 201446364 Вопросов: 22 Ответов: 72 |
Профиль | | #9 | Добавлено: 15.01.07 00:32 |
|
HACKER, на этом рисунке уже приведен ответ для данной формы. По две единицы, т.к. нужна полная окантовка, захват. Прикинь сам, как долно быть, как бы ты провел?
11111 111111 1 1111 1 11 1 1 111 11 11 11 1 1111 1 111111 1 1111111 11 1 1111 1 11111 1 1 1 1 1 1 1 1111 111111 |
||
|
Номер ответа: 10 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #10 | Добавлено: 15.01.07 23:24 |
|
ну почему не
11111
111111 1 1111 1 1 1 1 1 1 11 11 11 1111 1 111111 1 1111111 1 1 1111 1 11111 1 1 1 1 1 1 1 1111 111111 ну итп, довольно много подобных вариантов можно наприсовать... |
||
|
Номер ответа: 11 Автор ответа: TurICQ: 201446364 Вопросов: 22 Ответов: 72 |
Профиль | | #11 | Добавлено: 16.01.07 10:54 |
| HACKER, не совсем так, точнее совсем не так, т.е. способ определения вершин многоугольника единственный и он полностью определен в моем ответе номер 9. Перенеси в точности мой рисунок в ответе 9 (или еще лучше полный вариант в ответе 5) в Excel(сделай в нем ширину столбцов 1) и ты увидишь то понятие на основе которого я провожу оболочку. Ты увидишь единственность оболочки приведенной в ответе 9. | ||
|
Номер ответа: 12 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #12 | Добавлено: 17.01.07 00:13 |
| ок сорр, значит я не в теме... Хотя возможно просто ты не понял, что я имел ввиду... Просто помойму вариант в посте 9 не единственный... | ||
|
Номер ответа: 13 Автор ответа: TurICQ: 201446364 Вопросов: 22 Ответов: 72 |
Профиль | | #13 | Добавлено: 17.01.07 13:39 |
| Алгоритм простой: натягиваем вокруг фигуры нитку и облегаем ей плотно фигуру. Если будут рядом с фигурой другие фигуры или отдельные клетки (единицы) которые лишь касаются по диагонали исходной фигуры, то игнорируем их. Все. Если есть что предложить какой-нибудь алгоритм, то буду рад. В первом приближении я это уже сделал, то получилось сложно и громоздко. А если придется в будущем менять понятие смежности, то все заново придется расписывать. Тяжело. | ||
Страница: 1 |