http___fmi.wikidot.com_okg-clipping_1.xml
http___math453spring2009.wikidot.com_lecture-5.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 2.3 3.1 4.1 5.1 6.1 6.2 7.1 8.1 9.1 10.1 10.2 10.3 10.4 10.5 10.6 10.7 11.1 11.2 11.3 12.1 12.2 12.3 12.4 13.1 14.1 14.2 15.1 16.1 17.1 18.1 18.2 18.3 19.1 19.2 19.3 20.1 21.1 21.2 22.1 24.1 26.1 27.1 28.1 28.2 29.1 29.2 30.1 31.1 32.1 32.2 32.3 32.4 32.5 32.6 32.7 33.1 34.1 35.1 36.1 37.1 38.1 39.1 39.2 39.3 40.1 40.2 40.3 41.1 41.2 41.3 41.4 41.5 42.1 42.2 42.3 42.4 43.1 43.2 43.3 43.4 44.1 46.1 47.1 48.1 48.2 49.1 50.1 50.2 50.3 51.1 52.1 52.2
Summary Today we began by finishing off the proof of the fundamental theorem of arithmetic. After we completed the proof, we saw how the fundamental theorem could be used to facilitate the computation of GCDs and LCMs, and we also used it to prove that there are infinitely many primes which leave remainder 3 after division by 4. Finally, we got a sneak peak at the fundamental concept in chapter 2: congruence of integers. Finishing off the FTA In class last time we were in the midst of proving the Fundamental Theorem of Arithmetic, which says The Fundamental Theorem of Arithmetic: Any integer $n>1$ can be uniquely expressed as a product of prime numbers. We had already shown that every integer has a factorization into primes, but we had left to show that this factorization was unique. That's what we'll do now. To show that any integer n has only one prime factorization, suppose we're given two factorizations of an integer n:(1) 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(2) 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$ GCDs, LCMs and FTA To see that the Fundamental Theorem can be used to make our lives easier, we're going to show how it relates to a concept already discussed (GCDs) as well as a close cousin (LCMs, or least common multiples). This second term has yet to be mentioned in this class, so we give a definition Definition: For two positive integers a and b, the least common multiple of a and b — written either $[a,b]$ or sometimes $\mbox{lcm}[a,b]$ — is the smallest number m so that $a \mid m$ and $b \mid m$. Example: Computing $[10,6]$ In order to compute the least common multiple of 10 and 6, we should write down all common multiples of these two numbers:(3) Notice that the first number common to both lists is 30, and so that means that 30 is the least common multiple of 10 and 6. Notice that in this case the least common multiple of a and b was *not* simply ab; there was a smaller common multiple than the "obvious" common multiple. $\square$ Instead of writing out a list of common multiples, it would be nice if we had a uniform way to computer LCMs. In fact, there is a connection between GCDs and LCMs that makes one easy to compute whenever you have the other. This is given by the following Theorem: For any integers a and b, one has $ab = (a,b)[a,b]$. One can prove this result from the definition of GCDs and LCMs, but it because quite cumbersome. Instead, one can prove it by taking advantage of the following result that's borne from the Fundamental Theorem. Theorem: For integers a and b with prime factorizations $a = p_1^{a_1}\cdots p_k^{a_k}$ and $b = p_1^{b_1}\cdots p_k^{b_k}$, one has and We won't prove this result in class, but we'll use it to prove the theorem relating the GCD and LCM of two numbers above. //Proof that //$ab = (a,b)[a,b]$: We'll assume that a and b have factorizations given by $a = p_1^{a_1}\cdots p_k^{a_k}$ and $b = p_1^{b_1}\cdots p_k^{b_k}$ as in the theorem above. This then lets us substitute in the values of $(a,b)$ and $[a,b]$ in the product $(a,b)[a,b]$:(4) Now we just notice that for any integers x and y we have $\min\{x,y\}+\max\{x,y} = x+y$. Hence the product above becomes(5) $\square$ Primes of a Particular form We asked a while back how primes spread out amongst different classes of integers. For instance, we asked: how many primes are there which can be written as $4k$ for some integer k? We saw pretty quickly that there were no primes that took this form. We also asked: how many primes can be written in the form $4k+2$ for some integer k? This time we argued that there was only 1 such prime (namely 2). This left primes of the form $4k+1$ or $4k+3$, and we asked: are there "more" primes of one form than the other? We'll start to give an answer to this question today in class with a proof of the following Theorem: There exist infinitely many primes p for which there exists $n \in \mathbb{Z}$ with $p = 4n+3$. In order to do this, we first note the following Lemma: The product of two integers of the form $4n+1$ and $4m+1$ is another integer of the form $4k+1$. Proof: It isn't hard to see that(6) Taking $k = 4nm + n + m$ gives the desired result.$\square$. Now we're ready to prove our theorem above Proof of Theorem: Suppose, to the contrary, that there are only finitely many such primes. We'll list these primes out in order: $p_0 = 3, p_1 = 7, \cdots$, with the largest such prime denoted $p_k$. We claim that the integer $N = 4p_1\cdots p_k + 3$ contains a prime divisor not on our list. To see this, note first that N is an odd number, so its prime factorization contains only odd primes. If all these primes were of the form $4k+1$, then so too would N be of this form (using induction on our previous lemma). Hence there exists at least one prime divisor p of N for which $p = 4n+3$ for some integer n. We claim that p is not included in our list of primes. Suppose first that $p = 3$. By our result on divisibility of integral linear combinations, this implies that $3 \mid N - 3 = 4p_1\cdots p_k$. Hence Euclid's Lemma implies that either $3 \mid 4$ (which it doesn't) or $3 \mid p_i$ for some i (also impossible). Hence we're led to a contradiction, and so we must have $p \neq 3$. Since we have a complete list of primes which have remainder 3 after division by 4, this means that $p = p_i$ for some $1 \leq i \leq k$. But then we have $p_i \mid N - 4p_1 \cdots p_k = 3$ — another clear contradiction. We're left to conclude that $p \neq p_i$ for any of the $p_i$ in our supposed complete list of primes of the form $4k+3$, and hence our list must have been incomplete. $\square$. Though an awfully nice result, we can't adapt this technique to show that there are infinitely many primes of the form $4k+1$ — we would need a result that says the product of two primes which took the form $4n+3$ again takes that form, but this is NOT true. Hence we have to be more clever if we want to prove such a result. Indeed, studying problems such as these makes us wonder how many primes there are of the form $5n+1$ or $6n + 5$ — or plenty of other possible prime types. Though the proof goes beyond the means we have in this class, there is a big result which tells us about primes of that form Dirichlet's Theorem on Primes in an Arithmetic Progression: For any integers a and b with $(a,b) = 1$, the sequence contains infinitely many prime numbers. The proof of this result uses complex analysis to show that(7) diverges. Crazy! A Preview of Chapter 2: Congruence The topics we've covered so far — basic ideas which are born from the concept of divisibility — cover most of the basic tools used in number theory as of a few hundred years ago. Our next concept — the notion of modular congruence — was developed by Gauss and was a key result for moving forward in number theory. The basic idea centers around the following Definition: Two integers a and b are said to be congruence (or equivalent) module an integer m — written $a \equiv b \mod{m}$ — if $m \mid a-b$. We'll see that this definition provides a relation that has a lot of the properties of our "usual" equality. What is truly powerful, though, is when one realizes that this new version of "equality" admits arithmetic operations (addition and multiplication) just like our usual notion of equality.