Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обход замкнутого контура, с чего начать ? / 21 сообщений из 21, страница 1 из 1
12.04.2005, 11:40
    #33010209
Void666
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Есть точка внутри контура, есть условия принадлежности контуру, как определить границы контура ? C чего начать ?

Спасибо
...
Рейтинг: 0 / 0
12.04.2005, 11:48
    #33010228
synapse
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
а конкретней можно?
_______________________________________________________________
@Мы медленно запрягаем, быстро ездим, и сильно тормозим.@
...
Рейтинг: 0 / 0
12.04.2005, 11:51
    #33010243
Мимопроходящий
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Привет, synapse!
Ты пишешь:

synapse s> а конкретней можно?
Лаба по компьютерной графике.
Тема - "заливка замкнутого контура".

--
With best regards, Мимопроходящий.

Posted via ActualForum NNTP Server 1.1
...
Рейтинг: 0 / 0
12.04.2005, 11:55
    #33010252
Void666
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
synapseа конкретней можно?


т.е, вроде конкретно :)
на выходе должны быть координаты границ контура
...
Рейтинг: 0 / 0
12.04.2005, 12:07
    #33010291
4d_monster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Закрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу,
и так пока хоть что-то закрашивается

Вот решение в лоб, что-то вроде пузырька в сортировке :-)
...
Рейтинг: 0 / 0
12.04.2005, 12:14
    #33010314
Void666
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
4d_monsterЗакрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу,
и так пока хоть что-то закрашивается

Вот решение в лоб, что-то вроде пузырька в сортировке :-)

хотелось бы не рекурсивный алгоритм и нужно получить последовательность точек, что бы по ним можно было бы построить polyline.
...
Рейтинг: 0 / 0
12.04.2005, 13:02
    #33010513
synapse
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Void666 synapseа конкретней можно?


т.е, вроде конкретно :)
на выходе должны быть координаты границ контура

конкретно это значит на примере решть задачу с известными параметрами и неизвестными переменными составить уравнение и решить....
тем более раз уж ты не хочешь рекурсии то без уравнения никак (у мня вот был такой курс в высшей математике не помню как назывался но там как раз строили разные плоскости и решали уравнения принадлежности точки к этой плоскости (поверхности, фигуре)).
...
Рейтинг: 0 / 0
12.04.2005, 13:03
    #33010521
synapse
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Void666 4d_monsterЗакрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу,
и так пока хоть что-то закрашивается

Вот решение в лоб, что-то вроде пузырька в сортировке :-)

хотелось бы не рекурсивный алгоритм и нужно получить последовательность точек, что бы по ним можно было бы построить polyline.

а алгоритм будет зависеть от фигуры...
...
Рейтинг: 0 / 0
12.04.2005, 13:12
    #33010562
Void666
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
synapse Void666 synapseа конкретней можно?


т.е, вроде конкретно :)
на выходе должны быть координаты границ контура

конкретно это значит на примере решть задачу с известными параметрами и неизвестными переменными составить уравнение и решить....
тем более раз уж ты не хочешь рекурсии то без уравнения никак (у мня вот был такой курс в высшей математике не помню как назывался но там как раз строили разные плоскости и решали уравнения принадлежности точки к этой плоскости (поверхности, фигуре)).

Есть 2-x мерная матрица (n,m), Пусть значения матрицы числа от 10 до -10, Дана начальная точка nx0, mx0 ( [nx0,mx0] < -1). Нужно найти по начальной точке замкнутый контур (1 мерная матрица, значения которой координаты точек описывающий контур, при этом первое значение в матрице должно совпадать с последним, контур замкнутый). Условие пренадлежности точек контуру: [nx,mx] < -1; Вроде все.
...
Рейтинг: 0 / 0
12.04.2005, 13:14
    #33010569
Void666
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
еще хотелось бы что бы алгоритм был побыстрее чем волновой алгоритм Ли :), например.
...
Рейтинг: 0 / 0
13.04.2005, 00:48
    #33012155
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
...
Рейтинг: 0 / 0
13.04.2005, 07:55
    #33012259
Void666
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
tchingizзаметание плоскости называется
http://search.rambler.ru/srch?words=%22%DA%C1%CD%C5%D4%C1%CE%C9%D1+%D0%CC%CF%D3%CB%CF%D3%D4%C9%22&where=1

слишком мало инфы, хотелось бы поподробнее
...
Рейтинг: 0 / 0
13.04.2005, 12:07
    #33012925
AL_KIR
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Самый медленный и самый надежный алгоритм закрашивания произвольных областей - это применение механизма рекурсии (подробно можно посмотреть в любой книге по программированию графики), кстате выше уже пытались его изложить....
создаем рекурсивную функцию, в функцию передаются значения точки закрашивания, функция проверяет принадлежит ли точка заданной области и если да то для каждой соседней точки вызывает себя же...

размер текста программы маленьки, работает медленно, так как какждая закрашиваемая точка проверяется на условия несколько раз, но этот алгоритм работает и очень хорошо работает для сложных областей...
...
Рейтинг: 0 / 0
13.04.2005, 14:11
    #33013380
Void666
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
AL_KIRСамый медленный и самый надежный алгоритм закрашивания произвольных областей - это применение механизма рекурсии (подробно можно посмотреть в любой книге по программированию графики), кстате выше уже пытались его изложить....
создаем рекурсивную функцию, в функцию передаются значения точки закрашивания, функция проверяет принадлежит ли точка заданной области и если да то для каждой соседней точки вызывает себя же...

размер текста программы маленьки, работает медленно, так как какждая закрашиваемая точка проверяется на условия несколько раз, но этот алгоритм работает и очень хорошо работает для сложных областей...

Это все уже известно :), более быстрее будет волновой алгоритм (не будет рекурсии). Хотелось бы узнать о более мощных/быстрых/наукоемких алгоритмах, об их реализациях.
...
Рейтинг: 0 / 0
13.04.2005, 21:55
    #33014554
mikhail_n
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Нда, с грустью приходится констатировать что с распадом СССР математическая культура населения ассимптотически стремится к нулю.

авторЕсть точка внутри контура, есть условия принадлежности контуру, как определить границы контура ? C чего начать ?

Начать нужно с себя. Ибо если условие принадлежности точки контуру есть, то в чем, чёрт возьми, проблема? А, ну тут следует догадаться что под контуром подразумевается область (кстати что о ней-то известно - выпуклая/невыпуклая, односвязная/многосвязная?), этим самым контуром ограниченная... Интересно, что ни у кого, кроме synapse, вопросов не возникло, все всё как-то так по дефолту решили что это

авторЛаба по компьютерной графике.
Тема - "заливка замкнутого контура".

Хотя данная гипотеза безусловно имеет право на существование, в дальнейших постах тов. Void666 она прямого подтверждения не получила, хотя, справедливости ради, должен отметить что и опровергнута им не была. Однако для всех тех, кто считает, что только применение механизма рекурсии спасёт отца Русской демократии, позволю сформулировать задачу следующим образом:

Неизвестный заданный контур - окружность с центром в начале координат и радиусом R. Функция принадлежности точки области ограниченной данной окружности:

bool within(double x, double y)
{
return R*R - x*x + y*y > 0;
}

текст функции приведен здесь только с демонстрационными целями, по условиям задачи он не доступен, т.е. есть чёрный ящик в который можно передать декартовы или какие нибудь ещё координаты точки и получить true если точка лежит внутри области ограниченной контуром и false в противном случае. При такой постановке задачи, ответа от рекурсивного алгоритма мы дождёмся через 10**N лет, где N - число пикселей на экране Вашего монитора (шутка). Но вообще-то меня несколько озадачило, с какой лёгкостью все рванули считать пиксиля...

Извиняюсь за флейм, но не мог просто так пройти мимо этого:

авторЕсть 2-x мерная матрица (n,m), Пусть значения матрицы числа от 10 до -10, Дана начальная точка nx0, mx0 ( [nx0,mx0] < -1). Нужно найти по начальной точке замкнутый контур (1 мерная матрица,...

хотя и 2х мерная матрица - это просто тавтология, особое эстетическое наслаждение получил от одномерной матрицы...

Резюмируя: сама по себе задача в том виде как она поставленна, некорректна, ибо решения не имеет. Если Вам надо отловить пикселя на экране, то это ещё туда-сюда. Если же это математическая задача, без какой-то дополнительной информации о контуре решить её строго не получится. Например, где то у Вас проскальзывает, что Вы хотели бы получить кусочно-линейное решение. Это уже что-то с чем можно работать. Однако боюсь что ничего кроме волнового алгоритма Вам не посоветуют, по крайней мере не на этом форуме. Попробуйте специализированные форумы, но для начала приведите в порядок терминологию, а то Вам просто там никто не ответит.
...
Рейтинг: 0 / 0
13.04.2005, 22:19
    #33014577
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
что мало?
----
В этом методе воображаемая вертикальная линия сканирования перемещается слева направо, пересекая геометрические объекты. В процессе обработки решаются задачи, относящиеся только к частям объектов, лежащим слева от линии сканирования. Когда линия сканирования перемещается достаточно далеко, то вся задача оказывается решенной. Например, при нахождении всех точек пересечения конечного множества отрезков на плоскости, последнюю можно разбить вертикальными прямыми, проходящими через концы всех отрезков, на полосы, внутри которых лежат точки пересечения тех отрезков, которые пересекают эти полосы;
----
идея понятная. теперь надо идти искать алгоритм (ключевые слова есть), если самому лень писать
...
Рейтинг: 0 / 0
14.04.2005, 13:53
    #33015881
4d_monster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
может уже и не в кассу, но описанный мной алгоритм не рекурсивный, а итеративный
...
Рейтинг: 0 / 0
14.04.2005, 22:04
    #33017113
heizer
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
4d_monsterЗакрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу,
и так пока хоть что-то закрашивается

Вот решение в лоб, что-то вроде пузырька в сортировке :-)
Все правильно. Именно так. Только техника нужна правильная. Язык, в смысле.
Открываем 10'000'000 невесомых потоков (через генераторы) и получаем ответ
через 1 условную секунду.
Например, задача об обходе шахматным конем доски размером 400х400 решается
за пару секунд (конечно, без привлечения каких-то специальных эвристик и т.п.).

Источники:
1. Гвидо ван Россум. "Краткий путеводитель по южным Нидерландам".
2. Тьен Вунь. "Введение в язык Icon. Ретроспекция и анализ."
...
Рейтинг: 0 / 0
18.07.2005, 22:19
    #33172346
vilfred
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
...
Рейтинг: 0 / 0
22.07.2005, 15:22
    #33180362
Yossarian
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
2 mikhail_n

Вы ошибаетесь с постановкой задачи. Контур здесь - область ненулевой
ширины. И есть критерий принадлежности точки контуру.

2Void666 : я знаю 2 алгоритма. Первый - сканирование по кругу.
Пусть точка (x,y) принадлежит контуру. Тогда рассмотрим точки x+-1
y+-1 - всего таких 8. Пусть (например) точка (x-1,y-1) тоже принадлежит
контуру (мы это узнали на предыдущем шаге). Тогда начинаем перебирать
точки по кругу от (x-1,y) до (x,y-1). Первая принадлежащая контуру
становится текущей, а текущая - базой для начала следующего круга.

Второй метод - кусочно-линейная аппроксимация. Пусть у нас есть участок
контура в виде отрезка прямой (строго математически - отрезок, целиком
лежащий внутри контура). Пусть этот отрезок имеет длину L. и один из
его концов - точка (x,y). Продолжим его до тех пор, пока он не выйдет за
границы контура. (точка х1 у1) Теперь будем менять наклон луча, исходящего
из (x,y) влево-вправо от исходного значения. Найдем максимум длины
которую таким образом удастся получить. Если нестрогий максимум
получается в (х1, у1) то выбрасываем точку (х,у) вообще и продолжаем
отрезок. В противном случае добавляем (х1 у1) - (найденная точка)

Washington Irving
...
Рейтинг: 0 / 0
23.07.2005, 00:04
    #33181068
mikhail_n
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Обход замкнутого контура, с чего начать ?
Да что здесь называется контуром я уже давно понял. Просто во всём остальном мире, когда говорят о контуре как о математической категории, то имеют в виде линию, ограничивающую некую двумерную область, а не саму область.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обход замкнутого контура, с чего начать ? / 21 сообщений из 21, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]