Отсечение выпуклым многоугольником

Алгоритм средней точки (midpoint) (авторы те же)

Случаи, в которых отрезок лежит целиком снаружи или внутри отсекаемой области выявим изложенным в п.2 методом.

В общем случае возьмем среднюю точку нашего отрезка AB (обозначим ее C₁) и применим к отрезкам AC₁ и C₁B этот алгоритм рекурсивно. Следующие средние точки отрезков AC₁ и C₁B обозначим C₂ и C₃ соответственно (см. Рис. 2).

И так далее, пока размер оставшихся отрезков не станет меньше размера пиксела.

Рис. 2. Алгоритм средней точки.

В примере на Рис. 2 после второй итерации отрезок AC₂ будет отсечен, и для него дальнейшее половинное деление производиться не будет, С₁С₃ лежит целиком внутри области отсечения, он будет нарисован, и для него дальнейшее половинное деление также производиться не будет. Остальные части будем делить дальше.

Алгоритм:

Отсечение (точка A, точка B)

{

Если (длина AB меньше размера пиксела) выход;

Если (AB лежит вне отсекающего прямоугольника) выход;

Если (AB лежит внутри отсекающего прямоугольника) { Рисовать AB; выход; }

Отсечение (A, (A+B)/2)

Отсечение ((A+B)/2), B)

}

Простой алгоритм, но не очень эффективный на практике, так как требует большой глубины рекурсии.

Рис. 3. Многоугольник.

Многоугольник обычно задается списком вершин (для удобства примем соглашение, что они обходятся по часовой стрелке и нумеруются с 1).

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

Рис. 4. Отсечение выпуклым многоугольником.

Пусть наш отрезок - это AB. Перейдем к канонической системе координат Axy, в которой A=(0,0), а B=(0,l), где l - длина AB. Не будем рисовать отрезок, если он пересекается с многоугольником по его границе.

На Рис. 4 исходный отрезок - это AB, а отсеченный - CB.

Алгоритм Cyrus-Beck [Cyrus-Beck, 1978]

Для каждого ребра возможны 3 случая:

а) обе его вершины лежат выше или ниже Ax (например на Рис. 4 1-2)

б) его вершины лежат по разные стороны от Ax (например на Рис. 4 3-4)

найдем точку пересечения и запомним ее;

в) вырожденные случаи: ребро лежит на Ax или одна из его вершин лежит на Ax

Для всего многоугольника возможны 2 случая:

1) Точки пересечения отрезка и многоугольника отсутствуют либо лежат на границе:

а) все вершины лежат выше или ниже Ax;
б) одно из ребер лежит на Ax;
в) только одна вершина лежит на Ax;

ничего рисовать не надо

2) Существует непустое пересечение внутренней части многоугольника с отрезком,

при этом точек пересечения с границами ровно 2 (в силу выпуклости)

а) существует 2 точки пересечения Ax с ребрами;
б) существует 1 точка пересечения Ax с ребром и 1 точка пересечения Ax с вершиной;
в) существует 2 точки пересечения Ax с вершинами (не одного ребра).