Как определить, принадлежат ли координаты одному из графиков?

Question

[WTFAYD]

Здравствуйте!

Есть программа для построения графиков. Графики представляются в виде контейнера с точками (x,y) и рисуются как ломаные кривые. Стоит задача определения графика при наведении на него указателя.

Подскажите пожалуйста в общих чертах, как такое можно реализовать? В голову приходит только банальный перебор всех значений графиков при изменении положения курсора мыши, но это неэффективно, поскольку графики могут быть больше чем на 100000 точек.

Comments

[Satangelus]

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

или попробовать посмотреть здесь: точка на кривой безье
https://dxdy.ru/topic10198.html

или попробовать покопать inkspace исходники посмотреть как решают там эту задачу.

[MaxLich]

А как задаются кривые? только точками или уравнениями?

Answer 1

[D3lphi]

Что-то я не пойму, в чем проблема? Подставляете в функцию x,y и проверяете, выполняется ли уравнение, если да - эта координата принадлежит графику функции.

y = x^2+2x-4
Точка (3, 11)
11 = 3^2+2*3-4
11 = 11
Точка (3, 11) принадлежит графику функции y = x^2+2x-4.

Comments

[WTFAYD]

Проблема в том, что графики задаются не по функциям, а просто набором точек (x,y).

[D3lphi]

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

[napa3um]

WTFAYD, проблема, значит, в том, чтобы предварительно по набору точек нужно подобрать (аппроксимировать) какую-нибудь функцию, которая могла бы их описывать. Существует множество методов для разных случаев.

[Roman]

Проблема в том, что такое ломанная кривая?
Если у Вас ломаная, то найти принадлежность точки отрезку, постоянному по координатам двух точек. Если кривая, то должна быть какая то функция.
Или у Вас ломаная кривая спроса https://ru.m.wikipedia.org/wiki/Ломаная_кривая_спроса ?

[MaxLich]

Возможно, лучше, чем тупо подряд перебирать точки, сначала их отсортировать, а потом искать двоичным поиском. Тогда скорость будет более-менее нормальная.
Если есть возможность, то лучше сразу при добавлении точек на график кидать их в красно-чёрное дерево.

[WTFAYD]

MaxLich, Да, все-таки решил проблему двоичным поиском - точки поступают уже сортированные по X, так что с этим проблемы нет.

[MaxLich]

WTFAYD, Хорошо. Если решили задачу, то опишите своё решение в отдельном ответе (и отметьте его решением).

Answer 2

[Zanak]

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