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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
NativeLand
0 / 0 / 0
Регистрация: 27.12.2010
Сообщений: 46
#1

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

22.08.2013, 12:52. Просмотров 521. Ответов 12
Метки нет (Все метки)

Добрый день. Взялся за .. как мне показалось вначале .. легкую задачу и что-то засел над ней второй день... Код все больше и больше усложняю, но пока он криво работает...
Мб кто-то подскажет более-менее простой алгоритм ее решения?

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

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

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

Найти точку пересечения отрезка и перпендикуляра, опущенного на отрезок из точки - C++
Привет! Помогите двоишнику, я же тупой батхэд :D! Есть отрезок, заданный двумя точками P1 и P2. Есть точка P3. Так вот, нужно найти...

Структуры. Точки. Найти точку, которая наиболее удалена от начала координат - C++
Решить задачу, используя структуру point для хранения координат точки. Найти точку, которая наиболее удалена от начала координат. Множество...

Заменить в тексте каждую точку многоточием, если после точки есть пробел - C++
Заменить в тексте каждую точку многоточием, если после точки есть пробел.

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

В введенной строке заменить каждую запятую и точку на точку с запятой - C++
В введенной строке заменить каждую запятую и точку на точку с запятой и вывести полученную строку.

Вычислительная геометрия (Даны координаты центра, R окружности, координаты точки вне окруж-ти. Найти точку пересечения одной из касательных с окруж-ю) - C++
Даны координаты центра (xc,yc) и радиус R окружности, координаты точки (x,y) вне окружности. Найти точку пересечения одной из касательных с...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
za5
440 / 344 / 30
Регистрация: 16.10.2010
Сообщений: 842
Записей в блоге: 7
22.08.2013, 13:21 #2
я бы нашёл центр масс этой фигуры и отсортировал бы точки по углу которые они составляют с осью Х относительно центра. и тогда уменьшая угол мы будем идти по часовой;

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

Найти точку D, симметричную точку A относительно стороны BC. - C++
помогите решить пожалуйста...

Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки - C++
Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки. Подсчитать количество сделанных замен.

Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки - C++
15. В введенной строке заменить все запятые на точки, а точки - на восклицательные знаки. Подсчитать количество таких замен. почему оно...

Найти точки пересечения прямых проходящих через заданные точки - C++
Всем привет! Прошу помощи в решении задачи: Дана система координат X:Y (по 25 точек в каждую сторону) В ней расположен ряд точек в...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.08.2013, 14:31
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru