http___fmi.wikidot.com_okg6_1.xml
http___mathonline.wikidot.com_level-curves-and-contour-plots.xml
1.1 2.1 3.1 3.2 3.3 3.4 3.5 3.6 4.1 5.1 5.2 5.3 6.1 6.2 6.3 7.1 8.1 8.2 8.3 8.4 8.5 9.1 10.1 10.2 10.3 10.4 10.5 11.1 12.1 12.2 13.1 13.2 13.3 13.4 13.5 14.1 15.1 15.2 16.1 17.1 18.1 19.1 19.2 19.3 20.1 20.2 20.3 20.4 21.1 21.2 21.3 22.1 23.1 23.2 23.3 24.1 24.2 25.1 26.1 27.1 28.1 28.2 28.3 29.1 30.1 30.2 30.3 31.1 31.2 32.1 32.2 33.1 34.1 34.2 35.1 36.1 37.1 38.1 39.1 39.2 39.3 39.4 39.5 40.1 40.2 40.3 41.1 42.1 42.2 43.1 43.2 44.1 44.2 44.3 44.4
Дискретно изчертаване на основни примитиви – отсечка, окръжност, елипса Растеризация Често се налага да се изчертават на екрана основни геометрични обекти като отсечки, части от окръжност/елипса. Както знаете обаче мониторът е правоъгълна таблица от пиксели, като всеки пиксел свети в определен цвят. Естествено възниква проблемът за изчертаване на отсечка/окръжност със зададени координати1 върху тази правоъгълна таблица. Т.е трябва да определим кои точно пиксели трябва да светят и евентуално колко силно. Проблемът не е сложен за решаване, но бързодействието е от изключително голяма важност. В тази глава ще разгледаме основните алгоритми за растеризация на отсечка, окръжност и елипса. Отсечка Най-често се налага изобразяването на отсечки върху растера2. Ще разгледаме алгоритъма на Брезенхам (на английски Bresenham). Като за начало да видим какво точно ще правим: Ако си представим отсечката като безкрайно тънка линия, която минава през 2 точки от екрана, то трябва да 'светнем' квадратчетата (пикселите), през които тази отсечка минава. За удобство ще приемем, че отсечката върви от югозапад (долу-ляво) до североизток (горе-дясно) и ъгълът, който тя сключва със $\overrightarrow{Ox}$, e по-малък от 45 градуса (т.е отсечката е по-"легнала"). Всички останали случаи са еквивалентни на този с подходяща ротация на координатната система. С тези ограничения задачата ни става наистина много лесна - ако си представим, че в момента сме в даден пиксел и се чудим в кой следващ пиксел да отидем имаме само 2 възможности - надясно или по диагонал нагоре и надясно: На всяка стъпка от алгоритъма, трябва да знаем текущото квадратче, което сме светнали както и грешката, която показва колко далеч е минала линията от квадратчето. За център на квадратчето ще приемем долния му ляв ъгъл. Ще разглеждаме също пресечните точки на линията (отсечката) с вертикалните линии на решетката. Спрямо тези точно пресечни точки (отбелязани с червено на фигурата) избираме най-близката точка от решетката по тази вертикална линия (т.е най близкия долен ляв ъгъл на квадрат със същия $x$) - на фигурата е отбелязано с лилаво мерниче. След като изберем долните леви ъгли просто светваме съответните им квадратчета (т.е квадратчето, което стои горе вдясно спрямо точката). бре Имаме дадени 2та края на отсечката - нека това са $(x_1, y_1), (x_2, y_2)$. Тогава $\Delta x = x2 - x1, \Delta y = y2 - y1$. Нека за улеснение приемем, че $\Delta x \ge \Delta y$, т.е линията има по-малък наклон от $\frac{\pi}{4}$. Ако си отбележим наклона с $\alpha$, то $\tg \alpha = \frac{\Delta y}{\Delta x} = m$. Това е първата много важна характеристика на линията (за единица дължина по $x$, колко пиксела нагоре (по $y$) се изкачва линията). Алгоритъм на Брезенхам: - Във всеки момент се знае кой е текущият пиксел, в който се намираме - $x_c, y_c$ както и стойността на текущата грешка - $e$, т.е колко далече минава истинската линия от квадратчето. Ще приемем, че координатите на квадратчето са координатите на долния му десен ъгъл и ще се интересуваме повече от самото ъгълче, отколкото от целия квадрат. - От всеки пиксел можем да се движим или надясно (т.е увеличаваме $x$) или по диагонал (т.е увеличаваме $x$ и $y$). Това зависи от грешката - тя се изчислява като към старата грешка прибавим $m$. Т.е $e_{new} = e_{old} + m$. Тъй като грешката е разстоянието от долния десен ъгъл на пиксела до пресечната точка на истинската отсечка с вертикалната права, минаваща над този долен десен ъгъл (на картинката отбелязано със синьо), то за да получим следващата грешка прибавяме точно разстоянието, което отсечката ще "изкачи" за един пиксел. Тъй като искаме точката (долния десен ъгъл) да бъде най-близо до пресечната точка на отсечката с вертикалната права, то ако грешката е повече от $\frac{1}{2}$, избираме горната точка, иначе - долната. Окръжност Сега ще разгледаме подробно алгоритъма за растеризиране на окръжност. За удобство ще приемем за изчертаваната окръжност: - центъра и е в $(0, 0)$ (в общия случай трябва да транслираме) - има целочислен радиус - изчертаваме само частта, която е разположена в първи квадрант (останалите са симетрични) Както при алгоритъма за отсечка, ще приемем, че пиксела се отъждествява с долния си ляв ъгъл. Също така по текущ пиксел в който се намираме $(x, y)$, ще видим как да стигнем до следващия. В случая на окръжност, ако изчертаваме само първи квадрант имаме следните 3 случая: надясно (по хоризонтала), надолу и надясно (по диагонал), на долу (по вертикала): Ще разгледаме случай 1 и 2, останалите два са им симетрични. Основното, което ще използваме, е разстояние от точка до окръжност, което се свежда до разстояние между 2 точки (самата точка и центъра на окръжността). Нека с функцията $k(x, y)$ означим това разстояние. Тогава:(1) Първо трябва да разберем дали сме в първите два случая (1 и 2) или във вторите два случая (3 и 4). За тази цел просто ще определим разположението на точката по диагонала (с координати $(x+1, y-1)$) спрямо окръжността - т.е дали тя е външна или вътрешна. Да положим на $\Delta$ разстоянието от диагоналната точка до центъра на окръжността:(2) Очевидно: Да разгледаме подробно случай 1 (окръжността минава между точките с координати $(x+1, y)$ и $(x+1, y-1)$ (т.е между дясната и диагоналната спрямо текущата). За да разберем коя от 2те точки трябва да светнем, трябва да проверим до коя точка модула от разстоянието до окръжността е минимално - т.е да изберем по-близката до окръжността точка. С други думи трябва да сравним:(3) Понеже сме в първи случай, знаем че точката $(x+1, y)$ е извън окръжността, а точката $(x+1, y-1)$ е в окръжността, следователно знаем знаците на изразите в модулите. Да махнем модула и да разпишем:(4) Сега да видим какво става според знака на $\delta$: С това случай 1 е завършен. Да разгледаме случай 2: По принцип може да направим абсолютно същите разсъждения като в предния случай - това обаче не е необходимо. В случай 2 и диагоналната и дясната точка са в окръжността и очевидно дясната е по-близо, т.е в този случай избираме дясната. Сега ще проверим следното: когато сме в случай 2, $\delta \le 0$, т.е стойността, която сметнахме за случай 1 ще важи и тук (т.е няма нужда даже да проверяваме дали сме в този случай - просто разписваме $\delta$ все едно сме в случай 1 и използваме резултата). Във втори случай сме когато дясната точка е в окръжността: Т.е получихме, че когато сме във 2ри случай, то сметнатото $\delta$ от първи случай е винаги отрицателно. Но това означава че ако просто бяхме забравили за 2ри случай и приемем че има само първи, ако получим $\delta < 0$ пак ще вземем хоризонталната дясна точка - т.е ще направим правилен избор. Ето защо 1ви и 2ри случай се изчерпват с разглеждането на таблицата, показана в 1ви случай. Както казахме 3ти и 4ти случай са напълно аналогични на разгледаните до сега. Ще запишем в таблица всички случай за улеснение: $\Delta'$ е просто новата стойност на $\Delta$. Така си спестявате малко умножения :) Елипса Остана да разлгедаме и алгоритъма на Бреззенхам за растеризация на елипса. Ще приемем че: - елипсата има център $(0, 0)$ и осите и са успоредни на координатните (т.е така би изглеждала след канонизация) - дължините на диаметрите й са реални числа - ще начертаем само частта и в първи квадрант Сега да погледнем какво трябва да се получи: Ще чертаем само в първи квадрант отдолу нагоре. При тези условия ако в даден момент се намираме в клетка $(x, y)$ имаме 3 възможни случая - нагоре, наляво и по диагонал (горе-ляво). В началото елипсата ще се движи по-скоро нагоре (т.е следващият пиксел ще е или над текущия или по диагонал), а след един точно определен момент (този, в който допирателната към елипсата сключва ъгъл 135 (= 180 - 45) градуса с $Ox$) - наляво. Преди и след този специален момент, алгоритъмът върви по подобен начин. Първо ще разгледаме ъгъл на допирателната по-малък от 135 градуса: Ако в момента се намираме в $(x, y)$, то следващата точка е или $(x, y+1)$ (нагоре) или $(x-1, y+1)$ (по диагонал). За да решим коя от 2те ще изберем, ще проверим положението на средната точка $(x - \frac{1}{2}, y+1)$ спрямо елипсата. Просто ще заместим в уравнението на елипсата:(7) След като тангенсът на допирателната стане по-малък от -1 (в началото е $-\infty$ при ъгъл $\frac{\pi}{2}$ (защото е вертикална), накрая е $0$ при ъгъл $\pi$ (защото е хоризонтална)), трябва да разгледаме новата средна точка $(x-1, y+\frac{1}{2})$: Единствено остава да изясним преминаването от случай 1 към случай 2. Производната спрямо $x$ на функцията $f(x, y)$ е точно:(9) Заместваме със $x, y$ и получаваме производната. После естествено я сравняваме с $-1$ Забележка: Как да получите формулата за производната? П просто разписвате спрямо $y$ или пък правите пълен диференциал на функцията. Как точно? Има статии по анализ :)
1.1 2.1 2.2 3.1 4.1 4.2 4.3 5.1 5.2 5.3 6.1 7.1 7.2 7.3 7.4 8.1 9.1 9.2 9.3 9.4 10.1 11.1 12.1 12.2 12.3 13.1 14.1 15.1 15.2 15.3 15.4 15.5 15.6 15.7
Level Curves and Contour Plots As we've already seen, it is often times very difficult to graph surfaces in $\mathbb{R}^3$ on a flat surface. However, we will develop a method of depicting a surface given by a two variable real-valued function $z = f(x, y)$. From the definition of a level curve above, we see that a level curve is simply a curve of intersection between any plane parallel to the $xy$-axis and the surface generated by the function $z = f(x, y)$. For example, consider the two variable real-valued function $f(x, y) = x^2 + y^2$, which represents a paraboloid that is parallel to the $z$-axis, and consider the level curves generated by the intersection of this paraboloid with the planes $z = 1$, $z = 2$, and $z = 3$. These level curves will be concentric circles with center $(0, 0)$. The image below depicts the level curve of this paraboloid corresponding to $z = 2$. Another example is the two variable real-valued function $f(x, y) = x^2 - y^2$ which represents a hyperboloid. The level curves generated by the planes $z = 1$, $z = 2$, and $z = 3$ are hyperbolas. The image below depicts the level curve of this hyperboloid corresponding to $z = 1$. We will now look at another definition is applying these level curves. When we depict a contour plot of a two variable function, it is important to note that it is impossibly to place all the level curves of $z = f(x, y)$ onto the $xy$-plane, and so we often choose specific level curves. For example, consider the paraboloid $f(x, y) = x^2 + y^2$ once again. We saw above that the level curves for $f$ were concentric circles. The following image represents a few planes that are parallel to the $xy$-plane intersecting this paraboloid. If we project all of these level curves onto the $xy$-plane, then we would obtain the following contour plot for $f(x, y) = x^2 + y^2$. For a two variable real-valued function, a contour plot can tell us regions of elevation and regions of depression. For example, from above, we can see that as $x$ increases, we scale up the paraboloid. The same happens for when $y$ increases. However, when both $x$ and $y$ approach $0$, we get closer and closer to the part of the paraboloid that is at its "deepest". Example 1 Describe the shape of the surface given by the following contour plot: We first note that the elevation increases as we go along the $x$-axis in both directions, and that the elevation decreases as we go along the $y$-axis in both directions. We also note that the level curves of this contour plot are hyperbolas. We deduce that this is a contour plot of a hyperboloid. Example 2 Construct a contour plot for the surface generated by the two variable real-valued function $f(x,y) = x + 2y$. We first note that $f$ represents a slanted plane. Let's now determine what the level curves of $f$ look like. First let $z = 0$. Then we get the equation $0 = x + 2y$, or rather $y = -\frac{x}{2}$, which represents a negative straight line. In fact, notice that the level curve corresponding to $z = k$, $k \in \mathbb{R}$ is $y = -\frac{x}{2} + \frac{k}{2}$ which represents a negative straight line. Thus, all of our level curves are straight lines. Notice that as $k$ increases, the $y$-intercept of the corresponding level curve also increases, and so we can even determine the relative elevation of the plane as depicted with the contour plot for $f$ shown below: