построение огибающей ломаной линии , построение огибающей ломаной линии

[olegkuzn]

Пожалуйста помогите решить задачу.
1. Есть два массива A[m] и B[n] точек point(x, y). Каждый массив образует свою ломаную кривую.
2. первые точки каждого массива находится на координате x = 0. (A[1] = point(0, ya) ; B[1] = point(0, yb))
3. последние точки каждого массива находится на координате x = l. (A[m] = point(l, ya) ; B[1] = point(l, yb))
4. координата x точки point(x, y) в массивах A и B строго по возрастанию, координата y неотрицательна

Необходимо найти "верхнюю огибающую" ломаную кривую (т.е.) кривую линии которой идут по наиболее "верхней" линии каждой из данных ломаных кривых.
Исходные ломаные кривые могут пересекаться (и как правило часто пересекаются). Отрезки ломаных
кривых могут налагаться друг на друга.

Пример :
Ломаная№1 : (0.0, 0.0) ; (4.0, 4.0) ; (6.0, 2.0) ; (7.0, 3.0) ; (8.0, 2.0) ;(10.0, 4.0);
Ломаная№2 : (0.0, 4.0) ; (3.0, 1.0) ; (6.5, 4.5) ; (9.0, 2.0) ; (10.0, 3.0);

"Огибающая" : (0.0, 4.0);(2.0, 2.0);(4.0, 4.0);(5.0, 3.0);(6.5, 4.5);(8.5, 2.5);(10.0, 4.0)

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

Заранее благодарен.

[Славян]

1.Делаете фиктивный указатель на пару массивов якобыА и якобыB так, что якобыА всегда был выше.
Т.е. если вдруг ya<yb, то поменяете эти фиктивные имена, а сами массивы не трогаете.
2.Идёте пошагово по линии из верхнего массива якобыА, проверяя, не пересекли ли мы вдруг отрезок из массива якобыB.
3.Если пересекли, то очевидно меняете имена местами, а точку пересечения вносите в новую для огибающей.
4.Иначе (если не пересекли), то идёте в п.2.
5.Так до конца.
По времени должны уложиться в O(m+n).

Добавлено 12.11.14, 17:07
Очевидно, что в п.4 (перед переходом в п.2) вносите очередную точку, к коей пришли, тоже в новую для огибающей.

[MBo]

Что вызывает затруднения? Вроде бы сермяжный алгоритм является оптимальным:
Встали в первую точку обеих наборов. Выбрали большую Y-координату. Если одинаковые, выбираем ту ломаную, у которой наклон первого отрезка более положителен.
Идем по индексам обоих наборов, как в алгоритме слияния - если X - координата очередной первого набора меньше - продвигаемся по нему, иначе по второму.
В каждой точке проверяем пересечение последних отрезков. Если есть - заносим точку пересечения в новый набор, иначе заносим очередной конец отрезка, если он выше отрезка другого набора.