Затруднения Наш алгоритм определения пересечения двух выпуклых полигонов очеш чувствителен к ошибкам округления, когда два полигона пересекаются i точке, являющейся вершиной одного или обоих полигонов. Одна из проблем заключается в том, что такая точка может быть пропущена. В одном ш случаев на рис.3 ребра р и q пересекаются в точке х, являющейся ко нечной концевой точкой ребра р. При использовании точной арифметики параметрическое значение х вдоль отрезка р равно единице. Однако в арифметике с плавающей точкой фактически вычисленное значение может не сколько превышать единицу, что соотвотствует положению точки х после конца ребра р и такая точка может оказаться необнаруженной. С целью обойти подобное затруднение при вычислении точки пересеченш двух ребер в программе convexPolygonlntersect применяется функцш crossingPoint. Для заданных двух ребер e и f функция сначала вычисляет точку, в которой пересекаются бесконечные прямые линии, определяемые ребрами e и f. Если эта точка оказывается в непосредственной близости одного из четырех концов упомянутых ребер, то в качестве точки пересе чения берется ближайшая концевая точка. В силу особенностей применении функция работает с параметрическими значениями, а не с самими точками. Путем расширения диапазона параметрических значений вдоль ребра f ребро фактически удлиняется на величину EPSILON2 в обоих направлениях. Если точка пересечения при вычислении находится в пределах EPSILON2 от одной из концевых точек ребра f, то точка пересечения принудительно "привязывается" к этой концевой точке. То же самое правило применяет и к ребру е. Функция crossingPoint возвращает одно из значений COLLINEAR, PARALLEL, SKEW_NO_CROSS или SKEW_CROSS (коллинеарны, параллельны, не пересекаются, пересекаются), показывающее взаимное положение ребер е и f. Если возвращается значение SKEW_CROSS, показывающее, что ребра имеют точку пересечения, то эта точка пересечения возвращается через ссылочный параметр р: #define EPSILON2 1E-10 int crossingPoint(Edge &e, Edge &f, Point &p) { double a, t; int classe = e.intersect(f, s); if ((classe == COLLINEAR) || (classe == PARALLEL)) return classe; double lene = (e.dest-e.org).length(); if ((s < -EPSILON2*lene) (((s > 1.0+EPSILON2*lene)) return SKEW_NO_CROSS; f.intersect(e, t); double lenf = (f.org-f.dest).length(); if ((-EPSILON2+lenf <= t) && (t <= 1.0+EPSILON2*lenf)) { if (t <= EPSILON2*lenf) p = f.org; else if (t >= 1.0-EPSZLON2*lenf) p = f.dest; else if (s <= EPSILON2*lene) p = e.org; else if (a >= 1.0-EPSILON2*lene) p = e.dest; else p = f.point(t); return SKEW_CROSS; } else return SKEW_NO_CROSS; } Если в качестве основы для вычисления точек пересечения брать функцию crossingPoint, то наша программа определения пересечения выпуклых полигонов будет устойчиво работать даже тогда, когда полигоны пересекаются в вершинах. Но заметим, что наша программа может дать ошибку, если вершины одного из полигонов располагаются очень близко (в пределах EPSILON2) от границ другого полигона, но практически не касаясь границы. <<<  Назад  1  2  3   8  Комментарии к статье  8 8  Обсудить в чате