Алгоритм/принцип построения графика неявной зависимости f(x,y) = 0?

Хабралюди! Подскажите, подкиньте идей!

Нарисовать на canvas, c++, pascal и т.п. график функции y = f(x) — проще простого. Выясняем ОДЗ аргумента и с определенным шагом вычисляем y(x). Ставим точку, и так далее.

А как быть с графиком f(x,y) = 0, если y(x) не выразить? Понимаю, что в общем случае, наверное, можно решить только перебором значений по плоскости. Какие есть частные решения? Нужен что-то вроде brain-storm. Заранее спасибо!

Начну список:

  • Перебор значений по x и по y с определенным шагом. Долго, но 100% :-)

  • Нахождение зависимости y(x). Подходит только тогда, когда можно выразить.

  • Переход в полярные координаты, выражение радиуса от угла. Пробегание по углу от 0 до 2pi. Подходит не всегда, но бывает, когда y(x) выразить сложно.

  • Tupper, Jeff. «Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables» www.dgp.toronto.edu/people/mooncake/papers/SIGGRAP...

    Спасибо gribozavr. (не получилось почему-то в вопросе вставить ссылкой)

  • поиск нулей функции градиентным методом (спуском)

    Спасибо Lerq

  • Вопрос задан
  • 8589 просмотров
Решения вопроса 1
Lerg
@Lerg
Defold, Corona, Lua, GameDev
Получается что вам нужно найти пересечение поверхности z = f(x, y) с плоскостью z = 0.
Я знаю сюществуют специальные численные методы для нахождения этих контуров пересечения, нужно хорошенько в сети их поискать.
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
Akson87
@Akson87
Могу предложить немного изменить описанный выше подход с градиентами и 3хмерным описанием проблемы. Возьмите срезы по XZ для каждого Y, который соответствует пикселям на экране (надо помнить, что нам не надо расчитывать результат с точность, которая превышает разрешение монитора). Тогда каждый срез будет представлять из себя стандартную задачу по решению уравнения f(x)=0, тут уж можно какие-нибудь численные итеративные методы стандартные (метод ньютона например или что-то другое) использовать (которые по сути и используют градиенты в каком-то смысле). Проблемой с такими срезами будет то, что будут плохо отображаться горизонтальные линии. Можно попробовать последовательно делать с фиксированными Х и У, тогда должно получиться получше. Но все это мысли вслух так сказать, как бы я подходил к проблеме.
Ответ написан
Комментировать
@gribozavr
Наиболее хороший с моей точки зрения метод
Tupper, Jeff. «Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables» www.dgp.toronto.edu/people/mooncake/papers/SIGGRAPH2001_Tupper.pdf
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Можно сделать так. Если известна хотя бы одна пара соседних точек растра, на которых функция имеет разные знаки (например, f(x,y)>0, f(x+1,y)<0), то линия проходит межу ними. Можно взять один из квадратов, ограничивающих этот отрезок (например, (x,y)-(x+1,y)-(x+1,y+1)-(x,y+1) ), и, проверив знаки функции f(x+1,y+1) и f(x+1,y), узнать, какую вторую сторону квадрата пересечет график. Процесс продолжать, пока график не дойдет до границы области или не замкнется.
Для поиска стартовых точек можно взять значения в точках (Nx,Ny) при каком-нибудь N, и уже на этом растре искать соседние точки с разными знаками: график наверняка пройдет между ними. Маленькие компоненты при этом могут потеряться, но для их поиска пришлось бы использовать очень серьезные методы — например, решать систему f(x,y)=0, df(x,y)/dx=0 (ее решения дадут экстремальные точки всех компонент). Можно для этого применить метод Ньютона (тоже стартуя из всех точек (Nx,Ny)).
Ответ написан
bfDeveloper
@bfDeveloper
Есть ещё одно интересное соображение по трёхмерному решению, навеянное методом Хука-Дживса.
Пусть мы нашли одну точку нашего графика (например, рассмотрев сечение x = const и применив в нём метод Пиявского). Назовём эту точку опорной. Если предположить, что мы ищем одну непрерывную кривую, то можно утверждать, что рядом с найденной точкой есть другие, принадлежащие этой кривой. Возьмём некоторый шаг h и посчитаем значение функции F(x, y) в нескольких точках на расстоянии h от первой. Выберем точку со значением максимально близким к 0 за следующую опорную и повторим действия. Таким образом мы как бы пройдёмся по дну оврага (если брать модуль F) или просто по склону, сохраняя высоту.
Если хорошо подумать над тем как искать следующую точку, то можно сообразить как от начальной точки пройти сразу по двум направлениям (она же не обязательно будет на границе, и описанный выше метод найдёт кривую только по одну сторону от точки).
Получив массив точек, мы можем применить метод градиентного спуска для каждой из них для получения более точного результата. Так как точки уже близки к кривой, практически исключается возможность скатывания в локальные минимумы.
Вообще в методах глобальной оптимизации принято сначала локализовывать точки минимума, а потом запускать методы локальной оптимизации в найденных областях. Здесь это тоже неплохо работает.
Ответ написан
Комментировать
limon_spb
@limon_spb Автор вопроса
Спасибо всем за ответы! Жаль, как решение, можно только один пост поставить!
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы