• На форуме с 18 января 2008г.
  • Сообщений: 12
  • Спасибо: 0

Тема: Находится ли точка внутри треугольника?

Имеем координаты вершин треугольника и координаты точки(разумеется в плоскости). Надо придумать алгоритм функции, которая определила бы находтся эта точка внутри треугольника или нет.
Могу предложить один способ:
1. Берем одну вершину треугольника и рисуем прямую, проходящую через нее и точку, если расстояние между вершиной и точкой менее расстояния между вершиной и точкой пересечения противолежащей к ней стороне треугольника и построенной прямой, переходим  к пункту 2,(если точка дальше от вершины, чем точка пересечения противолежащей  к вершине стороны и построенной прямой, то точка заведомо лежит вне этого треугольника).
2. Повторяем эту операцию и для остальных вершин этого треугольника.
Этот способ можно применить и для любого другого выпуклого многоугольника, слегка модифицировав его.
Всем этот способ хорош, только один недостаток есть: Очень много пассчетов, и как следствие - очень долго выполняются программы, особенно, где таких треугольников очень много...
Заранее спасибо, Николай.

  • Откуда: Москва
  • На форуме с 2 июля 2004г.
  • Сообщений: 2,538
  • Спасибо: 10

Re: Находится ли точка внутри треугольника?

> Николай
Именно для треугольников, есть огромное количество алгоритмов...
Когда, передо мной стояла такая задача - проверка нахождения точки внутри треугольника, при условии, что все точки лежат на одной плоскости, хотя она не обязательно совпадает с ХУ, но заданы точки в единой системе координат.
Я использовал функцию вычисления площади треугольника, написанную по формуле Герона (не зависит то плоскости и не надо преобразовывать точки). Алгоритм простой - вычисляем площадь исходного треугольника и сумму площадей треугольников, образованных проверяемой точкой и каждой из сторон исходного треугольника, если они совпадают до нужного знака, значит точка внутри треугольника или на одной из его сторон, иначе вовне...

  • На форуме с 18 января 2008г.
  • Сообщений: 12
  • Спасибо: 0

Re: Находится ли точка внутри треугольника?

Спасибо, Евгений! Ваше решение, красивей предложенного. Хотя на перввый взгляд оно то-же требует большого количества расчетов и выигрыш, наверное большим не будет, но решение обладает еще и универсальностью(можно проверить находится ли точка в плоскости треугольника). Если не найду решения ЗНАЧИТЕЛЬНО сокращающего рассчеты буду использовать Ваше: понравилось.
СПАСИБО.

  • Откуда: Москва
  • На форуме с 2 июля 2004г.
  • Сообщений: 2,538
  • Спасибо: 10

Re: Находится ли точка внутри треугольника?

> Николай
Рад, что смог помочь...
Есть еще один способ, отлично подходит для треугольников в 2D.
Вычисляешь направления обхода вершин в треугольнике, а потом сравниваешь с направлением в каждом из треугольников, образованных точкой и сторонами треугольника.
Если направление обхода исходного треугольника, равно направлению всех трех полученных треугольников, значит точка внутри.
Немного пояснений:
По сути, это тот же алгоритм, но вычисление направления делаем по формуле нахождения площади, путем сложения,

(+ (* (+ x1 x2)(- y1 y2) 0.5)(* (+ x2 x3)(- y2 y3) 0.5) .... )

Формула подходит для любых многоугольников, не имеющих самопересечений. При обходе по часовой стрелке, площадь положительная.
Этот метод, позволяет в некоторых случаях уменьшить количество вычислений, те. если при вычислении мы получили площадь равную нулю или отрицательную, значит уже нет смысла продолжать вычисления. К тому же, мы не вычисляем длины сегментов, перед вычислением площадей...
PS.  Второй способ, я с успехом применял, при построении полигонов Тиссона (диаграммы Вороного).

  • На форуме с 18 января 2008г.
  • Сообщений: 12
  • Спасибо: 0

Re: Находится ли точка внутри треугольника?

Спасибо и за второй пример.
Думаю, что он будет быстр, так как не требует вычисления сложных функций например: квадратный корень используется только сложение, умножение и сравнение.
Я нашел еще очень интересный ресурс, связанный с этой темой: http://faqs.org.ru/science/geometry_faq.htm.
Думаю он очень интересен.

  • Откуда: Москва
  • На форуме с 2 июля 2004г.
  • Сообщений: 2,538
  • Спасибо: 10

Re: Находится ли точка внутри треугольника?

> Николай
Специально для тебя, нашел очень интересную работу - несколько лет назад, она мне очень помогла!
Ссылка на pdf
http://www.srcc.msu.su/num-meth/zhurnal … art1_2.pdf
ссылка на страницу, где лежит
114.     Обзор алгоритмов построения триангуляции Делоне
http://www.scholar.ru/catalog.php?page= … opic_id=65

  • На форуме с 18 января 2008г.
  • Сообщений: 12
  • Спасибо: 0

Re: Находится ли точка внутри треугольника?

Евгений, Спасибо!
Задачу свою я уже решил. Я проектировщик, использующий AutoCAD как инструмент, у меня на руках горящий проект, как всегда. Когда с смогу заняться более подробным изучением этой проблеммы я не знаю.......
В любом случае ОГРОМНОЕ СПАСИБО за помощь.