powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обход замкнутого контура, с чего начать ?
21 сообщений из 21, страница 1 из 1
Обход замкнутого контура, с чего начать ?
    #33010209
Void666
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть точка внутри контура, есть условия принадлежности контуру, как определить границы контура ? C чего начать ?

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

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

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

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


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

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

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

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


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

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

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

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

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


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

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

Есть 2-x мерная матрица (n,m), Пусть значения матрицы числа от 10 до -10, Дана начальная точка nx0, mx0 ( [nx0,mx0] < -1). Нужно найти по начальной точке замкнутый контур (1 мерная матрица, значения которой координаты точек описывающий контур, при этом первое значение в матрице должно совпадать с последним, контур замкнутый). Условие пренадлежности точек контуру: [nx,mx] < -1; Вроде все.
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #33010569
Void666
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
еще хотелось бы что бы алгоритм был побыстрее чем волновой алгоритм Ли :), например.
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #33012155
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #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
Обход замкнутого контура, с чего начать ?
    #33012925
AL_KIR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Самый медленный и самый надежный алгоритм закрашивания произвольных областей - это применение механизма рекурсии (подробно можно посмотреть в любой книге по программированию графики), кстате выше уже пытались его изложить....
создаем рекурсивную функцию, в функцию передаются значения точки закрашивания, функция проверяет принадлежит ли точка заданной области и если да то для каждой соседней точки вызывает себя же...

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

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

Это все уже известно :), более быстрее будет волновой алгоритм (не будет рекурсии). Хотелось бы узнать о более мощных/быстрых/наукоемких алгоритмах, об их реализациях.
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #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
Обход замкнутого контура, с чего начать ?
    #33014577
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
что мало?
----
В этом методе воображаемая вертикальная линия сканирования перемещается слева направо, пересекая геометрические объекты. В процессе обработки решаются задачи, относящиеся только к частям объектов, лежащим слева от линии сканирования. Когда линия сканирования перемещается достаточно далеко, то вся задача оказывается решенной. Например, при нахождении всех точек пересечения конечного множества отрезков на плоскости, последнюю можно разбить вертикальными прямыми, проходящими через концы всех отрезков, на полосы, внутри которых лежат точки пересечения тех отрезков, которые пересекают эти полосы;
----
идея понятная. теперь надо идти искать алгоритм (ключевые слова есть), если самому лень писать
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #33015881
Фотография 4d_monster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
может уже и не в кассу, но описанный мной алгоритм не рекурсивный, а итеративный
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #33017113
heizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
4d_monsterЗакрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу,
и так пока хоть что-то закрашивается

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

Источники:
1. Гвидо ван Россум. "Краткий путеводитель по южным Нидерландам".
2. Тьен Вунь. "Введение в язык Icon. Ретроспекция и анализ."
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #33172346
vilfred
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
...
Рейтинг: 0 / 0
Обход замкнутого контура, с чего начать ?
    #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
Обход замкнутого контура, с чего начать ?
    #33181068
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да что здесь называется контуром я уже давно понял. Просто во всём остальном мире, когда говорят о контуре как о математической категории, то имеют в виде линию, ограничивающую некую двумерную область, а не саму область.
...
Рейтинг: 0 / 0
21 сообщений из 21, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обход замкнутого контура, с чего начать ?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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