|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 22 Oct 2001 06:52:49
To : Ilia Kantor
Subject : 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
Привет, Илья!
21.10.01 22:27, Ilia Kantor писал:
AL>> 1) Есть кооpдинаты тpех точек тpеугольника A(x1,y2), B(x2,y2),
AL>> C(x3,y3).
AL>> есть четвеpтая точка M тоже с известными кооpдинатами x и y.
AL>> Hужно опpеделить находится ли эта точка M внутpи тpеугольника ABC.
AL>> Решил пpовеpяя pавна ли площадь тpеугольника ABC сумме площадей
AL>> тpех тpеугольников: ABM, ACM, BCM (по фоpмуле Геpона).
AL>> Есть ли более экономичный ваpиант с точки зpения вpемени вычисления ?
IK> <-- Выдеpжка из algolist.by.ru/maths/geom/isprin/poli2d.html ->
IK> Проверка принадлежности точки многоугольнику.
IK> Случай треугольника.
IK> Для треугольника существует стандартный алгоритм, который надо знать,
IK> хотя и более общий тоже годится. Это - 'классика' аналитической
IK> геометрии, и в ручных расчетах используется именно он.
Это, действительно, классика аналитической геометрии, но приведённая
программа никуда не годится.
Во-первых, она неэффективна. Много умножений, есть даже деления.
Во-вторых, если абсциссы какой-нибудь пары из точек a, b, c совпадают
(на практике, частый случай), то программа вылетит по делению на ноль.
В-третьих, если точки a, b и c лежат на одной прямой, то программа
всегда отвечает "да" независимо от расположения точки p.
Hе хотелось бы, чтобы такой ответ попал в FAQ, поэтому программу
скипаю (с извинениями) и привожу более правильную, хоть и не идеальную,
так как работа с плавающей точкой требует более аккуратного обращения.
Если координаты целочисленны и не очень велики, имеет смысл все вычисления
производить в целых числах.
/* Если направление обхода треугольника abc - по часовой стрелке,
то точка p принадлежит внутренности треугольника abc тогда и только тогда,
когда направления обхода треугольников abp, bcp и cap тоже по часовой
стрелке.
Если же направление обхода треугольника abc - против часовой стрелки,
то точка p принадлежит внутренности треугольника abc тогда и только тогда,
когда направления обхода треугольников abp, bcp и cap тоже против часовой
стрелки.
If (Sabc > 0)
return (Sabp > 0 && Sbcp > 0 && Scap > 0);
else return (Sabp < 0 && Sbcp < 0 && Scap < 0);
Где 2*Sabc = (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x) =
= (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x) =
= (c.x-b.x)*(a.y-b.y)-(c.y-b.y)*(a.x-b.x) --
удвоенная "ориентированная" площадь треугольника abc --
больше 0, если направление обхода abc по часовой стрелке,
меньше 0, если направление обхода abc против часовой стрелки,
и равна 0, если точки a, b и c лежат на одной прямой.
Кому требуется нестрогое включение, тот должен отдельно рассмотреть
случай, когда все 4 точки лежат на одной прямой (все площади нулевые).
*/
bool BelongToPoly (point a, point b, point c, point p)
{
double acx = c.x - a.x;
double acy = c.y - a.y;
double bcx = c.x - b.x;
double bcy = c.y - b.y;
double apx = p.x - a.x;
double apy = p.y - a.y;
double bpx = p.x - b.x;
double bpy = p.y - b.y;
if (acx*bcy-acy*bcx > 0)
return (apx*bpy-apy*bpx>0 && bcx*bpy-bcy*bpx>0 && apx*acy-apy*acx>0);
else return (apx*bpy-apy*bpx<0 && bcx*bpy-bcy*bpx<0 && apx*acy-apy*acx<0);
}
Такой подход годится и для любого _выпуклого_ многоугольника.
Для невыпуклых есть более другие методы. Они много раз здесь обсуждались.
С уважением, Олег Полубасов.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
