Loading [MathJax]/jax/output/CommonHTML/jax.js
Садржај
1. Основни алгебарски алгоритми
1.1 Увод
1.2 Тест прималности
Тест прималности - квиз
Прости бројеви - задаци
1.3 Факторизација броја
Факторизација броја - квиз
Факторизација броја - задаци
1.4 Највећи заједнички делилац
Највећи заједнички делилац - квиз
НЗД и НЗС - задаци
1.5 Одређивање свих простих бројева до дате границе
Ератостеново сито - квиз
Ератостеново сито - задаци
2. Основни геометријски алгоритми
2.1 Увод
2.2 Поравнати правоугаоници
Поравнати правоугаоници - квиз
2.3 Тачке и вектори
2.4 Оријентација тројке тачака
Односи тачака и вектора - квиз
2.5 Обими и површине многоуглова
Обими и површине многоуглова - квиз
2.6 Визуелизација
3. Основни алгоритми текста
3.1 Увод
3.2 Методи за рад са стринговима
3.2.1 Поређење стрингова
3.2.2 Претраживање и провера постојања садржаја стринга
3.2.3 Трансформисање стрингова
Методи за рад са стринговима - квиз
Стрингови - задаци
3.3.1 Регуларни изрази
3.3.2 Сложенији регуларни изрази
Регуларни изрази - квиз
3.3.3 Регуларни изрази у програмима
Регуларни изрази - задаци
3.4 Парсирање и рекурзивни спуст
3.4.1 Примери граматика
3.4.2 Потпуно заграћени изрази
3.4.3 Произвољни изрази
3.4.4 Креирање дрвета израза
4. Основни графовски алгоритми
4.1 Увод
4.2 Примери графова
Примери графова - квиз
4.3 Дефиниције појмова у вези са графовима
Дефиниције појмова у вези са графовима - квиз
4.4 Представљање графова
Представљање графова у рачунару - квиз
Представљање графова - задаци за самостални рад
4.5 Обилазак графова
Обилазак графова - квиз
Обилазак графова - решени задаци
Обилазак графова - задаци за самостални рад
4.6 Компоненте повезаности
Компоненте повезаности - задаци за самостални рад
4.7 Тополошко сортирање
Тополошко сортирање - задаци за самостални рад
5. Одабрани алгоритми и структуре података
Увод
5.1.1 Проширени Еуклидов алгоритам
Проширени Еуклидов алгоритам - задаци
5.1.2 Рачунање са полиномима
5.1.3 Још неки алгебарски алгоритми
5.2.1 Конвексан омотач
5.2.2 Припадност простом многоуглу
5.2.3 Још неки геометријски алгоритми
5.3.1 Алгоритми претраге подниске
5.3.2 Формати JSON и YAML
5.3.3 Формат Markdown
5.3.4 Још неки алгоритми са текстом
5.4.1 Најкраћи путеви у графу
5.4.2 Минимално разапињуће дрво
5.4.3 Још неки графовски алгоритми

Визуализација

Међу проблемима из области рачунарске геометрије које смо до сада разматрали, неки су врло погодни за визуализацију у графичким апликацијама. На овом месту претпостављамо да сте већ стекли основно знање о креирању графичких апликација, па те основе нећемо објашњавати овде. Читаоце који немају искуства у прављењу графичких апликација упућујемо на Петљин приручник Мали увод у графички кориснички интерфејс.

У наставку разматрамо неке уобичајене проблеме које треба решити приликом визуализације, као што је омогућавање кориснику да приказ помери, увећа или умањи по својој жељи. Приказаћемо начин на који ово може да се постигне, тако да овде приказану технику можете да комбинујете са својим програмима, који ће илустровати нешто од раније наученог.

Чак и ако се одлучите да правите једноставније програме који не омогућавају померање и зумирање приказа, свакако ћете имати потребе да рачунате координате у корисниковом координатном систему када су дате координате у пикселима и обрнуто, тако да препоручујемо да свакако проучите бар део о трансформацији координата.

Комплетан изворни кôд примера који је овде делимично изложен, можете да преузмете на овом линку. На линку се налази изворни код примера трансформације координата, као и осталих пројеката спакованих у један Visual Studio Solution.

Трансформације између координата света и екрана

Корисник програма за визуализацију има на уму неки свој координатни систем, у коме y координата вероватно расте навише, а јединична дуж је је обично знатно већа од једног пиксела екрана. То значи да, када пишемо такав програм, имамо посла са два координатна система. Један координатни систем је корисников, а други потиче од прозора у коме цртамо. Уобичајено је да се координате тачака у ова два система зову редом координате света и координате екрана. Програм треба писати тако да су све информације које корисник задаје и добија изражене у координатама света.

Због тога је потребно да можемо брзо и једноставно да прерачунавамо координате тачака, тј. да од координата тачке у једном систему добијемо координате у другом.

https://petljamediastorage.blob.core.windows.net/root/Media/Default/Kursevi/OnlineNastava/kurs-prog3-spec-IT/transformacija_koordinata.png

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

Трансформације светских координата у екранске

Размотримо прво како на основу координата (xw,yw) неке тачке P у систему света да израчунамо координате (xs,ys) исте тачке у систему екрана.

Нека је, на пример, xw=6,yw=4.5, тј. нека су координате тачке P у систему света (6,4.5). Нека је координатни систем света померен у односу на систем екрана тако да су екранске координате координатног почетка светског система (450,550). Да бисмо израчунали екранске координате (xs,ys) тачке P, потребно је још да знамо дужине јединичних дужи координатних оса система света, изражене у пикселима, тј. јединицама координатног система екрана. Означимо те дужине редом са a,b (a за осу x, а b за осу y).

https://petljamediastorage.blob.core.windows.net/root/Media/Default/Kursevi/OnlineNastava/kurs-prog3-spec-IT/transformacija_w_s.png

Израчунавање координата екрана Xs, Ys, када су познате координате света Xw, Yw.

Користећи боје и ознаке са слике, закључујемо да вредност xs можемо да израчунамо када „на плаву координату зелене y осе (а то је xt=450) додамо xw дужи од по a пиксела”. Слично томе, вредност ys можемо да израчунамо када „од плаве координате зелене x осе (а то је yt=550) одузмемо yw дужи од по b пиксела”. Конкретно, ако узмемо a=b=100, добијамо:

xs=450+1006=150,ys=5501004.5=100.

Приметимо да вредност ys добијамо одузимањем а не сабирањем, зато што су y осе у ова два координатна система различито усмерене.

Пређимо сада на општи случај. Нека је познат положај координатног почетка и величине јединичних дужи система света у координатама екрана. Конкретније, нека су дати следећи параметри:

  • координате (xt,yt) координатног почетка система света, изражене у систему екрана,

  • дужине a,b водоравне и усправне јединичне дужи система света, изражене у систему екрана.

Знајући xt,yt,a,b, за било коју тачку чије су координате у систему света једнаке (xw,yw), екранске координате (xs,ys) исте тачке можемо да израчунамо по формулама:

xs=axw+xt,ys=byw+yt.

И у општем случају подразумевамо да су x осе у овим системима усмерене исто, а y осе различито, па зато у првој формули стоји плус, а у другој минус.

Из ових формула лако се добија и обрнута трансформација.

Трансформације екранских координата у светске

Када су дате координате (xs,ys) тачке P у систему екрана, онда координате (xw,yw) те тачке у систему света можемо да израчунамо помоћу следећих формула:

xw=1a(xsxt),yw=1b(ysyt).

Еко како изгледају функције за прерачунавање координата. Напомињемо да се у програму за уведене параметре користе мало дужа имена:

  • xt је у програму TranslationX

  • yt је у програму TranslationY

  • a је у програму ScalingX

  • b је у програму ScalingY

11
 
1
private void WorldToScreen(float xw, float yw, out float xs, out float ys)
2
{
3
    xs = xw * ScalingX + TranslationX;
4
    ys = -yw * ScalingY + TranslationY;
5
}
6
private void ScreenToWorld(float xs, float ys, out float xw, out float yw)
7
{
8
    xw = (xs - TranslationX) / ScalingX;
9
    yw = (ys - TranslationY) / -ScalingY;
10
}
11

(transformacija_koordinata)

Транслаторно померање слике вучењем

Разумно је очекивати да корисник повремено жели да види део координатног система који тренутно није приказан на екрану. Многи програми зато омогућавају кориснику да мишем повуче приказ у жељену страну. Корисник вуче приказ тако што помера миша са притиснутим тастером и за то време координате миша не треба да се се мењају у систему света, већ само у систему екрана.

Како се мењају параметри трансформације координата приликом вучења приказа? Дужине a,b јединичних дужи се не мењају, али се мења положај xt,yt координатног почетка система света, и то тачно за онолико, за колико се помери миш приликом вучења. Према томе, да бисмо подржали вучење приказа, потребно је да током померања миша са притиснутим тастером ажурирамо вредности xt и yt у формулама (променљиве TranslationX и TranslationY у програму). Ево како то може да изгледа у програму:

31
 
1
private void Form1_MouseDown(object sender, MouseEventArgs e)
2
{
3
    if (e.Button == MouseButtons.Right)
4
    {
5
        // zapocni vucenje
6
        IsDragging = true;
7
        LastDraggingPosX = e.X;
8
        LastDraggingPosY = e.Y;
9
    }
10
    ... // druge obrade dogadjaja pritiska tastera misa
11
}
12
13
private void Form1_MouseMove(object sender, MouseEventArgs e)
14
{
15
    if (IsDragging)
16
    {
17
        TranslationX += e.X - LastDraggingPosX;
18
        TranslationY += e.Y - LastDraggingPosY;
19
        LastDraggingPosX = e.X;
20
        LastDraggingPosY = e.Y;
21
        Invalidate();
22
    }
23
    ... // druge obrade dogadjaja pomeranja misa
24
}
25
26
private void Form1_MouseUp(object sender, MouseEventArgs e)
27
{
28
    if (e.Button == MouseButtons.Right)
29
        IsDragging = false;
30
}
31

(podrska_vucenju_prikaza)

Покретањем примера који следи, можете да стекнете јаснију представу о томе како програм треба да се понаша приликом вучења приказа мишем. Резимирајмо које је очекивано понашање:

  • Програм приказује на екрану нацртан координатни систем света и координате миша у систему света.

  • Током обичног померања миша мењају се приказане координате миша у систему света, а положај координатног система света се не мења.

  • Насупрот томе, када корисник вуче приказ (тј. помера миша са притиснутим тастером), приказане координате миша се не мењају, али се мења положај целог координатног система света.

(viz_transformacije_koordinata_py)

Зумирање

Корисник може да има потребу да увећа или умањи приказ који му нудимо. То се у програмима најчешће ради окретањем точка миша. Размислимо како треба да се промене параметри трансформације координата, да бисмо подржали умањивање или увећавање приказа. Овај пут, мењају се дужине a,b јединичних дужи. Када је потребно да се приказ увећа, ове дужине множимо неким коефицијентом (већим од један), а када треба да се смањи, дужине делимо истим коефицијентом. Када се мења величина приказа, пожељно је да се промени и величина фонта којим се црта текст на екрану, што постижемо множењем или дељењем величине фонта истим коефицијентом који користимо и за промену параметара трансформације координата.

Положај xt,yt координатног почетка система света не морамо да мењамо, и у том случају ће управо координатни почетак бити непомична тачка у приказу. Оно што такође често виђамо у програмима је да непомична тачка буде тренутна позиција миша. У том случају треба променити и вредности xt,yt, а извођење формула за нове вредности ових параметара остављамо читаоцима за вежбу.

У програму, подршка промени величине приказа може да изгледа овако:

15
 
1
private void Form1_MouseMove(object sender, MouseEventArgs e)
2
    {
3
        ... // ostale obrade dogadjaja pomeranja misa
4
        if (e.Delta != 0)
5
        {
6
            // tocak misa je okrenut, zumiraj (ka ili od)
7
            int WheelDelta = SystemInformation.MouseWheelScrollDelta;
8
            float f = (float)Math.Pow(1.1, -e.Delta / WheelDelta);
9
            ScalingX *= f;
10
            ScalingY *= f;
11
            FontSize *= f;
12
            Invalidate();
13
        }
14
        ... // ostale obrade dogadjaja pomeranja misa
15

(podrska_zumiranju)

Задаци:

  • Написати програм који омогућава кориснику да кликовима зада произвољан број тачака, а приказује задате тачке и најмањи рам (поравнати правоугаоник) који их садржи.

  • Написати програм који омогућава кориснику да кликовима зада три тачке, а приказује паралелограм коме су задате тачке редом прва три темена (програм треба да одреди четврто теме).

  • Написати програм који омогућава кориснику да кликовима зада две тачке, а приказује квадрат коме су то два суседна темена.

  • Написати програм који омогућава кориснику да кликовима зада две тачке, а приказује квадрат коме су то два наспрамна темена.

  • Написати програм који омогућава кориснику да кликовима зада три тачке, а затим одговара на питање да ли дата тројка чини заокрет и на коју страну.

  • Написати програм који омогућава кориснику да кликовима зада темена многоугла, а затим одговара на питање да ли је задати многоугао конвексан.

  • Написати програм који омогућава кориснику да кликовима зада темена многоугла, а затим израчунава и приказује обим и површину тог многоугла.

Програмима по жељи можете да додате контроле или другачију подршку, помоћу које корисник може да обрише тачку, помери тачку, понови цео поступак и слично.

Технике које су овде приказане можете и не морате да користите у својим програмима. Приказане технике су нарочито корисне у последњем задатку.

Претходна лекција
Следећа лекција
A- A+
Тема
Темa

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.