Пересечения на плоскости

Первая функция определяет пересекаются ли точка и многоугольник. Направление обхода вершин многоугольника может быть произвольным. Для определения применяется метод луча:

bool isIntersect ( const Vector2d & p, CArrRef<Vector2d> poly );

Следующая функция определяет пересекаются ли точка и круг:

bool isIntersect ( const Vector2d & p, const Circle2d & fig );

Следующие функции находят точку пересечения прямых и отрезков, если она единственная:

Def<Vector2d> intersection ( const Line2d & line1, const Line2d & line2 );
Def<Vector2d> intersection ( const Line2d & line, const Segment2d & seg );
Def<Vector2d> intersection ( const Segment2d & s1, const Segment2d & s2 );
Функция cut отсекает заданной прямой часть отрезка находящуюся в положительной полуплоскости ( или другими словами находит пересечение отрезка с отрицательной полуплоскостью ). Если в положительной полуплоскости находятся оба конца отрезка, то функция возвращает неопределённый отрезок:
Def<Segment2d> cut ( const Line2d & line, const Segment2d & seg );

Следующие функции находят пересечения прямых и отрезков с кругом. Результатом пересечения будет отрезок, возможно неопределённый:

Def<Segment2d> intersection ( const Line2d & line, const Circle2d & cir );
Def<Segment2d> intersection ( const Segment2d & seg, const Circle2d & cir );

Следующие функции находят пересечения прямых и отрезков с эллипсом:

Def<Segment2d> intersection ( const Line2d & line, const Ellipse2d & e );
Def<Segment2d> intersection ( const Segment2d & seg, const Ellipse2d & e );

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

DynArrRef<Segment2d> & 
intersection ( const Line2d & line, CArrRef<Vector2d> poly, DynArrRef<Segment2d> & res );
SuiteRef<Segment2d> & 
intersection ( const Segment2d & seg, CArrRef<Vector2d> poly, SuiteRef<Segment2d> & res );

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

SuiteRef< Suite<Vector2d> > & 
cut ( CArrRef<Vector2d> poly, const Line2d & line, SuiteRef< Suite<Vector2d> > & res );

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

Suite< Suite<Vector2d> > & 
intersect1c ( CArrRef<Vector2d> conv, CArrRef<Vector2d> poly, Suite< Suite<Vector2d> > & res );

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

bool intersection ( CArrRef<Vector2d> poly1, CArrRef<Vector2d> poly2, Suite< Suite<Vector2d> > & res );
В случае обнаружения ошибки в ходе выполнения функция возвращает значение false.

Описание шаблонов классов CArrRef, DynArrRef, SuiteRef и Suite находится здесь.
Описание классов Segment2d, Line2d, Circle2d и Ellipse2d находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.

Примеры использования всех этих функций можно посмотреть в приложении DEMO.
Исходники алгоритмов находятся в файле intersect2d.cpp.

Наверх
Hosted by uCoz