http___fmi.wikidot.com_okg-clipping_1.xml
http___math453fall2008.wikidot.com_lecture-4.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 2.2 3.1 3.2 3.3 4.1 5.1 5.2 5.3 5.4 6.1 7.1 7.2 7.3 8.1 9.1 9.2 10.1 10.2 10.3 11.1 12.1 12.2 13.1 13.2 13.3 14.1 15.1 16.1 16.2 17.1 18.1 19.1 20.1 21.1 21.2 21.3 22.1 23.1 23.2 24.1 25.1 25.2 25.3 25.4 26.1 27.1 28.1 28.2 28.3 28.4 29.1 29.2 29.3 29.4 29.5 30.1 31.1 31.2 32.1 33.1 34.1 34.2 34.3 34.4 34.5 34.6 34.7 35.1 35.2 36.1 37.1 38.1 39.1 39.2 39.3 39.4 39.5 39.6 39.7 40.1 40.2 40.3 41.1 41.2 41.3 41.4
Recap & Summary Last class period we talked about greatest common divisors and least common multiples. We saw some of the basic properties of both, and we also saw that they are intimately connected to one another. Today we'll begin by giving a computationally efficient way for computing GCDs known as the Euclidean Algorithm. In practice, this is how GCDs of large numbers are actually computed. Afterwards we'll discuss and prove the Fundamental Theorem of Arithmetic. The Euclidean Algorithm Greatest Common Divisors might seem like a boring subject to you, since likely you already saw GCDs when you were in high school. The kinds of GCDs you were after then — between pairs of numbers which are relatively small and easily factored — are quite different from the kinds of GCDs people care about in practice — namely between pairs of numbers which are much too large to easily factor. For this reason, we need a method for computing GCDs effeciently. The idea for this method comes from the remarkably simple Lemma: Suppose that a and b are integers and that $a = qb + r$ as per the Division Algorithm. Proof: This is really not a hard proof. Suppose that d is a common divisor of a and b. Then since $r = a-qb$, we have that d is a divisor of r as well (using our "divisibility of integral linear combinations" result). Likewise, if d is a common divisor of b and r, then since $a = qb + r$ we have that d is also a divisor of a. Hence all common divisors of a and b are also common divisors of b and r, and vice versa, proving that the greatest elements amongst these common divisors are the same. $\square$ We can apply this idea iteratively to give a computationally effective way to computer GCDs. This process has been known for a long time and — like many other ideas from this chapter — was outlined in Euclid's Elements. For that reason, it bears the moniker of the Euclidean Algorithm. Example: Computing GCDs with the Euclidean Algorithm Suppose you're interested in computing (8633,6319). Using the previous result, since(1) we know that this GCD is the same as (6319,2314). In fact, we can keep using this result over and over again, provided we keep using the division algorithm every time we get a non-zero remainder. These applications of the division algorithm are:(2) Hence we have(3) Example: Expressing GCD as a linear combo This same procedure can be used to write the GCD between a and b as an integral linear combination of the two. In the previous computation, for instance, the second-to-last division algorithm application gives(4) The previous application of the division algorithm, though, showed us that $178 = 623-445$, and hence we can substitute this into our expression for 89:(5) Using the equality $445 = 1691 - 2\cdot 623$ and substituting again gives(6) Continuing this kind of back substitution gives(7) The Fundamental Theorem of Arithmetic Having covered many of the basics, it's now time for us to knock down the Fundamental Theorem of Arithmetic. This theorem is something which you all have seen many times before — whether explicitly or not — and is an incredibly useful tool in number theory. Recall its statement: The Fundamental Theorem of Arithmetic: Any integer $n>1$ can be uniquely expressed as a product of prime numbers. We won't prove the result quite yet, since we need a preliminary result before we can knock down the Fundamental Theorem. This preliminary result is known as Euclid's Lemma, and it is essentially a special case of one of you homework problems for the week (44a). Euclid's Lemma: If p is a prime number and $p \mid ab$, then either $p \mid a$ or $p \mid b$. Proof: Suppose that $p \nmid a$, and we'll argue that $p \mid b$. For this, notice that $p \nmid a$ forces $(p,a) = 1$ — the only divisors of p are 1 and itself, and we already know that p isn't a divisor of a. Applying 44a gives the desired result. $\square$ We can every take this result a little further, arguing that a prime which divides any product of integers (no matter how many) must divide one of the factors. Corollary: If p is a prime number and $p \mid a_1\cdots a_r$, then $p \mid a_i$ for some $i \in \{1, \cdots, r\]$. Proof: We'll apply induction to the previous result. Our base case — when $r = 2$ — is already handled by Euclid's Lemma. So suppose we know that if p divides any product of r-1 integers, then p divides one of those integers. We'll show that if $p \mid a_1\cdots a_r$, then $p \mid a_i$ for some $i \in \{1, \cdots, r\}$. Notice that if $p \mid a_1\cdots a_r$ then $p \mid a_1 \left(a_2 \cdots a_r\right)$. Applying Euclid's Lemma (with $a = a_1$ and $b = a_2\cdots a_r$) then shows $p \mid a_1$ of $p \mid a_2\cdots a_r$. In the former case we're done, and in the latter case we can just apply the induction hypothesis to conclude $p \mid a_i$ for some $i \in \{2, \cdots, r\}$. Together this gives the desired result. $\square$ The Proof of the Fundamental Theorem We're now ready to prove the Fundamental Theorem of Arithmetic. We'll break our proof into two parts - Existence: that every $n > 1$ can be written as $n = p_1\cdots p_r$ for some prime numbers $p_i$ - Uniqueness: there is only one such way to factor a given integer Existence: Suppose that there were integers greater than 1 which couldn't be factored into a product of primes. This would mean that there is a smallest such integer (by the well-ordering principle), and we'll call this smallest element n. Now n can't be prime since otherwise n is already an expression of itself as a product of primes. Hence $n = ab$ for some $1 < a,b < n$. Since both a and b are smaller than n, this means that they must be elements which do have prime factorizations (since n was selected as the smallest positive integer which didn't have this property). Therefore $a = p_1 \cdots p_k$ and $b = q_1 \cdots q_r$ for appropriate primes $p_i,q_j$. But then we have(8) a prime factorization of n. Since this contradicts the selection of n as the least element without a prime factorization, we must conclude that every integer greater than 1 can be factored as a product of primes. Uniqueness: To show that any integer n has only one prime factorization, suppose we're given two factorizations of an integer n:(9) This expression just means that each of the $p_i, q_j$ are prime, and that the corresponding exponents are positive. We aim to show that the list of primes $\{p_1, \cdots, p_r\}$ and $\{q_1,\cdots, q_s\}$ are indeed the same, and moreover that the corresponding exponents match up as well. For this, we start by noting that for each $i \in \{1, \cdots, r\}$, the term $p_i$ clearly divides the first expression of n as a product of primes. For this reason we must also have $p_i \mid q_1^{b_1}\cdots q_s^{b_s}$, and the supped up version of Euclid's Lemma says that $p_i \mid q_j$ for some j. But since $q_j$ is prime, this means that in fact $p_i = q_j$. Hence the list of primes for the first factorization is a subset of the list of primes for the second factorization. Running the same argument for a given prime $q_j$ in the second factorization, we have that the list of primes for the second factorization is a subset of the list of primes for the first. Hence the list of primes are, in fact, identical. And not just identical as sets, but — by virtue of our increasing ordering of the $p_i$ and $q_j$ — we must in fact have $p_i = q_i$ and $r = s$. Now that the lists of primes are identical, we just need to show that $a_i = b_i$. For this, suppose that $a_i > b_i$. Then we have(10) Now clearly $p_i$ divides the first expression (since $a_i - b_i > 0$), whereas it cannot divide the second expression (since $p_i$ doesn't show up in the factorization). This is a contradiction, and so we must have $a_i \leq b_i$. A similar argument shows that $a_i < b_i$ is impossible, and so we have $a_i = b_i$. $\square$