сечение поверхности

incwizitor

посоветуйте способы решения или дайте линки на любые материалы касательно следующей проблемы.
есть поверхность заданная на равномерной сетке с шагом h (на прямоугольнике)..в принципе она гладкая и от 0 до 1
требуется для любого 0 < s < 1 построить контура которые соответствуют сечению z=s и выдать их с любым шагом (к примеру h/4). для поверхности применяется квадратичная аппроксимация.
контура должны быть выданы в любом удобном формате-как полигоны-самое простое....самое интересное уметь разбивать контура на компоненты связности.
алгоритм должен быть быстрым , то бишь "сделан с умом"
не знаю кто сообразительнее-программеры или математики поэтому в стади тоже написал

NHGKU2

Т.е. по сути, нужно построить линию уровня поверхности, соотвествующую z=s?
Пусть поверхность задана функцией f(x,y).
Если считать, что h мало, то каждый элементарный прямоугольник разбиваем диагональю на два треугольника. Для каждого элементарного треугольника вычисляются значения функции в вершинах, затем с помощью линейной интерполяции вычисляются точки на сторонах, в которых функция должна принимать заданное значение. Таких точек либо нет, либо их две. В последнем случае рисуется отрезок. (©)
Но это не самый быстрый способ, наверное

incwizitor

нужно не рисовать
а сохранить например в виде полигонов (упорядоченный набор пар чисел (x,y) - ето не пиксели . грамотно разделить на компоненты связности и потом уже работать с этими объектами.

Sanych

Более-менее стандартная идея: сначала упорядочиваешь известные значения функции по высоте (сохраняя их x,y координаты а потом снижая s от 1 до 0 составляешь линии раздела между классами точек, которые ещё ниже и уже выше s. Для ускорения нужно запоминать от шага к шагу что-нибудь полезное, например хранить претендентов на приграничные точки - соседей уже пройденных точек, которые пока ещё ниже s. Тогда достаточно анализировать окрестность их+соседей того отрезка значений, что вылез выше s.
По-поводу "самое интересное": уметь разбивать на компоненты связности это не проблема, если сразу запоминать соседей; займёт времени не больше, чем сохранить контур. Обычное покомпонентное вычеркивание - это всего лишь O(размер результата).

incwizitor

совершенно не понял задачу ;(
Оставить комментарий
Имя или ник:
Комментарий: