| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > построение огибающей ломаной линии |
| Автор: olegkuzn 12.11.2014, 10:01 |
| Пожалуйста помогите решить задачу. 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) Есть ли какой-нибудь алгоритм решения этой задачи или хотя бы где посмотреть примерно такую же задачу. Заранее благодарен. |
| Автор: Akina 12.11.2014, 10:20 |
| Объедините массивы в один, если иксы из отдельных ломаных совпадают, берите больший игрек. Отсортируйте по иксу. Для каждой пары "соседних иксов" выполните проверку на пересечение соотв. отрезков отдельных кривых в этом диапазоне, если пересечение имеется, причём не на границе, добавьте точку пересечения в массив. Для каждой тройки "последовательных иксов" выполните проверку нахождения трёх точек на одной прямой, если да - выбросьте среднюю точку, повторять, пока выбрасывать станет нечего. Задача решена. |
| Автор: olegkuzn 12.11.2014, 16:02 |
| по-моему не отсекаются "нижние" точки в объединенном массиве. или я что-то неправильно понял. |
| Автор: Akina 12.11.2014, 16:15 |
| Да, верно. При объединении массивов следует также выкидывать те точки одной из ломаных, которые лежат ниже соотв. отрезка второй ломаной. |