Принадлежность точки кривой

[kibsoft]

Существует массив контрольных точек кривой, нарисованной пользователем(рисование карандашом, как в paint и т.д.). Как можно определить, принадлежит ли конкретная точка этой кривой? Проблема в том, что кривая может иметь разную толщину. Это нужно для выделения кривой, когда пользователь кликнул по ней. Поэтому нужна довольно быстрая проверка.

[voral]

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

Если объектов/линий может быть много и пересекаются. Надо такой массив на каждую "линию".

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



А по цвету в вашей задаче не вариант?

[kibsoft]

Нет, цвет тоже разный может быть. Решил попробовать использовать QPainterPath в качестве backend'а. А вообще рисование происходит на QML Canvas.

[Igors]

Полагается что "аналитика кривой" неизвестна.

Разбить кривую на отрезки, искать минимальное расстояние от точки до отрезка и сравнивать его с какой-то дельтой.

Оптимизация - сортируем точки по Х и с помощью lower_bound находим точку A - ближайшую к мыше. Находим расстоянме до отрезка с точкой A. Дальше просматриваем сортированный массив вперед и назад от точки A пока расстояние по X не превысит найденное.

[kibsoft]

Igors, как я понял, тут не учитывается толщина линии?

[Igors]

как я понял, тут не учитывается толщина линии?

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