Задача.

Треугольник  и точка. Лежит ли точка  [latex] M \left( x_{m}, y_{m} \right) [/latex]  внутри треугольника, заданного координатами своих вершин  [latex] \left( x_{A}, y_{A} \right) [/latex],   [latex] \left( x_{A}, y_{A} \right) [/latex],   [latex] \left( x_{A}, y_{A} \right) [/latex].

Комментарий.

Предполагаем, что треугольник невырожденный, т.е. точки  [latex] A [/latex], [latex] B [/latex]  и  [latex] C [/latex]  не лежат на одной прямой.

Слово «внутри» будем понимать следующим образом: точка «лежит внутри треугольника», если она принадлежит внутренности (в топологическом смысле) этого треугольника. Как следствие, если точка лежит на одной из сторон треугольника, внутри треугольника она НЕ лежит.

Тесты.

Рассмотрим четыре основных типа треугольников:

• ровно одна сторона параллельна оси абсцисс;
• ровно одна сторона параллельна оси ординат;
• две стороны параллельны координатным осям;
• ни одна из сторон не параллельна ни к одной из осей.

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

По моим подсчётам есть 96 вариантов расположения треугольника и точки, с учётом параллельности/непараллельности сторон осям, расположения вершин по координатным четвертям и принадлежности/непринадлежности точки внутренности треугольника. Поэтому хочется верить, что выбранные тестовые примеры достаточно показательные.

Код.

Ideone (C++)

Код (Java)

Ideone (Java)

Решение.

1.  Составим уравнения сторон треугольника. Как известно, в эвклидовой геометрии в прямоугольных декартовых координатах уравнение прямой, проходящей через две (различные!) точки  [latex] \left( r1, r2 \right) [/latex]  и  [latex] \left( s1, s2 \right) [/latex]  есть  [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) = 0[/latex] . Эта прямая разбивает плоскость на три части: собственно прямую и две открытые полуплоскости, задаваемые неравенствами  [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) < 0[/latex]  и  [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) > 0[/latex].
2. Как известно, точка лежит внутри невырожденного треугольника, если и только если она лежит с каждой вершиной этого треугольника в одной полуплоскости относительно стороны, противоположной этой вершине.
3. Из  1.  заключаем, что точки с декартовыми координатами  [latex] \left( x,y \right)[/latex]  и  [latex] \left( u,v \right)[/latex]  лежат по одну сторону от прямой, проходящей через точки  [latex] \left( r1,r2 \right)[/latex]  и  [latex] \left( s1,s2 \right)[/latex], если и только если числа  [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right)[/latex]  и   [latex] \left(v — r2 \right) \left( s1 — r1 \right) — \left( u- r1 \right) \left( s2 — r2 \right)[/latex]   отличны от нуля и одного знака, т.е. если произведение этих чисел  —  строго положительное число.
4. Проверяем условие из пункта  3.  для вершины  [latex] C [/latex]  и стороны  [latex] AB [/latex]. Если условие выполнено, переходим к пункту  5. В противном случае точка внутри треугольника не лежит.
5. Проверяем  условие из пункта  3.  для вершины  [latex] B [/latex]  и стороны  [latex] AC [/latex]. Если условие выполнено, переходим к пункту  5. В противном случае точка внутри треугольника не лежит.
6. Проверяем  условие из пункта  3.  для вершины  [latex] A [/latex]  и стороны  [latex] BC [/latex]. Если условие выполнено, точка лежит внутри треугольника. В противном случае точка внутри треугольника не лежит.

Related Images: