Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Построение кривой, равноудаленной от заданной  (Прочитано 37905 раз)
0 Пользователей и 1 Гость смотрят эту тему.
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« : 18-12-2010 06:35 » 

Доброго времени суток.
Есть задача: для кривой, заданной в виде массива коотдинат по оси У (координата по оси Х — номер элемента в массиве), построить две кривые, равноудаленные от неё (см. рис. во вложении).
Не знает ли кто-нибудь алгоритма решения или что можно почитать по данной теме?

* Илл.bmp (310.83 Кб - загружено 931 раз.)
« Последнее редактирование: 18-12-2010 08:17 от sinsin » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 18-12-2010 08:23 » 

По теме можно почитать учебник по аналитической геометрии в части аффинных преобразований. Тебе нужна операция параллельного переноса на вектор. И судя по рисунку, это вектор вида (0, dY).
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 18-12-2010 09:41 » 

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

* Илл.png (9.9 Кб - загружено 886 раз.)
« Последнее редактирование: 18-12-2010 09:44 от sinsin » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 18-12-2010 09:52 » 

Dimka, это на параллельный перенос. И не афинное преобразование. Это огибающие семейства окружностей.

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

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

Если про кривая непрерывна, то равноудаленные кривые тоже будут непрерывны. Из этого следует, что если удалось найти одну точку из искомой кривой, то следующая точка будет в окрестности найденной. То есть надо будет просматривать не всю плоскость, а только 8 точек вокруг найденной.

Получается такой алгоритм.
1. Отсортировать точки исходной кривой по возрастанию х.
2. Для минимального значения х найти у точки, которая будет на заданном расстоянии от кривой.
    Сделать найденную точку текущей
3. Найти следующую точку в окрестности текущей
    Сделать найденную точку текущей.
4. Если х текущей точки меньше максимального, вернуться на шаг 3
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 18-12-2010 10:05 » 

Да, на изгибы не обратил внимания.

Можно попробовать в (условно) гладких случаях использовать вектор нормали к кривой. А в точках разрыва первого рода, где существуют два вектора нормали, искать в окрестностях окружности, как предложено выше.
« Последнее редактирование: 18-12-2010 10:07 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #5 : 18-12-2010 10:56 » 

Построение эквидистантных линий  в общем случе есть нетривиальная задача. Приведённые рисунки ну никак таковые не отображают. Например, в углах это должны быть дуги или сплайны. Единственное верное решение подсказал npak - "огибающие семейства окружностей". Очень давно занимался этой проблемой разрабатывая CAD-софт для швейных машин. А недавно вернулся к ней: потребовалось сделать для элипса. Вот как это выглядит:
http://pmpu.ru/vf4/dets/discrim/equidist

sinsin, может тебе всё-таки что-то другое нужно?

Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 18-12-2010 13:02 » 

Вообще изначально задача звучит так: имеется график некоторой величины в виде массива точек, надо построить линии ограничения, отстоящие от графика на заданую величину, т.е. все-же эквидистанта. Насчет прямых углов - это просто наметки, т.е. могут быть и сплайны. Пока попробую способ с окружностью, только как-нибудь попытаюсь линейные участки оптимизировать.
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #7 : 18-12-2010 14:10 » 

Скорей всего, точки экспериментальные, а значит существует некоторый разброс - отклонения от идеальной ф-ции. Если сделать регрессионный анализ и получится хороший коэффициент корреляции, то график можно свести к простой ф-ции. А дальше по теории.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 18-12-2010 18:24 » 

Точки к простой функции не сведешь, разрывы все-равно будут, но попытаться выделить линейные участки можно, я думаю.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 20-12-2010 08:18 » 

sinsin, может быть, с нужной дискретностью на исходной кривой посчитать нормали и отложить на нормалях точки на заданном расстоянии в обе стороны. Соединить точки линиями, а если надо - аппроксимировать
Записан

Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #10 : 20-12-2010 09:05 » 

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

Неприятные проблемы возникали, когда осевая линия имела внутренний острый угол. Тогда простое смещение по нормали к контуру не работает, поскольку такой контур имеет самопересечения. Приходилось эти петли находить и отбрасывать. В остальных случаях все тривиально.
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 20-12-2010 10:24 » 

Решено перебором, с разными допусками по времени и амплитуде:
Код:
int PointsToSee = Sm;// смещение по времени в точках
double a = PointsToSee;//
double b = MaxAmp*Dop;//
// строим верхнюю огибающую
for (int k = 0;k<Num;k++)// для всех точек
{
    double Y = Src[k]+MaxAmp*Dop;
int Sn,En;
if (k-PointsToSee<0)
Sn = -k;
else
Sn = -PointsToSee;
if (k+PointsToSee>Num)
En = Num-k;
else
En = PointsToSee;
for (int z = Sn; z<=En; z++)
{
double Tmp = Src[k+z]+sqrt(b*b-z*z*b*b/(a*a));
if (Tmp>Y)
Y = Tmp;
}
Dst[k] = Y;
}
/**/
...... вывод графика - Dst..........
/**/
// строим нижнюю огибающую
for (int k = 0;k<Num;k++)
{
double Y = Src[k]-MaxAmp*Dop;
int Sn,En;
if (k-PointsToSee<0)
Sn = -k;
else
Sn = -PointsToSee;
if (k+PointsToSee>Num)
En = Num-k;
else
En = PointsToSee;
for (int z = Sn; z<=En; z++)
{
double Tmp = Src[k+z]-sqrt(b*b-z*z*b*b/(a*a));
if (Tmp<Y)
Y = Tmp;
}
Dst[k] = Y;
}
/**/
...... вывод графика - Dst..........
/**/

Дальше оптимизирую.
« Последнее редактирование: 20-12-2010 11:08 от sinsin » Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #12 : 20-12-2010 10:35 » 

Как алгоритм ведет себя на острых внутренних углах?
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 20-12-2010 10:41 » 

На рисунке.

* Безымянный.bmp (788.88 Кб - загружено 911 раз.)
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #14 : 20-12-2010 11:42 » 

По рисунку не слишком похоже, что точки A и B равноудалены от кривой. По-моему, оптимизировать рановато.

* EqDist.bmp (788.88 Кб - загружено 830 раз.)
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #15 : 20-12-2010 12:13 » 

Судя по рисунку, эквидистантами там близко не пахнет.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #16 : 20-12-2010 12:19 » 

Dale, Джон,  смешение по оси времени и амплитуде разное ("с разными допусками по времени и амплитуде"), поэтому так и выглядит. Если для эквидистанты надо катить по линии окружность, то здесь я протащил эллипс. В принципе  задача - построение ограничений -  решена.

Добавлено через 9 минут и 3 секунды:
Код:
double a = PointsToSee;// смешение линии по времени
double b = MaxAmp*Dop;// по амплитуде
Если строить эквидистанту, то а надо брать равным b, тгогда будет по другому(рис, черная линия - данные, желтая и красная - ограничения)

* Безымянный.bmp (599.54 Кб - загружено 3038 раз.)
« Последнее редактирование: 20-12-2010 12:34 от sinsin » Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #17 : 20-12-2010 12:34 » 

А как вообще формулируется задача?

Я к тому, что если вариации амплитуды и времени не коррелируют между собой, то не корректнее ли было бы вместо эллипса тащить прямоугольник?
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #18 : 20-12-2010 12:53 » 

См. пост №6: имеется график некоторой величины в виде массива точек, надо построить линии ограничения, отстоящие от графика на заданую величину.
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #19 : 20-12-2010 12:55 » 

А как вообще формулируется задача?

Это-то и хотелось выяснить с самого начала. Есть какое-то смутное сомнение, что всё-таки спрашивается не эквидистанта.

И кстати да? Почему именно элипс? Ведь его нужно ещё и вращать, чтобы например большая ось являлась нормалью к графику.

Цитата
См. пост №6: имеется график некоторой величины в виде массива точек, надо построить линии ограничения, отстоящие от графика на заданую величину.

Ну так полученные гарфики никак не удовлетворяют данному условию. См. аргумент Dale. Или эта величина непостоянна и тоже меняется во времени?

Добавлено через 2 минуты и 43 секунды:
Ещё раз, если спрашивается вот это:



то это не эквидистанта. Вершины у внутренних углов (желётая линия), так же как и первый и четвёртый красные углы. Это должны быть дуги.
« Последнее редактирование: 20-12-2010 12:58 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #20 : 20-12-2010 13:00 » 

Джон, есть такая небольшая погрешность, но на мой взгляд нормально. Основная цель  - визуальное сравнение данных и ограничений, а его выполнить можно.
« Последнее редактирование: 20-12-2010 13:04 от sinsin » Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #21 : 20-12-2010 13:01 » 

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

хы Кстати, погрешность не такая уж и маленькая. Для прямого угла ~ 1,4 в единицах измерения.
« Последнее редактирование: 20-12-2010 13:05 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #22 : 20-12-2010 13:06 » 

Согласен, вопрос был сфрмулирован не совсем четко. Для визуального сравнения достаточно.
« Последнее редактирование: 20-12-2010 13:09 от sinsin » Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #23 : 20-12-2010 13:11 » 

Ок.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #24 : 20-12-2010 15:42 » 

По-моему для визуальной отметки границ погрешности некоторой функции вида y=f(x) всё же достаточно сделать перенос вверх и вниз от графика. Если исходная функция имеет много зубцов, то границы можно сгладить скользящим средним или чем-нибудь в этом роде. Хотя равноудалённости при этом не будет - особенно на высоких "ступеньках".
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #25 : 20-12-2010 17:31 » 

Если есть разрывы в функции, как например на рисунке, то простой перенос ничего не даст(см.рис).

Оффтоп: как вставить рисунок, аналогично #21?

* Безымянный.png (6.6 Кб - загружено 2652 раз.)
« Последнее редактирование: 20-12-2010 18:12 от sinsin » Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #26 : 20-12-2010 17:56 » 

sinsin, копируешь ссылку на вложение, затем "изменить", вставляешь рисунок.

зы, увы пока так.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #27 : 20-12-2010 18:08 » 

Sla, спасибо.

Добавлено через 12 часов, 3 минуты и 16 секунд:
Может кому-нибудь пригодиться: статья по построению эквидистант: "An offset algorithm for polyline curves"  http://cgcad.thss.tsinghua.edu.cn/~yongjh/papers/CiI2007V58N03P0240.pdf
« Последнее редактирование: 21-12-2010 06:11 от sinsin » Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #28 : 21-12-2010 14:06 » 

Ок, но это всё-таки не построение эквидистанты в прямом смысле этого слова. Собственно говоря, я занимался ими в проекте для фирмы Dürkopp Adler - они делают промышленные швейные машинки-автоматы. В частности, которые пришивают карманы (ну как на рубашке). Так вот они тоже сначала загрузили нас эквидистантой. Нууу кто-то ляпнул умное слово. В общем мы пыжились-пыжились, решая задачу для общего случая. Потом они прислали эскизы, и оказалось, что им нужно именно подобное смещение, сдвиг на определённую величину, с сохранением основной формы. Например, нижний край кармана представляет собой угол (карман-пятиугольник), они пришивают его двойным швом, и ессно, что у второго шва это тоже должен быть угол. Эквидистанта же понимает в таком месте дугу окружности с радиусом равным смещению и центром в этом углу. Во всём остальном шов идёт параллельно заданному. Короче выяснили, что, слава Богу, таки не эквидистанта нужна. Ну и решали кусочно, для каждого конкретного случая.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
sinsin
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #29 : 21-12-2010 18:15 » 

У меня в принципе подобное -  данные, надо ориентировочно показать вержнюю и нижнюю границу допустимого воздействия.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines