Лекциите на ФМИ

За да изглеждаме умни пред другите

Начало

Начална страница

Членове на
сайта

Присъедини
се

За автори

Препоръки за писане на
статии

Формат на статиите

Форум

Новини от
форума

Последни
промени

Списък със
задачи

Първи курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

За
администратори

Create account or Sign in

Начало

Начална страница

Членове на сайта

Присъедини се

За автори

Препоръки за писане на
статии

Формат на статиите

Последни
промени

Панел за
администратори

Лекции

Първи Курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

Избираеми дисциплини

Математическа Логика

Дискретна Оптимизация

Теория на Множествата

Теория на Графите

Избрани Глави от
Анализа

Okg Clipping

Екранно отсичане (clipping)

страницата се нуждае от дописване/преглеждане

foldunfold

Table of Contents

Увод

Отсичане на
отсечка

Алгоритъмът

Аналитично задаване на
отсечка

Намиране на пресечна точка
на две отсечки

Отсичане на
многоъгълник

Алгоритъмът

Увод

Както е споменато по-рано тук
доста важен е въпросът за това, кое се вижда на екрана, и кое е покрито или
извън екрана (и съответно - не се вижда). Ще разгледаме два елементарни
алгоритъма, чрез които намираме каква част от отсечка или многоъгълник се
намират в друг многоъгълник (отсичащ).

Отсичане на отсечка

Ще използваме алгоритъма на Cyrus-Back. Честно казано - тези двамата не са
измислили нищо особено - алгоритъмът е от прост по-прост. Да видим първо какво е
дадено

отсечка с крайща

изпъкнал многоъгълник

Целта е в края на алгоритъма да получим нова отсечка
която е изцяло вътре в многоъгълника .
Разбира се допустимо е накрая да остане … нищо, защото отсечката е вън от
многоъгълника.

Алгоритъмът

Ще разгледаме поотделно всички страни на многоъгълника и ще отсечем
последователно отсечката със всяка от тях. Както виждате задачата се свежда до
отсичане на една отсечка (дадената) със друга отсечка (страна от многоъгълника),
като разбира се от дадената отсечка остава тази част, която е във
вътрешността на многоъгълника. Да разгледаме малко картинки:

Аналитично задаване на отсечка

Първо ще покажем един начин за аналитично задаване на отсечката
чрез функция на един аргумент:
(1)

Аргумента
всъщност показва колко далече сме от началото на отсечката и в каква
посока. Например
е точно средата на отсечката, докато
е централно симетричната на
относно .
Точно заради това при
функцията описва точно всички точки от отсечката.

Намиране на пресечна точка на две отсечки

Сигурно сте се досетили, че ще търсим пресечната точка на отсечката
със страните на многоъгълника .
Нека за всяка страна
изберем нормалният вектор който сочи към вътрешността на многоъгълника
- .
Сега ще изразим аналитично чрез
пресечната точка на
и ,
като използваме факта, че скаларното произведени на 2 перпендикулярни вектора
(именно
и вектора образуван от
и пресечната точка )
е 0:
(2)

Сега да видим каква информация събрахме до момента:

пресечната точка е извън отсечката (преди началото)

пресечната точка е върху отсечката

пресечната точка е извън отсечката (след нея)

Освен това имаме и информация за това каква е ориентацията на отсечката
спрямо страната - т.е дали
е по-близо (по ъгъл) до вътрешността или .
Знака на знаменателя определя косинуса между векторите
и .

ъгълът е ,
т.е
е по към вътрешността

ъгълът е ,
т.е .
В този случай не трябва да търсим
иначе ще делим на 0

ъгълът е ,
т.е
е по към вътрешността

Следната таблица обединява горните две за да се види в кой точно случай се
намираме:

3

4

2

1

4

3

След като разбрахме в кой случай се намираме, остава да отрежем отсечката по
подходящ начин и да продължим нататък. За да си улесним живота, ще пазим просто
горна и долна граница на ,
когато отсичаме. Примерно ако се окаже, че отсечката е отсечена през средата и
остава частта със ,
то записваме, че отсечката започва минимум от ,
защото по-малките
са извън многоъгълника. Съответно ако остава частта съдържаща
то отбелязваме, че отсечката стига максимум до ,
защото по-големите
са извън многоъгълника. Ето табличен израз на последното:

случай \ начални стойности

1

при нов кандидат за максимум избираме по-малкия, защото точките
по-големи от кой да е от тях са извън отсечката

2

при нов кандидат за минимум избираме по-големия, защото точките
по-малки от кой да е от тях са извън отсечката

3

по този начин ефективно затриваме цялата отсечка

4

по този начин ефективно затриваме цялата отсечка

Отсичане на многоъгълник

Алгоритъмът

За всяка отсечка от отсичащия многоъгълник и всяка отсечка от отсичания
многоъгълник правим горния алгоритъм. После това което остане от всички отсечки
го сглобяваме и полученият франкещайн е отсечения многоъгълник.

Естествено, има и други начини. Ако някой желае, да се чувства свободен да ги
сподели.

page_revision: 4, last_edited: 1229160757|%e
%b %Y, %H:%M %Z (%O ago)

EditRate
(0)TagsDiscuss History Files
Print Site tools+ Options

Edit sections Append Edit meta Watchers Backlinks Page source Parent Lock
page Rename Delete

Help | Terms
of Service | Privacy | Report a bug | Flag as objectionable
Powered by Wikidot.com

Unless otherwise stated, the content of
this page is licensed under Creative
Commons Attribution-NonCommercial-ShareAlike 3.0 License

Click here to edit contents of this page.

Click here to toggle editing of individual
sections of the page (if possible). Watch headings for an "edit" link when
available.

Append content without editing the whole
page source.

Check out how this page has evolved in the past.

If you want to discuss contents of this page -
this is the easiest way to do it.

View and manage file attachments for this page.

A few useful tools to manage this Site.

See pages that link to and include this page.

Change the name (also URL address, possibly
the category) of the page.

View wiki source for this page without
editing.

View/set parent page (used for creating
breadcrumbs and structured layout).

Notify administrators if there is
objectionable content in this page.

Something does not work as expected? Find out
what you can do.

General Wikidot.com documentation and help
section.

Wikidot.com Terms of Service - what you can,
what you should not etc.

Wikidot.com Privacy Policy.