Дано:

1. массив A размера w * h, содержащий произвольную кривую (для простоты можно считать, что она никогда не пересекает себя)
2. Точка p, принадлежащая к этой кривой

Существует ли какой-нибудь более-менее стандартизированный алгоритм построения касательной к такой кривой в точке p? И имеет ли эта задача какое-либо отношение к методике kNN?

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

Заранее спасибо.

Это сообщение отредактировал(а) hisashi - 8.5.2014, 05:55

производная в точке (x0,y0)   k= dy/dx = (y1-y0)/(x1-x0) = тангенс угла наклона касательной прямой
имея точку (x0,y0) и угол наклона строим касательную.
y=k*x+b     b= y0-k*x0

Где (x1, y1) - это соседний к (x0, y0) пиксель? Тогда получается, что k может принимать всего лишь 6 значений.

так вообще то точки из которых состоит кривая хранят допустим в массиве float, а только потом это всё растеризуется на картинку и попадает уже в конкретные пиксели.
так что соседняя в массиве точка.

http://math.stackexchange.com/questions/30...nd-a-derivative
 

Это сообщение отредактировал(а) mrgloom - 8.5.2014, 10:37

Все, что у меня есть - это двухмерный массив int-ов размерности (w, h). Но по ссылке довольно таки вкусно, попробуем.

Спасибо.

Думаю, если Вам нужен "красивый" результат на экране, нужно будет учитывать характер данных. Я бы попробовал примерно так: Описывал участок кривой, состоящий из N точек какой-нибудь формулой (сплайном, скажем) и строил касательную, используя эту формулу. От характера данных зависило бы по скольким точкам строить сплайн.

Вообще говоря лучший вариант конечно аппроксимация полиномом низкой степени (те самые сплайны). Если нужна скорость и простота, тогда для любой не крайней точки, имеем двух соседей x[i-1]y[i-1] и x[i+1]y[i+1]. поскольку в действительности мы имеем ломанную, то касательная в точке x[i]y[i] определена не однозначно, но наиболее "правильный" (в сильном смысле средний) вариант провести касательную параллельно прямой, соединяющей соседние точки. Это решение опирается на следующие соображения. 
Правая касательная это прямая, являющаяся пределом секущей проходящей через данную точку и лежащую справа от  нее при стремлении правой соседней точки к данной.
Левая касательная определяется так же.
Для непрерывно дифференцируемых функций левая и правая касательные в каждой точке совпадают. В этом случае можно говорить о просто касательной. Очевидно, что левая касательная в вашем случае является прямой проходящей через точки x[i-1]y[i-1] и x[i]y[i], правая касательная - через точки x[i]y[i] и x[i+1]y[i+1]. Что будет просто касательной?
Если мы предположим, что ваш массив точек это дискретизация непрерывно дифференцируемой функции, то производная в точке x[i]y[i] может выть вычислена тремя способами:
1. Левая производная (y[i]-y[i-1])/(x[i]-x[i-1])
2. Правая производная (y[i+1]-y[i])/(x[i+1]-x[i])
3. Центральная производная (y[i+1]-y[i-1])/(x[i+1]-x[i-1])
Левая и правая производные имеют первый порядок точности аппроксимации, центральная - второй.
Таким образом, центральная производная является наиболее точной и прямая, параллельная прямой, проходящей через точки x[i-1]y[i-1] и x[i+1]y[i+1], является наилучшим приближением к касательной.

Однако это верно только в том случае, если ваш набор точек является дискретизацией непрерывно дифференцируемой функции. Если была проведена дискретизация просто непрерывной функции, то можно говорить только о левой и правой касательных. Если функция непрерывна слева, то только о левой, если функция непрерывна только справа, то о правой. Если функция в данной точке не является непрерывной ни с лева, ни справа (разрыв второго рода) то производная не определена.

Если действовать честно, то получается где-то так.