Вопрос к т.н. "технарям"

[darth_vasya]

Тупняк на меня напал. Имеется функция в виде набора значений на двумерной сетке точек, надо определить кривую, на которой она обращается в нуль. Пока делаю очевидным образом: если произведение значения функции в (x_i,y_j) на значение в одной из трёх соседних точек ({x_i,x_i+1},{y_j,y_j+1}) отрицательное, то искомая точка считается лежащей на кривой. Очевидные недостатки - то, что в зависимости от направления кривой возле неё может получаться разное количество точек (для симметричной функции получится несимметричная кривая). Чтобы было понятнее, картинко:



Соответственно, принимаются предложения о том, как бы это всё сделать, чтобы получше результат получался. Заранее спасибо за помощь :)

Comments

[free-logic.livejournal.com]

Я бы сначала выбрал какой-нибудь способ интерполяции: например, покрыл бы всю поверхность графика функции треугольниками. Затем для каждого треугольника, пересекающего плоскость xy (условия пересечения тривиальны), нашел бы отрезок, лежащий в плоскости xy. Далее полученную ломаную можно еще раз интерполировать до чего-нибудь более гладкого.
А вообще, используй какой-нибудь Матлаб. Там все это сделают за тебя :)

[darth-vasya.livejournal.com]

Очень сложно. В идеале нужно просто неким образом модифицировать мою идею, чтобы она не имела указанных недостатков. Меня вполне устроит такой результат: просто отметить точки, между которыми происходит пересечение.

С Матлабом имеются трудности: во-первых, я под линухом. Во-вторых, осваивать какие-то большие пакеты сейчас некогда, мне через месяц уже доклад на конференции делать. Мой описанный рецепт обладает тем достоинством, что его можно быстро запрограммировать на баше (!), т.к. после умножения функции на 10 в соответствующей степени ничего, кроме целочисленной арифметики, не требуется :D

[sezam_lj.livejournal.com]

Ээ.. Чего-то я не понял постановки задачи - ищется точка пересечения точечного графика с кривой или аппроксимирующая точечный график кривая?

[darth-vasya.livejournal.com]

Ищется пересечение поверхности F(x,y) с плоскостью F=0, причём значения F даны на дискретной сетке точек. Соответственно, требуется отметить точки, между которыми происходит пересечение.

[sezam_lj.livejournal.com]

Отнормируй, переведи в графический формат, и в гимпе используй фильтр "выделение краёв" %)) А если серьёзно - в той среде, на которой программируешь, операции с матрицами или массивами поддерживаются или надо всё по точкам делать?

[darth-vasya.livejournal.com]

Только чур не смеяться :) - в идеале хочется ограничиться башем (картинка сделана с помощью баша и гнуплота). Т.е. максимум - целочисленные операции с массивами.

[sezam_lj.livejournal.com]

Хмм.. Тогда чего-то лучше чем у тебя не получается. А на картинке результат странный. Вроде так должно быть:

/х от 1 до фиг знает сколько/
/y от 1 до .../
/если F(x,y)*F(x+1,y)<0 или F(x,y)*F(x,y+1)<0 или F(x,y)*F(x+1,y+1)<0 то отметить точку (х,y)/
/возврат по у/
/возврат по х/
/покажи чего нашёл/

Правда, граница сдвинута в сторону обхода будет. Можно второй обход навстречу сделать, но тогда ряд точек двойной получится.

Почему на картинке иногда по две-три точки подряд при одном пересечении - не понимаю...

[darth-vasya.livejournal.com]

Полагаю, из-за (x+1,y+1) - на самом деле по диагонали не нужно.

[mr-fake.livejournal.com]

Если просто отметить точки между которыми имеется пересечение, то можно просто сделать 4 одномерных обхода: вертикаль, горизонталь и диагональ.

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

Это первое что приходит в голову, наверняка можно быстрее и проще.

[mr-fake.livejournal.com]

Вроде бы хватит 2х обходов по вертикали и горизонтали.

[darth-vasya.livejournal.com]

Ага, вот я тоже подумал сейчас, что диагональ-то и не нужна. И отмечать не одну точку, а обе.

[sezam_lj.livejournal.com]

+1

[vinslivins.livejournal.com]

поехале бухать на велике?

[darth-vasya.livejournal.com]

арбайтн, шайсе

[vinslivins.livejournal.com]

selbst ты шайсе

[fregimus.livejournal.com]

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

Возьмем массив трехцветных точек (скажем, черных, белых и красных), вначале белый, конгруэнтный Вашей сетке, и закрасим красным цветом все точки, где функция больше нуля (либо больше или равна нулю, либо, для лучшей симметрии, больше или равна нулю если x у >= 0, в противном случае строго больше нуля). Останется «обвести» границы белого или красного (или и — тогда они будут двойной толщины).

Обвести их можно так. Вначале сканируете массив до первой границы произвольным образом. Возьмем белую клетку на границе, закрасим черным. По конфигурации ее соседей легко найти, какую клетку закрасить черным следующей, так, чтобы граница не разрывалась по вертикали или диагонали. Закрасив соседнюю клетку, повторим процесс от нее (идти надо в обе стороны; можно начать в одну, а в другую идти только если упремся в границу). Процесс остановится сам, когда мы вернемся в исходную точку. Черная граница будет непрерывной в том смысле, в каком вы определите клеточные правила закрашивания соседей.

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

Но на баше писать это, конечно — епитимья. За что Вы себя так? :-)

[darth-vasya.livejournal.com]

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

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