Qwt: попадание точки на курву

[vfilatov]

Привет всем!
Есть QwtPlot, на нём QwtPlotCurve. Как для заданной точки определить, попадает ли она на курву или нет? С учётом того, что курва может быть интерполирована разными способами, в зависимости от установленных свойств.

[AlekseyK]

А что за задача? Посмотри примеры Qwt, кажется там было что-то подобное. Точно есть event (или сигнал) при нажатии на линию или точку.

[vfilatov]

Да задача простая, юзер водит мышкой над графиком и когда мышка над курвой, нужно показать всплывающую подсказку. Подсказку показываю через QwtPlotPicker, там в
virtual QwtText trackerText (const QwtDoublePoint &) const
передаются координаты точки. Но как понять, принадлежит ли эта точка курве, я пока не знаю.
В примерах что-то ничего похожего не нашёл. Максимум в примере event_filter можно таскать курву, но только за точки, на основе которых она постороена, это не интересно.

[AlekseyK]

Перехватывай mouseMove над QwtPlot() там где-то есть функция что-то типа расстояния от точки до линии (curve). Когда значение скажем в пределах 3 пикселя от линии - можешь смело показывать подсказку.

[vfilatov]

Если имеется ввиду функция

Код:

QwtPlotCurve::closestPoint

то судя по доке, она возврашает индекс в массиве точек

Returns:
Index of the closest curve point, or -1 if none can be found ( f.e when the curve has no points )

а это значит, что она ищет только по точкам, на основе которых построена курва, т.е. переданных через setData. Тогда получается совершенно не то, что нужно, т.к. не учитываются точки, полученные в результате интерполяции.

[AlekseyK]

а это значит, что она ищет только по точкам, на основе которых построена курва, т.е. переданных через setData. Тогда получается совершенно не то, что нужно, т.к. не учитываются точки, полученные в результате интерполяции.

Нет, это как то, что нужно, вернее единственное, за что ты можешь зацепиться. У меня была похожая задача. Перебираешь все кривые, получаешь номер точки, вычисляешь интерполяционные точки по X позиции, смотришь какое расстояние в пикселях, если < 3, то показываешь подсказку Только так.

[vfilatov]

Перебираешь все кривые, получаешь номер точки, вычисляешь интерполяционные точки по X позиции, смотришь какое расстояние в пикселях, если < 3, то показываешь подсказку

А как именно вычислять интерполяционные точки и почему только по X позиции?
Вот пример На картике, курва построена по точкам 1, 2, 3, 4, курсор находится в позиции, где красный крест. Он точно на курве, но от контрольных точек далеко. closestPoint вернёт большое расстояние. Что ты предлагаешь делать в этой ситуации?

[vfilatov]

В общем так. Готового решения нет и быть не может, потому что курва интерполируется непосредственно перед рисованием, а значит в другие моменты времени она и не знает, какие точки ей принадлежат. Поэтому всё придётся делать ручками самому.
Для решения задачи нужно получить все отрезки, из которых она состоит, для каждого отрезка вычислить расстояние от него до заданной точки (в которой мышка), взяв мимимум по этим расстояниям, получим расстояние до курвы. Дальше уже можем делать что угодно, например, если расстояние меньше некоторого числа, то считать, что мышка над курвой.
Сначала пишем функцию вычисления расстояния между точкой p и отрезком с начальной точкой a и конечной точкой b:

Код:

double distance(const QPointF& p, const QPointF& a, const QPointF& b)
{
	const QPointF v = b - a;
	const QPointF w = p - a;

	const double c1 = v.x() * w.x() + v.y() * w.y();
	const double c2 = v.x() * v.x() + v.y() * v.y();

	const QPointF np = (c1 <= 0 ? a : c2 <= c1 ? b : a + c1 / c2 * v );

	return sqrt( (p.x() - np.x()) * (p.x() - np.x()) + (p.y() - np.y()) * (p.y() - np.y()) );
}

Далее пишем код, вычисляющий расстояние до курвы. Для примера я его поместил в MyPlotPicker::trackerText, рассматриваю случай одной курвы, для нескольких аналогично, просто пробежать в цикле по всем и найти минимальное расстояние:

Код:

virtual QwtText trackerText(const QwtDoublePoint& point) const
{
	// Берём откуда-нибудь курву
	const MyPlotCurve* curve = ...;

	// Переходим к пиксельным координатам
	const QwtScaleMap xmap = curve->plot()->canvasMap(QwtPlot::xBottom);
	const QwtScaleMap ymap = curve->plot()->canvasMap(QwtPlot::yLeft);

	const QPointF p(xmap.transform(point.x()), ymap.transform(point.y()));

	// Запихиваем контрольные точки курвы в полигон
	QPolygonF polygon;

	const QwtData& data = curve->data();

	for(std::size_t i = 0; i < data.size(); ++i) {
		polygon.push_back(QPointF(xmap.transform(data.x(i)), ymap.transform(data.y(i))));
	}

	// Учитываем случай, когда курва интерполируется не линейно
	const bool      fitted = curve->testCurveAttribute(QwtPlotCurve::Fitted);
	QwtCurveFitter* fitter = curve->curveFitter();

	if(fitted && fitter) {
		polygon = fitter->fitCurve(polygon);
	}

	// Находим расстояние до курвы как минимум расстояний до всех отрезков курвы
	double mind = std::numeric_limits<double>::max();

	if(polygon.size() > 1) {
		for(int i = 0; i < polygon.size() - 1; ++i) {
			const QPointF& a = polygon[i];
			const QPointF& b = polygon[i + 1];

			const double d = distance(p, a, b);

			if(mind > d) {
				mind = d;
			}
		}
	}

	// Показываем расстояние во всплывающей подсказке
	return QString::number(static_cast<int>(mind));
}

[AlekseyK]

Перебираешь все кривые, получаешь номер точки, вычисляешь интерполяционные точки по X позиции, смотришь какое расстояние в пикселях, если < 3, то показываешь подсказку

А как именно вычислять интерполяционные точки и почему только по X позиции?
Вот пример На картике, курва построена по точкам 1, 2, 3, 4, курсор находится в позиции, где красный крест. Он точно на курве, но от контрольных точек далеко. closestPoint вернёт большое расстояние. Что ты предлагаешь делать в этой ситуации?

Потому, что по Х: твой пример наглядно это показывает, когда линия под острым углом идёт. Все отрезки перебирать глупо и долго. Берёшь Х ближайшей точки, смотришь X мыши больше или меньше: если больше тогда Y на линии от Х(мыши) вычисляешь (интерполируешь) по ближайшей точке и следующей, если меньше - по ближайшей и предыдущей.

[vfilatov]

Все отрезки перебирать глупо и долго. Берёшь Х ближайшей точки

Ну замечательно. А как взять X ближайшей точки? Не closestPoint ли вызвать?
closestPoint точно также перебирает все точки курвы, считает расстояние до заданной и возвращает минимум. Разница только в том, что closestPoint считает расстояние между двумя точками, а я между точкой и отрезком, но это совершенно не принципиально с точки зрения производительности. Зато ты после closestPoint ещё предлагаешь делать дополнительные вычисления, каким-то образом интерполировать Y и т.д., в то время как у меня уже готов результат.
В общем если бы ты привёл работающий код своего алгоритма, можно было бы сравнить, а так...

[AlekseyK]

Ну извините, давно делал, сейчас не найду. Кстати, предложи этот код разработчику: может добавит в основную ветку - полезный же?

[vfilatov]

Кстати, предложи этот код разработчику: может добавит в основную ветку - полезный же?

Да что-то неохота
Понятно, что этот код можно оптимизировать, сортировать отрезки, искать ближайшую точку не линейно, а двоичным поиском и т.д. Но у меня и так хорошо работает, так что для себя я эту тему закрываю, тут с этим Qwt и других вопросов полно

[Igors]

Код

C++ (Qt)
qreal distance(const QVector2D & p, const QVector2D & a, const QVector2D & b)
{
 QVector2D vecAB = b - a;  
 QVector2D vecPA = a - p; 
 QVector2D vecPB = b - p; 
 double lenAB = vecAB.length();
 
// расcтояние AB слишком мало?
 if (lenAB < EPS) 
  return ((a + b) * 0.5f - p).length();
 
 vecAB /= lenAB;
 
// знаковая длина проекция вектора PA на прямую AB
 qreal dot1 = dotProduct(vecAB, vecPA); 
 
// знаковая длина проекция вектора PB на прямую AB
 qreal dot2 = dotProduct(vecAB, vecPB); 
 
// если за границами отрезка, возвращаем расстояние до ближайшей точки
 if (dot1 * dot2 > 0)
   return (fabs(dot1) < fabs(dot2)) ? vecPA.length() : vecPB.length();
 
// возвращаем длину перпендикуляра 
 return (vecPA - vecAB * dot1).length();
// можно и так, тот же результат
// return (vecPB - vecAB * dot2).length();
}