Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.
Тесты
В тестах нужно обязательно отразить следующие случаи:
- Точка строго вне треугольника
- Точка строго внутри треугольника
- Точка совпадает с одной из вершин треугольника
- Точка лежит на одной из сторон треугольника
- Точка лежит на продолжении одной из сторон треугольника
- Одна из сторон треугольника параллельна одной из осей координат
- Две стороны треугольника параллельны осям координат
| xa | ya | xb | yb | xc | yc | xd | yd | Принадлежит? |
|---|---|---|---|---|---|---|---|---|
| -1 | -1 | 1 | -1 | 0 | 1 | 2 | 2 | нет |
| -2 | -2 | 1 | -1 | 0 | 1 | 0 | 0 | да |
| -1 | -1 | 1 | -1 | 0 | 1 | 0 | 1 | да |
| -1 | -1 | 1 | -1 | 0 | 1 | 0.5 | 0 | да |
| -1 | -1 | 1 | -1 | 0 | 1 | 1 | 3 | нет |
| -1 | -1 | 1 | -1 | 0 | 1 | 0 | 0 | да |
| 0 | 0 | 2 | 0 | 0 | 2 | 1 | 1 | да |
| 0 | 0 | 2 | 0 | 0 | 2 | 5 | 5 | нет |
Плохое решение
В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.
Неплохое решение
Начнём с простого наблюдения:
Все точки треугольника (и любого выпуклого многоугольника) должны лежать по одну сторону от прямой, проходящей через каждую его сторону.
Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.
Неважно как называть стороны, важно научиться их различать.
Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].
Обратите внимание, что мы не утверждаем, что для любой точки на прямой наши приближённые вычисления обязаны дать точный ноль. Это было бы неверно. Мы только утверждаем, что если проведенные с доступной нам точностью вычисления всё же дали точный ноль, то мы вынуждены считать данную точку лежащей на данной прямой.
Естественно, что нам придётся записать аналогичные условия для двух оставшихся сторон треугольника (или для всех оставшихся сторон выпуклого многоугольника).
Плохой код
Начнём с того, что объявим переменные и прочитаем их значения. После этого запишем одно очень громоздкое условие, которое и проверяет принадлежность.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <stdio.h> int main() { double xa, ya, xb, yb, xc, yc, xd, yd; scanf ("%lf%lf", &xa, &ya); // читаем координаты точки A scanf ("%lf%lf", &xb, &yb); // читаем координаты точки D scanf ("%lf%lf", &xc, &yc); // читаем координаты точки C scanf ("%lf%lf", &xd, &yd); // читаем координаты точки D printf ( (((xd - xa)*(yb-ya)-(yd-ya)*(xb-xa))*((xc - xa)*(yb-ya)-(yc-ya)*(xb-xa)) >= 0) && (((xd - xb)*(yc-yb)-(yd-yb)*(xc-xb))*((xa - xb)*(yc-yb)-(ya-yb)*(xc-xb)) >= 0) && (((xd - xc)*(ya-yc)-(yd-yc)*(xa-xc))*((xb - xc)*(ya-yc)-(yb-yc)*(xa-xc)) >= 0 )? "yes": "no"); return 0; } |
Нажмите здесь, чтобы выполнить этот код.
Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.
Неплохой код
Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <stdio.h> // Вычисляет положение точки D(xd,yd) относительно прямой AB double g(double xa, double ya, double xb, double yb, double xd, double yd) { return (xd - xa) * (yb - ya) - (yd - ya) * (xb - xa); } // Лежат ли точки C и D с одной стороны прямой (AB)? bool f(double xa, double ya, double xb, double yb, double xc, double yc, double xd, double yd) { return g(xa, ya, xb, yb, xc, yc) * g(xa, ya, xb, yb, xd, yd) >= 0; } int main() { double xa, ya, xb, yb, xc, yc, xd, yd; scanf("%lf%lf", &xa, &ya); // читаем координаты точки A scanf("%lf%lf", &xb, &yb); // читаем координаты точки B scanf("%lf%lf", &xc, &yc); // читаем координаты точки C scanf("%lf%lf", &xd, &yd); // читаем координаты точки D printf( f(xa,ya,xb,yb,xc,yc,xd,yd) && f(xb,yb,xc,yc,xa,ya,xd,yd) && f(xc,yc,xa,ya,xb,yb,xd,yd) ? "yes" : "no"); return 0; } |
Нажмите здесь, чтобы выполнить этот код.
Трудно сказать, стал ли код боле понятным или лаконичным. Однако можно точно сказать, что в нём отсутствуют повторяющиеся алгоритмические блоки. Все участки кода написаны строго по одному разу. Это уменьшает вероятность ошибки.
Чеширский код
Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <stdio.h> struct point { double x, y; }; // Читать координаты точки struct point get() { struct point a; scanf("%lf%lf", &a.x, &a.y); // читаем координаты точки return a; } // Вычисляет положение точки D(xd,yd) относительно прямой AB double g(struct point a, struct point b, struct point d) { return (d.x - a.x) * (b.y - a.y) - (d.y - a.y) * (b.x - a.x); } // Лежат ли точки C и D с одной стороны прямой (AB)? bool f(struct point a, struct point b, struct point c, struct point d) { return g(a, b, c) * g(a, b, d) >= 0; } int main() { struct point a = get(), b = get(), c = get(), d = get(); printf( f(a,b,c,d) && f(b,c,a,d) && f(c,a,b,d) ? "yes" : "no"); return 0; } |
Нажмите здесь, чтобы выполнить этот код.
Вы заметили как забавно увеличивается размер программы по мере того, как мы пытаемся сделать его более логичным и наглядным? Это характерно для маленьких программ. Такие дополнительные структуры становятся всё более оправданными для больших и огромных программ.
Отчёт может быть и таким