Алгоритм определения - точка вдоль линии ИЛИ довольно близко - PullRequest
Новая
       21

Алгоритм определения - точка вдоль линии ИЛИ довольно близко

1 голос
/ 11 декабря 2011

Хорошо, у меня есть приложение, которое использует систему отображения для рисования линий. Каждая строка A, B определяется в формате широта / долгота. Когда пользователь щелкает карту, все, что мне дается, это отдельная точка C, где пользователь щелкает в формате широта / долгота. Я хочу дать пользователю возможность выбирать линии на карте, нажав. Проблема в том, что из-за изменяющихся уровней масштабирования пользователю очень трудно щелкнуть точно вдоль линии. Лучшее, на что я могу надеяться, это то, что они нажимают в пределах некоторого порогового расстояния, которое я определяю. Как я могу выяснить, что пользователь нажал или обоснованно приблизился к строке, содержащей только эту информацию?

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

То, что я до сих пор придумал, это сначала проверить расстояние AC и BC. Если какое-либо расстояние больше, чем AB, то пользователь не щелкнул по линии. Если он пройдет эту проверку, то я рассчитываю углы CAB и CBA. Если C находится точно на линии, то оба угла должны быть равны 0, я думаю, мой триг немного ржавый. В противном случае, чтобы определить, достаточно ли близок C, я выберу наименьший из двух рассчитанных углов и посмотрю, не падает ли он ниже некоторого предопределенного порога.

Я на правильном пути или далеко? Есть идеи получше?

1 Ответ

6 голосов
/ 11 декабря 2011

Вы также можете напрямую рассчитать расстояние от вашей точки до любой линии.В статье Википедии приведены подробности, а также некоторый (псевдо) код.

В вашем случае вы также должны учитывать конечные точки отдельно.Т.е. сначала вы должны рассчитать параметр t (см. Статью выше) и проверить, находится ли он в диапазоне от 0 до длины AB.Тогда, если дополнительно расстояние лежит ниже предварительно определенной суммы, тогда пользователь нажимает на строку, в противном случае нет.

Формулы в вашем случае выглядят следующим образом: 

(C - (A + t * (B-A))) * (B-A) = 0

=> t = (C.x - A.x) * (B.x - A.x) + (C.y - A.y) * (B.y - A.y) / ((B.x - A.X) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y))

If t ниже 0 или выше 1 пользователь не щелкнул по строке.В противном случае (т. Е. t находится между нулем и единицей), вы можете рассчитать расстояние d, используя это значение t: 

d = dist(C, A+t*(B-A)) = sqrt( (C.x - A.x - t * (B.x - A.x))^2 + (C.y - A.y - t * (B.y - A.y))^2)

Если d ниже некоторого предварительно определенного порога, вы можете принятьчто пользователь нажал на вашу строку.

...