6. Условия непересечения многоугольников

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

Рис. 44.

Параметры размещения обозначим соответственно. На рис. 44 показаны различные случаи размещения отрезков. Отрезок лежит на прямой отрезок на прямой II. Очевидно, для пересечения, отрезков необходимо и достаточно, чтобы точки лежали по разные стороны прямой а точки

по разные стороны прямой Уравнения прямых I и II можно написать в виде

Функция имеет разные знаки по разные стороны от прямой а функция разные знаки по разные стороны от прямой II. Координаты концов отрезков соответственно:

Тогда для того, чтобы отрезки не пересекались, необходимо и достаточно, чтобы выполнялось по крайней мере одно из неравенств.

Неравенство (6.49) выполняется, если отрезок лежит по одну из сторон от прямой а неравенство (6.50) — если отрезок находится по одну из сторон от прямой Неравенства (6.49) и (6.50) можно заменить одним неравенством

Для записи условий непересечения отрезков примем обозначение как стандартное.

Используя неравенство (6.51) и результаты, полученные в гл. 6, 4, можно записать условия непересечения

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

Пример 1. Напишем условие непересечения квадратных выкроек со сторонами соответственно.

Поместим полюсы выкроек в центры квадратов, а оси подвижных систем координат направим параллельно сторонам соответствующих квадратов (рис. 45).

Рис. 45.

Условие непересечения выкроек равносильно условию непересечения контура меньшего квадрата с контуром большего квадрата, к которому присоединены диагонали

Выпишем параметры размещения сторон меньшего квадрата. Сторона АВ:

сторона

сторона

сторона

Параметры размещения сторон и диагоналей большего квадрата. Сторона

сторона

сторона

сторона

диагональ

диагональ

Тогда условие непересеченйя выкроек и запишется так:

Решение задачи о взаимном непересечении многоугольных выкроек может быть использовано для произвольных выкроек, контуры которых с заданной точностью можно аппроксимировать ломаными линиями. Однако при этом необходимо учитывать, что число звеньев в этих ломаных не может быть слишком большим, так как задачи оптимального раскроя приходится решать на реальных ЭЦВМ, имеющих ограниченную память и ограниченное быстродействие.