Форум программистов, компьютерный форум CyberForum.ru

Из точки А в точку В - C++

Восстановить пароль Регистрация
 
NativeLand
0 / 0 / 0
Регистрация: 27.12.2010
Сообщений: 46
22.08.2013, 12:52     Из точки А в точку В #1
Добрый день. Взялся за .. как мне показалось вначале .. легкую задачу и что-то засел над ней второй день... Код все больше и больше усложняю, но пока он криво работает...
Мб кто-то подскажет более-менее простой алгоритм ее решения?

Задача: дана матрица двумерная с значениями {0;1}. С помощью "1" изображена некая замкнутая кривая. Даются координаты точек А(START) и В(FINISH) на данной кривой. Необходимо по часовой стрелки из А в В перейти по всем точкам фигуры.

Мое решение было с такой идеей:
1. В зависимости какая из точек "выше" - соответственно от точки А и В перекодировать на .. скажем "1" на "2" до конца строк матрицы с точками А и В(или от начала строки до точки А и В при условии что точка В "выше" точки А).
2. Далее с верхней точки опускаться в нижнюю таким способом: а) начиная с верхней строки беру под ячейками с "2" три нижних ячейки и смотрю на наличие "1" .. если есть, изменяю на "2"; б) опускаюсь на эту же строку .. и проходя по всей строке ищу "2". Если есть "2", тогда все соседние к ней "1" изменяю на "2".
3. Повторяю процедуру "2" для новой строки до тех пор, пока не пройдусь от строки с А к строке с В.

Работает криво, т.к. ниже "нижней точки" не опускается. Т.е. если точка А и В в находятся в расстоянии нескольких пикселей на одной стороне кругоподобного чего-то - все работает нормально, а вот если по разные стороны (как показано на рисунке) - тогда не работает...
Миниатюры
Из точки А в точку В  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.08.2013, 12:52     Из точки А в точку В
Посмотрите здесь:

C++ Заменить в тексте каждую точку многоточием, если после точки есть пробел
C++ Найти точку D, симметричную точку A относительно стороны BC.
Вычислительная геометрия (Даны координаты центра, R окружности, координаты точки вне окруж-ти. Найти точку пересечения одной из касательных с окруж-ю) C++
Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки C++
C++ В введенной строке заменить каждую запятую и точку на точку с запятой
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
za5
440 / 344 / 30
Регистрация: 16.10.2010
Сообщений: 842
Записей в блоге: 7
22.08.2013, 13:21     Из точки А в точку В #2
я бы нашёл центр масс этой фигуры и отсортировал бы точки по углу которые они составляют с осью Х относительно центра. и тогда уменьшая угол мы будем идти по часовой;

хотя... нет. это для выпуклых фигур(многоугольников) справедливо.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
22.08.2013, 13:39     Из точки А в точку В #3
а если в лоб решить. стоим в точке с координатами х1 у1. ну и каким то образом (допустим пока что) нашли куда двигаться. у каждой точки есть ровно 8 соседних. часть из них отсекли (например 2 это обратное направление, и еще 3 это пустышки), а остальные рассматриваем. помечаем эти точки двоечками и заносим во временный массив к рассмотрению. теперь просматриваем этот массив временных точек (сейчас их 3). вокруг каждой из них так же есть только 8 точек. какие-то с 0, какие-то с 1, какие-то с 2. нас интересуют только те что с 1. ну и собственно повторяем процесс. ну это тупой алгоритм в лоб, да еще и рекурсивный. но наверняка рабочий
можно использовать не массив а стек и тогда алгоритм не будет рекурсивным.
NativeLand
0 / 0 / 0
Регистрация: 27.12.2010
Сообщений: 46
22.08.2013, 13:57  [ТС]     Из точки А в точку В #4
Цитата Сообщение от Kukurudza Посмотреть сообщение
а если в лоб решить. стоим в точке с координатами х1 у1. ну и каким то образом (допустим пока что) нашли куда двигаться. у каждой точки есть ровно 8 соседних. часть из них отсекли (например 2 это обратное направление, и еще 3 это пустышки), а остальные рассматриваем. помечаем эти точки двоечками и заносим во временный массив к рассмотрению. теперь просматриваем этот массив временных точек (сейчас их 3). вокруг каждой из них так же есть только 8 точек. какие-то с 0, какие-то с 1, какие-то с 2. нас интересуют только те что с 1. ну и собственно повторяем процесс. ну это тупой алгоритм в лоб, да еще и рекурсивный. но наверняка рабочий
можно использовать не массив а стек и тогда алгоритм не будет рекурсивным.
С этого "тупого" я и пытался начинать... Вот только есть куча нюансов - "стоп" по достижению матрицой 3х3 (текущая точка в центре) точки В? тогда и другие точки вокруг В не охватывает. Далее вопрос о том какие точки от А начинать перебирать - очень интересный .. т.к. направление пробовал определить по-разному .. ничего путного у меня не вышло.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
22.08.2013, 14:00     Из точки А в точку В #5
ну ответы на ваши вопросы должны быть в условии задачи. потому что действительно есть нетривиальные ситуации вокруг начальной точки. если это академическая задачка - в к преподавателю с этим вопросом. если для себя, чисто поржать, то считайте как хотите
NativeLand
0 / 0 / 0
Регистрация: 27.12.2010
Сообщений: 46
22.08.2013, 14:09  [ТС]     Из точки А в точку В #6
Цитата Сообщение от Kukurudza Посмотреть сообщение
ну ответы на ваши вопросы должны быть в условии задачи. потому что действительно есть нетривиальные ситуации вокруг начальной точки. если это академическая задачка - в к преподавателю с этим вопросом. если для себя, чисто поржать, то считайте как хотите
Да это для себя, чтобы мозг не ржавел... Решил, спасибо, кто откликнулся.
Нужно было немного усложнить ...
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
22.08.2013, 14:12     Из точки А в точку В #7
ну так решение в студию. где уважение к остальным участникам форума?
MousePro
49 / 30 / 1
Регистрация: 25.04.2013
Сообщений: 366
22.08.2013, 14:19     Из точки А в точку В #8
а если двигаться постоянно держась правой стенки (алгоритм обхода лабиринта) ???
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
22.08.2013, 14:20     Из точки А в точку В #9
тогда вы не все точки посетите. а по условию нужно все.
NativeLand
0 / 0 / 0
Регистрация: 27.12.2010
Сообщений: 46
22.08.2013, 14:22  [ТС]     Из точки А в точку В #10
Наворотил следующим образом к исходному алгоритму добавляю анализ по нижней/верхней точки (в зависимости от взаимного размещения А и В).
Т.е. мой же алгоритм предполагает аналог рекурсии с движением от верхней к нижней точке.
Я беру так же точки последней строки (или верхней, если на рисунки А и В поменять местами) и смотрю .. если из верхней точки опускается не к точке В, а к этим самым нижним точкам, тогда и из нижней точки я опускаюсь к этим точкам (или с верхних точек опускаюсь к точкам А и В, если опять же они будут изменены инверсивно на рисунке).
MousePro
49 / 30 / 1
Регистрация: 25.04.2013
Сообщений: 366
22.08.2013, 14:24     Из точки А в точку В #11
тогда двигаться от стенки к стенке ( как в змейке когда у тебя змейка большая)
NativeLand
0 / 0 / 0
Регистрация: 27.12.2010
Сообщений: 46
22.08.2013, 14:24  [ТС]     Из точки А в точку В #12
Цитата Сообщение от MousePro Посмотреть сообщение
а если двигаться постоянно держась правой стенки (алгоритм обхода лабиринта) ???
При "подъеме" вверх нужно его менять на движение держась левой стенки, по-идеи. Сей час почитаю, мб удастся его адаптировать как-то к этой задаче, спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.08.2013, 14:31     Из точки А в точку В
Еще ссылки по теме:

C++ Структуры. Точки. Найти точку, которая наиболее удалена от начала координат
Найти координаты второй точки, зная первую точку и расстояние между ними C++
Найти точку пересечения отрезка и перпендикуляра, опущенного на отрезок из точки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MousePro
49 / 30 / 1
Регистрация: 25.04.2013
Сообщений: 366
22.08.2013, 14:31     Из точки А в точку В #13
Ну считать в какую сторону ты двигаешься, с лево на право, снизу в верх и т.д
Yandex
Объявления
22.08.2013, 14:31     Из точки А в точку В
Ответ Создать тему
Опции темы

Текущее время: 08:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru