http___fmi.wikidot.com_okg-clipping_1.xml
http___dcernst-teaching.wikidot.com_forum_t-274378_each-versus-every.xml
1.1 2.1 3.1 4.1 4.2 5.1 6.1 6.2 6.3 7.1 8.1 9.1 9.2 10.1 11.1 11.2 11.3 12.1 13.1 14.1 14.2 14.3 15.1 16.1 16.2 16.3 17.1 18.1 18.2 19.1 20.1 20.2 20.3 20.4 20.5 21.1 22.1 23.1 23.2 24.1 24.2 24.3
Екранно отсичане (clipping) страницата се нуждае от дописване/преглеждане Увод Както е споменато по-рано тук доста важен е въпросът за това, кое се вижда на екрана, и кое е покрито или извън екрана (и съответно - не се вижда). Ще разгледаме два елементарни алгоритъма, чрез които намираме каква част от отсечка или многоъгълник се намират в друг многоъгълник (отсичащ). Отсичане на отсечка Ще използваме алгоритъма на Cyrus-Beck. Честно казано - тези двамата не са измислили нищо особено - алгоритъмът е от прост по-прост. Да видим първо какво е дадено - отсечка с крайща $p_1p_2 = p$ - изпъкнал многоъгълник $W = \{ f_1, f_2, \cdots, f_k \}$ Целта е в края на алгоритъма да получим нова отсечка $p'_1p'_2$ която е изцяло вътре в многоъгълника $W$. Разбира се допустимо е накрая да остане … нищо, защото отсечката е вън от многоъгълника. Алгоритъмът Ще разгледаме поотделно всички страни на многоъгълника и ще отсечем последователно отсечката със всяка от тях. Както виждате задачата се свежда до отсичане на една отсечка (дадената) със друга отсечка (страна от многоъгълника), като разбира се от дадената отсечка остава тази част, която е във вътрешността на многоъгълника. Да разгледаме малко картинки: Аналитично задаване на отсечка Първо ще покажем един начин за аналитично задаване на отсечката $p_1p_2$ чрез функция на един аргумент:(1) Аргумента $t$ всъщност показва колко далече сме от началото на отсечката и в каква посока. Например $p(\frac{1}{2})$ е точно средата на отсечката, докато $p(-1)$ е централно симетричната на $p_2$ относно $p_1$. Точно заради това при $t \in [0, 1]$ функцията описва точно всички точки от отсечката. Намиране на пресечна точка на две отсечки Сигурно сте се досетили, че ще търсим пресечната точка на отсечката $p_1p_2$ със страните на многоъгълника $f_if_{i+1}$. Нека за всяка страна $f_if_{i+1}$ изберем нормалният вектор който сочи към вътрешността на многоъгълника - $n_i$. Сега ще изразим аналитично чрез $p(t)$ пресечната точка на $f_if_{i+1}$ и $p_1p_2$, като използваме факта, че скаларното произведени на 2 перпендикулярни вектора (именно $n_i$ и вектора образуван от $f_i$ и пресечната точка $p(t)$) е 0:(2) Сега да видим каква информация събрахме до момента: Освен това имаме и информация за това каква е ориентацията на отсечката спрямо страната - т.е дали $p_1$ е по-близо (по ъгъл) до вътрешността или $p_2$. Знака на знаменателя определя косинуса между векторите $\overrightarrow{p}$ и $\overrightarrow{n_i}$. Следната таблица обединява горните две за да се види в кой точно случай се намираме: След като разбрахме в кой случай се намираме, остава да отрежем отсечката по подходящ начин и да продължим нататък. За да си улесним живота, ще пазим просто горна и долна граница на $t$, когато отсичаме. Примерно ако се окаже, че отсечката е отсечена през средата и остава частта със $p_2$, то записваме, че отсечката започва минимум от $t = \frac{1}{2}$, защото по-малките $t$ са извън многоъгълника. Съответно ако остава частта съдържаща $p_1$ то отбелязваме, че отсечката стига максимум до $t = \frac{1}{2}$, защото по-големите $t$ са извън многоъгълника. Ето табличен израз на последното: Отсичане на многоъгълник Алгоритъмът За всяка отсечка от отсичащия многоъгълник и всяка отсечка от отсичания многоъгълник правим горния алгоритъм. После това което остане от всички отсечки го сглобяваме и полученият франкещайн е отсечения многоъгълник. Естествено, има и други начини (пр. Sutherland-Hodgman clipping algorithm, Weiler-Atherton clipping algorithm и др.). Ако някой желае, да се чувства свободен да ги сподели.
1.1 2.1 3.1 3.2 3.3 4.1 4.2 4.3 4.4 4.5 4.6 5.1 6.1 7.1 7.2 7.3 7.4
At the end of class on Friday, Jeff and I had an interesting discussion about the wording of Theorem 1.60, which says If $p_1, p_2, p_3, \ldots$ is a non-decreasing sequence and there is a point, $x$, to the right of each point of the sequence, then the sequence converges to some point. Jeff claimed (please correct me if I am wrong) that the word every should have been used (as it is in the Completeness Axiom) instead of each. I claimed that it didn't matter which word was used and that the meaning was the same. I've just thought about this a little more and figured that I might as well share my thoughts. The quantifier on $x$ indicates that we are talking about a single $x$. This single $x$ is to right of each point in the sequence. That is, if you pick a random $p_i$ in the sequence, $p_i<x$. This implies that $x$ is to the right of every point in the sequence. The $x$ is a "one size fits all" point. So, I maintain it doesn't matter whether we use each or every. Contrast the statement of the theorem with the following statement: For each point in the sequence, there is a point $x$ that is to the right. In this case, the dependence of the quantifiers is reversed and we no longer have a "one size fits all" $x$. Each individual point $p_i$ in the sequence has a point $x_i$ to the right, where I am using a subscript on $x$ to emphasize that this point depends on $p_i$. The point to the right of $p_i$ may be different than the point to the right of $p_j$ (assuming $i\neq j$). This is a very different situation than that in Theorem 1.60.