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

Общие вопросы программирования, алгоритмы и т.п.

Модератор: Модераторы

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

Сообщение vulturedroid » 19.12.2017 18:50:41

Есть уравнение (x-x1)/(x2-x1)=(y-y1)/(y2-y1) , можно с помощью него проверить, лежит ли точка на отрезке. Но как его надо изменить, чтобы работало при различной толщине отрезка?
vulturedroid
незнакомец
 
Сообщения: 2
Зарегистрирован: 24.11.2017 07:32:38

Re: Проверить, лежит ли точка на отрезке с толщиной

Сообщение tema » 19.12.2017 20:35:35

Теорема Пифагора :-)
tema
постоялец
 
Сообщения: 375
Зарегистрирован: 24.03.2011 20:19:27

Re: Проверить, лежит ли точка на отрезке с толщиной

Сообщение Pavia » 19.12.2017 21:20:58

(The AP Professional graphics CD-ROM) Andrew S. Glassner-Graphics Gems. Volume 1-AP Professional (1995)

Алгоритм 49 страница, а математика на 47-48 страницах.
Аватара пользователя
Pavia
постоялец
 
Сообщения: 290
Зарегистрирован: 07.01.2011 12:46:51

Re: Проверить, лежит ли точка на отрезке с толщиной

Сообщение Дож » 19.12.2017 23:43:11

Вектор N=(y2-y1,x1-x2) перпендикулярен к прямой.

Если его скалярно умножить на любую точку на прямой, например, на (x1,y1), то получится "расстояние" от (0,0) до прямой вдоль N:
D = x1*(y2-y1) + y1*(x1-x2)

Возьмём тестируемую точку (X,Y), мы легко можем посчитать "расстояние" от неё до прямой, умножив скалярно на N и вычтя D:
X*(y2-y1) + Y*(x1-x2) - D

Остаются мелочи: поделить результат на длину вектора N, взять модуль и сравнить с толщиной [поделённой на два].
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

Re: Проверить, лежит ли точка на отрезке с толщиной

Сообщение vitaly_l » 20.12.2017 10:39:45

vulturedroid писал(а):как его надо изменить

Его ненужно менять, его можно запустить несколько раз подряд (в соответствии с толщиной линии) или проверять на вхождение точки в прямоугольник.


Добавлено спустя 1 час 11 минут 111 секунд:
Дож писал(а):легко можем посчитать "расстояние" от неё до прямой

А как быть, если отрезок например параллелен оси координат и точка на одной линии, совсем рядом с концом отрезка? Точка находится очень близко, но она не на линии. И ширина линии - задана больше расстояния между точкой и концом отрезка. Расстояние до линии будет попадать в предложенный алгоритм, но в реальности, точка-то - не будет на отрезке.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Проверить, лежит ли точка на отрезке с толщиной

Сообщение vada » 20.12.2017 12:04:42

А еще если отрезок растровый. А еще если его концы закруглены. А еще точка рядом с концом отрезка.
Тут непочатый край исследований!
:lol:
Аватара пользователя
vada
энтузиаст
 
Сообщения: 691
Зарегистрирован: 14.02.2006 13:43:17

Re: Проверить, лежит ли точка на отрезке с толщиной

Сообщение tema » 21.12.2017 01:18:19

vitaly_l писал(а):
Дож писал(а):легко можем посчитать "расстояние" от неё до прямой

А как быть, если отрезок например параллелен оси координат и точка на одной линии, совсем рядом с концом отрезка? Точка находится очень близко, но она не на линии. И ширина линии - задана больше расстояния между точкой и концом отрезка. Расстояние до линии будет попадать в предложенный алгоритм, но в реальности, точка-то - не будет на отрезке.

В этом случае каноническое уравнение прямой не канает. Надо это просто учитывать и все дела. Можно переводом в обычное уравнение.
tema
постоялец
 
Сообщения: 375
Зарегистрирован: 24.03.2011 20:19:27



Вернуться в Общее

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17

Рейтинг@Mail.ru