Обрезка линии | Набор 1 (алгоритм Коэна – Сазерленда)

Опубликовано: 20 Января, 2022

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

 Входные данные: прямоугольная область интереса (определяется
        ниже четырех значений, которые являются координатами
        внизу слева и вверху справа)
        x_min = 4, y_min = 4, x_max = 10, y_max = 8
       
        Набор линий (определяется двумя угловыми координатами)
        строка 1: x1 = 5, y1 = 5, x2 = 7, y2 = 7
        Строка 2: x1 = 7, y1 = 9, x2 = 11, y2 = 4
        Строка 2: x1 = 1, y1 = 5, x2 = 4, y2 = 1 

Вывод: Строка 1: Принимается с (5, 5) по (7, 7)
         Строка 2: Принято с (7.8, 8) до (10, 5.25)
         Строка 3: отклонено

Алгоритм Коэна-Сазерленда делит двумерное пространство на 9 областей, а затем эффективно определяет линии и части линий, которые находятся внутри данной прямоугольной области.

Алгоритм можно изложить следующим образом: -

 Создаются девять регионов, восемь «внешних» регионов и один 
«внутренний» регион.

Для данной крайней точки линии (x, y) мы можем быстро
найти четырехбитный код своего региона. Четырехбитный код может 
вычисляться путем сравнения x и y с четырьмя значениями 
(x_min, x_max, y_min и y_max).

Если x меньше x_min, то устанавливается бит номер 1.
Если x больше x_max, то устанавливается бит номер 2.
Если y меньше y_min, то устанавливается бит номер 3.
Если y больше y_max, то устанавливается бит номер 4.

Для любой данной строки есть три возможных случая.

  1. Полностью внутри данного прямоугольника: Побитовое ИЛИ области двух конечных точек линии равно 0 (Обе точки находятся внутри прямоугольника)
  2. Полностью за пределами данного прямоугольника: обе конечные точки имеют как минимум одну внешнюю область, что означает, что линия не пересекает видимую область. (побитовое И конечных точек! = 0).
  3. Частично внутри окна: обе конечные точки находятся в разных регионах. В этом случае алгоритм находит одну из двух точек, находящихся за пределами прямоугольной области. Пересечение линии от внешней точки и прямоугольного окна становится новой угловой точкой, и алгоритм повторяется.

Псевдокод:

 Шаг 1: Назначьте код региона для двух конечных точек данной линии.
Шаг 2. Если обе конечные точки имеют код региона 0000 
         тогда данная линия полностью внутри.
Шаг 3: В противном случае выполните операцию логического И для обоих кодов регионов.
    Шаг 3.1: Если результат не 0000, то данная строка полностью заполнена.
               вне.
    Шаг 3.2: Остальная линия частично внутри.
        Шаг 3.2.1: Выберите конечную точку линии 
                     что находится за пределами данного прямоугольника.
        Шаг 3.2.2: Найдите точку пересечения 
                     прямоугольная граница (на основе кода региона).
        Шаг 3.2.3: Замените конечную точку точкой пересечения 
                     и обновите код региона.
        Шаг 3.2.4: Повторяйте шаг 2, пока не найдем обрезанную линию. 
                     банально принимается или банально отвергается.
Шаг 4. Повторите шаг 1 для других строк.

Below is implementation of above steps.

C++

// C++ program to implement Cohen Sutherland algorithm
// for line clipping.
#include <iostream>
using namespace std;
 
// Defining region codes
const int INSIDE = 0; // 0000
const int LEFT = 1; // 0001
const int RIGHT = 2; // 0010
const int BOTTOM = 4; // 0100
const int TOP = 8; // 1000
 
// Defining x_max, y_max and x_min, y_min for
// clipping rectangle. Since diagonal points are
// enough to define a rectangle
const int x_max = 10;
const int y_max = 8;
const int x_min = 4;
const int y_min = 4;
 
// Function to compute region code for a point(x, y)
int computeCode(double x, double y)
{
    // initialized as being inside
    int code = INSIDE;
 
    if (x < x_min) // to the left of rectangle
        code |= LEFT;
    else if (x > x_max) // to the right of rectangle
        code |= RIGHT;
    if (y < y_min) // below the rectangle
        code |= BOTTOM;
    else if (y > y_max) // above the rectangle
        code |= TOP;
 
    return code;
}
 
// Implementing Cohen-Sutherland algorithm
// Clipping a line from P1 = (x2, y2) to P2 = (x2, y2)
void cohenSutherlandClip(double x1, double y1,
                         double x2, double y2)
{
    // Compute region codes for P1, P2
    int code1 = computeCode(x1, y1);
    int code2 = computeCode(x2, y2);
 
    // Initialize line as outside the rectangular window
    bool accept = false;
 
    while (true) {
        if ((code1 == 0) && (code2 == 0)) {
            // If both endpoints lie within rectangle
            accept = true;
            break;
        }
        else if (code1 & code2) {
            // If both endpoints are outside rectangle,
            // in same region
            break;
        }
        else {
            // Some segment of line lies within the
            // rectangle
            int code_out;
            double x, y;
 
            // At least one endpoint is outside the
            // rectangle, pick it.
            if (code1 != 0)
                code_out = code1;
            else
                code_out = code2;
 
            // Find intersection point;
            // using formulas y = y1 + slope * (x - x1),
            // x = x1 + (1 / slope) * (y - y1)
            if (code_out & TOP) {
                // point is above the clip rectangle
                x = x1 + (x2 - x1) * (y_max - y1) / (y2 - y1);
                y = y_max;
            }
            else if (code_out & BOTTOM) {
                // point is below the rectangle
                x = x1 + (x2 - x1) * (y_min - y1) / (y2 - y1);
                y = y_min;
            }
            else if (code_out & RIGHT) {
                // point is to the right of rectangle
                y = y1 + (y2 - y1) * (x_max - x1) / (x2 - x1);
                x = x_max;
            }
            else if (code_out & LEFT) {
                // point is to the left of rectangle
                y = y1 + (y2 - y1) * (x_min - x1) / (x2 - x1);
                x = x_min;
            }
 
            // Now intersection point x, y is found
            // We replace point outside rectangle
            // by intersection point
            if (code_out == code1) {
                x1 = x;
                y1 = y;
                code1 = computeCode(x1, y1);
            }
            else {
                x2 = x;
                y2 = y;
                code2 = computeCode(x2, y2);
            }
        }
    }
    if (accept) {
        cout << "Line accepted from " << x1 << ", "
             << y1 << " to " << x2 << ", " << y2 << endl;
        // Here the user can add code to display the rectangle
        // along with the accepted (portion of) lines
    }
    else
        cout << "Line rejected" << endl;
}
 
// Driver code
int main()
{
    // First Line segment
    // P11 = (5, 5), P12 = (7, 7)
    cohenSutherlandClip(5, 5, 7, 7);
 
    // Second Line segment
    // P21 = (7, 9), P22 = (11, 4)
    cohenSutherlandClip(7, 9, 11, 4);
 
    // Third Line segment
    // P31 = (1, 5), P32 = (4, 1)
    cohenSutherlandClip(1, 5, 4, 1);
 
    return 0;
}

Python

# Python program to implement Cohen Sutherland algorithm
# for line clipping.
 
# Defining region codes
INSIDE = 0  # 0000
LEFT = 1    # 0001
RIGHT = 2   # 0010
BOTTOM = 4  # 0100
TOP = 8     # 1000
 
# Defining x_max, y_max and x_min, y_min for rectangle
# Since diagonal points are enough to define a rectangle
x_max = 10.0
y_max = 8.0
x_min = 4.0
y_min = 4.0
 
 
# Function to compute region code for a point(x, y)
def computeCode(x, y):
    code = INSIDE
    if x < x_min:      # to the left of rectangle
        code |= LEFT
    elif x > x_max:    # to the right of rectangle
        code |= RIGHT
    if y < y_min:      # below the rectangle
        code |= BOTTOM
    elif y > y_max:    # above the rectangle
        code |= TOP
 
    return code
 
 
# Implementing Cohen-Sutherland algorithm
# Clipping a line from P1 = (x1, y1) to P2 = (x2, y2)
def cohenSutherlandClip(x1, y1, x2, y2):
 
    # Compute region codes for P1, P2
    code1 = computeCode(x1, y1)
    code2 = computeCode(x2, y2)
    accept = False
 
    while True:
 
        # If both endpoints lie within rectangle
        if code1 == 0 and code2 == 0:
            accept = True
            break
 
        # If both endpoints are outside rectangle
        elif (code1 & code2) != 0:
            break
 
        # Some segment lies within the rectangle
        else:
 
            # Line Needs clipping
            # At least one of the points is outside,
            # select it
            x = 1.0
            y = 1.0
            if code1 != 0:
                code_out = code1
            else:
                code_out = code2
 
            # Find intersection point
            # using formulas y = y1 + slope * (x - x1),
            # x = x1 + (1 / slope) * (y - y1)
            if code_out & TOP:
               
                # point is above the clip rectangle
                x = x1 + (x2 - x1) *
                                (y_max - y1) / (y2 - y1)
                y = y_max
 
            elif code_out & BOTTOM:
                 
                # point is below the clip rectangle
                x = x1 + (x2 - x1) *
                                (y_min - y1) / (y2 - y1)
                y = y_min
 
            elif code_out & RIGHT:
                 
                # point is to the right of the clip rectangle
                y = y1 + (y2 - y1) *
                                (x_max - x1) / (x2 - x1)
                x = x_max
 
            elif code_out & LEFT:
                 
                # point is to the left of the clip rectangle
                y = y1 + (y2 - y1) *
                                (x_min - x1) / (x2 - x1)
                x = x_min
 
            # Now intersection point x, y is found
            # We replace point outside clipping rectangle
            # by intersection point
            if code_out == code1:
                x1 = x
                y1 = y
                code1 = computeCode(x1, y1)
 
            else:
                x2 = x
                y2 = y
                code2 = computeCode(x2, y2)
 
    if accept:
        print ("Line accepted from %.2f, %.2f to %.2f, %.2f" % (x1, y1, x2, y2))
 
        # Here the user can add code to display the rectangle
        # along with the accepted (portion of) lines
 
    else:
        print("Line rejected")
 
# Driver Script
# First Line segment
# P11 = (5, 5), P12 = (7, 7)
cohenSutherlandClip(5, 5, 7, 7)
 
# Second Line segment
# P21 = (7, 9), P22 = (11, 4)
cohenSutherlandClip(7, 9, 11, 4)
 
# Third Line segment
# P31 = (1, 5), P32 = (4, 1)
cohenSutherlandClip(1, 5, 4, 1)

Выход:

 Линия принимается с 5.00, 5.00 до 7.00, 7.00
Линия принимается с 7.80, 8.00 до 10.00, 5.25
Линия отклонена

Below is C++ code with Graphics using graphics.h 

C++

// C++ program to implement Cohen Sutherland algorithm
// for line clipping.
// including libraries
#include <bits/stdc++.h>
#include <graphics.h>
using namespace std;
 
// Global Variables
int xmin, xmax, ymin, ymax;
 
// Lines where co-ordinates are (x1, y1) and (x2, y2)
struct lines {
    int x1, y1, x2, y2;
};
 
// This will return the sign required.
int sign(int x)
{
    if (x > 0)
        return 1;
    else
        return 0;
}
 
// CohenSutherLand LineClipping Algorith As Described in theory.
// This will clip the lines as per window boundaries.
void clip(struct lines mylines)
{
    // arrays will store bits
    // Here bits implies initial Point whereas bite implies end points
    int bits[4], bite[4], i, var;
    // setting color of graphics to be RED
    setcolor(RED);
 
    // Finding Bits
    bits[0] = sign(xmin - mylines.x1);
    bite[0] = sign(xmin - mylines.x2);
    bits[1] = sign(mylines.x1 - xmax);
    bite[1] = sign(mylines.x2 - xmax);
    bits[2] = sign(ymin - mylines.y1);
    bite[2] = sign(ymin - mylines.y2);
    bits[3] = sign(mylines.y1 - ymax);
    bite[3] = sign(mylines.y2 - ymax);
 
    // initial will used for initial coordinates and end for final
    string initial = "", end = "", temp = "";
 
    // convert bits to string
    for (i = 0; i < 4; i++) {
        if (bits[i] == 0)
            initial += "0";
        else
            initial += "1";
    }
    for (i = 0; i < 4; i++) {
        if (bite[i] == 0)
            end += "0";
        else
Алгоритмы Компьютерная графика

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022