Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Есть точка внутри контура, есть условия принадлежности контуру, как определить границы контура ? C чего начать ? Спасибо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 11:40 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
а конкретней можно? _______________________________________________________________ @Мы медленно запрягаем, быстро ездим, и сильно тормозим.@ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 11:48 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Привет, synapse! Ты пишешь: synapse s> а конкретней можно? Лаба по компьютерной графике. Тема - "заливка замкнутого контура". -- With best regards, Мимопроходящий. Posted via ActualForum NNTP Server 1.1 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 11:51 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
synapseа конкретней можно? т.е, вроде конкретно :) на выходе должны быть координаты границ контура ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 11:55 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Закрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу, и так пока хоть что-то закрашивается Вот решение в лоб, что-то вроде пузырька в сортировке :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 12:07 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
4d_monsterЗакрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу, и так пока хоть что-то закрашивается Вот решение в лоб, что-то вроде пузырька в сортировке :-) хотелось бы не рекурсивный алгоритм и нужно получить последовательность точек, что бы по ним можно было бы построить polyline. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 12:14 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Void666 synapseа конкретней можно? т.е, вроде конкретно :) на выходе должны быть координаты границ контура конкретно это значит на примере решть задачу с известными параметрами и неизвестными переменными составить уравнение и решить.... тем более раз уж ты не хочешь рекурсии то без уравнения никак (у мня вот был такой курс в высшей математике не помню как назывался но там как раз строили разные плоскости и решали уравнения принадлежности точки к этой плоскости (поверхности, фигуре)). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 13:02 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Void666 4d_monsterЗакрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу, и так пока хоть что-то закрашивается Вот решение в лоб, что-то вроде пузырька в сортировке :-) хотелось бы не рекурсивный алгоритм и нужно получить последовательность точек, что бы по ним можно было бы построить polyline. а алгоритм будет зависеть от фигуры... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 13:03 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
synapse Void666 synapseа конкретней можно? т.е, вроде конкретно :) на выходе должны быть координаты границ контура конкретно это значит на примере решть задачу с известными параметрами и неизвестными переменными составить уравнение и решить.... тем более раз уж ты не хочешь рекурсии то без уравнения никак (у мня вот был такой курс в высшей математике не помню как назывался но там как раз строили разные плоскости и решали уравнения принадлежности точки к этой плоскости (поверхности, фигуре)). Есть 2-x мерная матрица (n,m), Пусть значения матрицы числа от 10 до -10, Дана начальная точка nx0, mx0 ( [nx0,mx0] < -1). Нужно найти по начальной точке замкнутый контур (1 мерная матрица, значения которой координаты точек описывающий контур, при этом первое значение в матрице должно совпадать с последним, контур замкнутый). Условие пренадлежности точек контуру: [nx,mx] < -1; Вроде все. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 13:12 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
еще хотелось бы что бы алгоритм был побыстрее чем волновой алгоритм Ли :), например. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2005, 13:14 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
заметание плоскости называется 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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.04.2005, 00:48 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
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 слишком мало инфы, хотелось бы поподробнее ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.04.2005, 07:55 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Самый медленный и самый надежный алгоритм закрашивания произвольных областей - это применение механизма рекурсии (подробно можно посмотреть в любой книге по программированию графики), кстате выше уже пытались его изложить.... создаем рекурсивную функцию, в функцию передаются значения точки закрашивания, функция проверяет принадлежит ли точка заданной области и если да то для каждой соседней точки вызывает себя же... размер текста программы маленьки, работает медленно, так как какждая закрашиваемая точка проверяется на условия несколько раз, но этот алгоритм работает и очень хорошо работает для сложных областей... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.04.2005, 12:07 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
AL_KIRСамый медленный и самый надежный алгоритм закрашивания произвольных областей - это применение механизма рекурсии (подробно можно посмотреть в любой книге по программированию графики), кстате выше уже пытались его изложить.... создаем рекурсивную функцию, в функцию передаются значения точки закрашивания, функция проверяет принадлежит ли точка заданной области и если да то для каждой соседней точки вызывает себя же... размер текста программы маленьки, работает медленно, так как какждая закрашиваемая точка проверяется на условия несколько раз, но этот алгоритм работает и очень хорошо работает для сложных областей... Это все уже известно :), более быстрее будет волновой алгоритм (не будет рекурсии). Хотелось бы узнать о более мощных/быстрых/наукоемких алгоритмах, об их реализациях. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.04.2005, 14:11 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Нда, с грустью приходится констатировать что с распадом СССР математическая культура населения ассимптотически стремится к нулю. авторЕсть точка внутри контура, есть условия принадлежности контуру, как определить границы контура ? 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х мерная матрица - это просто тавтология, особое эстетическое наслаждение получил от одномерной матрицы... Резюмируя: сама по себе задача в том виде как она поставленна, некорректна, ибо решения не имеет. Если Вам надо отловить пикселя на экране, то это ещё туда-сюда. Если же это математическая задача, без какой-то дополнительной информации о контуре решить её строго не получится. Например, где то у Вас проскальзывает, что Вы хотели бы получить кусочно-линейное решение. Это уже что-то с чем можно работать. Однако боюсь что ничего кроме волнового алгоритма Вам не посоветуют, по крайней мере не на этом форуме. Попробуйте специализированные форумы, но для начала приведите в порядок терминологию, а то Вам просто там никто не ответит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.04.2005, 21:55 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
что мало? ---- В этом методе воображаемая вертикальная линия сканирования перемещается слева направо, пересекая геометрические объекты. В процессе обработки решаются задачи, относящиеся только к частям объектов, лежащим слева от линии сканирования. Когда линия сканирования перемещается достаточно далеко, то вся задача оказывается решенной. Например, при нахождении всех точек пересечения конечного множества отрезков на плоскости, последнюю можно разбить вертикальными прямыми, проходящими через концы всех отрезков, на полосы, внутри которых лежат точки пересечения тех отрезков, которые пересекают эти полосы; ---- идея понятная. теперь надо идти искать алгоритм (ключевые слова есть), если самому лень писать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.04.2005, 22:19 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
может уже и не в кассу, но описанный мной алгоритм не рекурсивный, а итеративный ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.04.2005, 13:53 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
4d_monsterЗакрасить все соседние точки если они не вышли за контур, потом все соседние всех точек, если они не вышли за границу, ..... потом все соседние всех точек, если они не вышли за границу, и так пока хоть что-то закрашивается Вот решение в лоб, что-то вроде пузырька в сортировке :-) Все правильно. Именно так. Только техника нужна правильная. Язык, в смысле. Открываем 10'000'000 невесомых потоков (через генераторы) и получаем ответ через 1 условную секунду. Например, задача об обходе шахматным конем доски размером 400х400 решается за пару секунд (конечно, без привлечения каких-то специальных эвристик и т.п.). Источники: 1. Гвидо ван Россум. "Краткий путеводитель по южным Нидерландам". 2. Тьен Вунь. "Введение в язык Icon. Ретроспекция и анализ." ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.04.2005, 22:04 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.07.2005, 22:19 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.07.2005, 15:22 |
|
||
|
Обход замкнутого контура, с чего начать ?
|
|||
|---|---|---|---|
|
#18+
Да что здесь называется контуром я уже давно понял. Просто во всём остальном мире, когда говорят о контуре как о математической категории, то имеют в виде линию, ограничивающую некую двумерную область, а не саму область. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2005, 00:04 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=33015881&tid=1347550]: |
0ms |
get settings: |
9ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
33ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
55ms |
get tp. blocked users: |
1ms |
| others: | 261ms |
| total: | 387ms |

| 0 / 0 |
