Лекция 8. Математические задачи решаемые при разработке САПР

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

 

Рис. 1. Внутренняя область треугольника соответствует отрицательным направлениям векторов нормалей.

 

Через каждую пару вершин треугольника можно провести прямую. Замкнутая область пересечения трех полуплоскостей, образованных этими прямыми есть внутренняя область треугольника. Пользуясь вектором нормали можно записать уравнение прямой на плоскости: . Идея первого метода состоит в том, чтобы записать функциональные представления уравнений прямых, образующих стороны треугольника, таким образом, чтобы внутренняя область треугольника соответствовала, например, отрицательным значениям. Тогда условием принадлежности внутренней области треугольника будут отрицательные значения трех функциональных уравнений прямых при подстановке координат проверяемой точки. Основной проблемой в этом методе является правильный выбор направления вектора нормали к прямой.

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

Рис. 2. Точка вне треугольника.

 

Условием принадлежности точки внутренней области треугольника будет несовпадение знаков ‑ координат оставшихся двух вершин после каждого из трех поворотов.

 

Рис. 3.Точка внутри треугольника.

 

Нахождение точки на одной из сторон треугольника легко определяется по несовпадению знаков -координат двух вершин которые после одного из поворотов оказались лежащими на оси . Этот метод эффективен когда больше вероятность что точка лежит вне треугольника. Отрицательной его чертой является необходимость вычисления синусов и косинусов углов при повороте системы координат.

 

Третий из приводимых здесь методов представляется наиболее компактным и скоростным с вычислительной точки зрения. Этот метод был предложен автору Д. Чистяковым в 1999 году. Заметим, что очень просто можно определить принадлежность точки внутренней области треугольника – единичного симплекса, то есть треугольника, образованного точками с координатами , , . Для этого достаточно чтобы координаты искомой точки имели значения в отрезке и выполнялось условие , где и ‑ координаты точки. Заметим также, что с помощью аффинных преобразований на плоскости или непрерывных деформаций любой треугольник можно преобразовать к единичному симплексу.

Рис. 4. Приведение произвольного треугольника к единичному симплексу.

 

После таких преобразований внутренняя и внешняя области треугольника остаются таковыми. Применив такое преобразование к искомой точке, достаточно затем будет определить ее нахождение во внутренней или внешней области симплекса. Найдем такое преобразование. Координаты векторов единичного базиса совпадают с координатами точек и симплекса, соответственно. Будем считать, что точка треугольника совпадает с началом координат. Этого всегда можно добиться параллельным переносом треугольника на вектор . При этом координаты точек и треугольника суть коэффициенты разложения соответствующих векторов и по единичному базису. Матрица перехода от единичного базиса к базису на векторах и составлена из координат этих векторов.

Значит для обратного перехода к единичному базису, (на векторах которого построен симплекс), необходимо найти обратную матрицу:

.

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