Построение кривой, равноудаленной от заданной

[sinsin]

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

[Dimka]

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

[sinsin]

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

[npak]

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

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

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

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

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

[Dimka]

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

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

[Джон]

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

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

[sinsin]

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

[Джон]

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

[sinsin]

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

[Алексей++]

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

[Dale]

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

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

[sinsin]

Решено перебором, с разными допусками по времени и амплитуде:

Код:

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..........
	/**/
	

Дальше оптимизирую.

[Dale]

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

[sinsin]

На рисунке.

[Dale]

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

[Джон]

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

[sinsin]

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

Добавлено через 9 минут и 3 секунды:

Код:

double a = PointsToSee;// смешение линии по времени
double b = MaxAmp*Dop;// по амплитуде

Если строить эквидистанту, то а надо брать равным b, тгогда будет по другому(рис, черная линия - данные, желтая и красная - ограничения)

[Dale]

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

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

[sinsin]

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

[Джон]

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

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

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

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

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

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

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

[sinsin]

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

[Джон]

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

хы Кстати, погрешность не такая уж и маленькая. Для прямого угла ~ 1,4 в единицах измерения.

[sinsin]

Согласен, вопрос был сфрмулирован не совсем четко. Для визуального сравнения достаточно.

[Джон]

Ок.

[Dimka]

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

[sinsin]

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

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

[Sla]

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

зы, увы пока так.

[sinsin]

Sla, спасибо.

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

[Джон]

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

[sinsin]

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