Как найти ближайшие 2 точки QPointF к позиции курсора на карте?
У меня есть многоугольник, когда я навожу курсор мыши на этот многоугольник, то я пытаюсь найти ближайшие две координаты к этой позиции мыши. Все вершины многоугольника у меня хранятся в векторе
QVector<QPointF> points;
Также сам курсор мыши у меня есть как QPointF. Сейчас я пытаюсь найти ближайшие точки к этой позиции, но не совсем понимаю как сделать это корректно и оптимально.
P.s. под ближайшими точками я подразумеваю именно 2 точки, которые в пересечении с позицией курсора мыши будут образовывать треугольник.
Ответы (1 шт):
Автор решения: Arty
→ Ссылка
Как понимаю ближайшая точка означает, с наименьшим евклидовым расстоянием.
Привожу здесь вариант алгоритма с соседнего поста только для случая евклидового расстояния до заданной точки (координаты мыши).
QPointF mouse; // Fill-in with mouse coordinates.
auto SqrDist = [](QPointF const & a, QPointF const & b) {
return (a.x() - b.x()) * (a.x() - b.x()) + (a.y() - b.y()) * (a.y() - b.y());
};
size_t min0i = 0, min1i = 1;
auto min0d = SqrDist(mouse, points.at(0)), min1d = SqrDist(mouse, points.at(1));
if (min0d > min1d) {
std::swap(min0i, min1i); // #include <algorithm>
std::swap(min0d, min1d);
}
for (size_t i = 2; i < points.size(); ++i) {
auto d = SqrDist(mouse, points.at(i));
if (d < min0d) {
min1i = min0i; min0i = i;
min1d = min0d; min0d = d;
} else if (d < min1d) {
min1i = i; min1d = d;
}
}
QPointF point_min0 = points.at(min0i), point_min1 = points.at(min1i);