Дано: у нас есть треугольник, нам известны только координаты его вершин. У нас есть точка, нам известны её координаты.
Что нужно узнать: нужно установить принадлежность точки треугольнику.
В данной статье разбирается несколько разных методов определения принадлежности точки треугольнику.
Быстро поискал в гугле — наиболее часто используют метод номер два. Третий метод также известен в интернете :)
ОтветитьУдалитьА так - спасибо, очень полезно :)
Не сомневаюсь)
УдалитьДля меня они все изначально уже были в геометрии, так что ничего нового)
По скромной статистике, которую я заметил, в порядке убывания популярности методы идут так: 2-й, 4-й, 1-й и хорошо поискав тоже нашёл 3-й в репликах народа на форумах.
когда-то давно я программировал игру "точки", так вот для нахождения "замкнули ли точку противника" использовал пересечения луча с многоугольником (осложнялось все тем, что нельзя пускать луч горизонтально, как у тебя в примере). в общем, тормозило все безбожно, но работало!)) не знал, что так много широкоиспользуемых методов! спасибо!
Удалитьтвоя идея - очень крутая! здорово, что у тебя так мощно идея движется!
ОтветитьУдалитьвнесу свои пять копеек - площадь в первом способе лучше находить векторным произведением, операций чуть меньше будет... а если вспомнить, что векторное произведение дает вектор и применить правило буравчика, то, придем к 7+7+7+3=24 операциям, причем без деления (обычно деление за 3 сложения считают).
очень здоровское сообщение у тебя вышло, побольше бы таких! тема простая, а читать интересно и живо! отлично!
Полезное замечание про площади!
УдалитьОбязательно дополню статью в скором времени)
Полезные вещи пишешь, молодец.
ОтветитьУдалитьБлагодарю за статью, но хотелось бы чуть больше математики в Векторном методе. А то когда увидишь голые формулы, вериться с трудом. (И одинаковых обозначений =^_^=)
ОтветитьУдалитьПоскольку математики не было, пришлось доходить самому. Поправьте, если я не прав:
9 m := (Xc*Ya - Xa*Yc) / (Xb*Ya - Xa*Yb); //Отношение 2 косых произведений векторов
Рассмотрим косое (псевдоскалярное) произведение (http://ru.wikipedia.org/wiki/Псевдоскалярное_произведение). Считается оно по формуле:
p ^ a = (p.x * a.y) - (a.x * p.y) // либо |p||a|*sin (alpha)
Это ориентированная площадь, где угол считается против часовой стрелки от p к a.
Вспомним знаки синуса, в первых 2 квадрантах(от 0 до Pi) - плюсы, в 3 и 4(под осью х) - минус.
Вернемся к строке 9. Получается, что здесь мы сравниваем 2 ориентированные площади: "большого" и "малого" треугольников, относительно одной из сторон большого.
Они должны иметь один знак, то есть относительно вектора a, вектор p и вектор b лежат с одной стороны.
Теперь о модуле величины косого произведения. Оно равно площади параллелограмма, натянутого на вектора. Параллелограмм - 2 треугольника (это для тех, кто запамятовал). Отсюда получаем что сумма m и l должна быть меньше единицы.
Фактически, l считать можно как (p^b) / (a^b). Но тут подставили в другое выражение.
Надеюсь, что я несильно наврал в этом пояснение.
Для меня тут геометрия на первом месте, а математика - это лишь метод решения(путь от одного значения к другому). Я просто смотрю на картинку и вижу решение. Нужно точку P представить как противоположную вершине A вершину параллелограмма 2 стороны которого лежат на сторонах треугольника. А потом визуально таскать вершину P, наблюдая за изменениями сторон параллелограмма. И когда ты вытаскиваешь вершину P за стороны данного треугольника(таким образом мы и можем выражать их через стороны треугольника), то визуально начинают пониматься условия, которые я так и вывел.
УдалитьТ.е. моё решение - это визуальное мышление + логика. А математика и формулы рождаются уже в процессе описания данного решения цифрами.
Я уже не помню точный путь решения и преобразования формул(это надо сесть и по новой написать), но точно могу сказать что я не задумывался в этой задаче о знаках в квадрантах. Т.к. будь точка P с другой стороны вне треугольника, то от отрицательности знаков просто не выполниться условие системы.
Тут суть в том, что надо выразить стороны парал. с точкой P через стороны треугольника. А потом смотреть на вхождение полученных множителей L и M в поставленные условия.
Векторный метод - это в действительности метод с использованием Барицентрических координат, и является довольно известным в определенных кругах.
ОтветитьУдалитьВот тут есть код по этому поводу, только не на Делфи: http://www.gamedev.ru/code/forum/?id=17046
Если я не ошибаюсь, кажется в первом методе расчета ошибка.
ОтветитьУдалитьВ формуле Герона забыли поделить на 2 :
Result := abs(ax2*ay3 - ax3*ay2 - ax1*ay3 + ax3*ay1 + ax1*ay2 - ax2*ay1) / 2;