Programowanie dynamiczne
zaj ˛ecia 1.
Bartosz Górski, Tomasz Kulczy ´nski, Bła˙zej Osi ´nski
Geometria dla informatyka
wył ˛
acznie obliczenia
wszystko oparte na liczbach, współrz ˛ednych, miarach
programista i/lub u˙zytkownik musi przeło˙zy´c geometri ˛e
na j ˛ezyk komputerowych oblicze ´n a pó´zniej
zinterpretowa´c wynik
Geometria dla informatyka
wył ˛
acznie obliczenia
wszystko oparte na liczbach, współrz ˛ednych, miarach
programista i/lub u˙zytkownik musi przeło˙zy´c geometri ˛e
na j ˛ezyk komputerowych oblicze ´n a pó´zniej
zinterpretowa´c wynik
Geometria dla informatyka
wył ˛
acznie obliczenia
wszystko oparte na liczbach, współrz ˛ednych, miarach
programista i/lub u˙zytkownik musi przeło˙zy´c geometri ˛e
na j ˛ezyk komputerowych oblicze ´n a pó´zniej
zinterpretowa´c wynik
Podstawowe poj ˛ecia
punkt
prosta, półprosta, odcinek
trójk ˛
at, wielok ˛
at
okr ˛
ag, elipsa
Podstawowe poj ˛ecia
punkt
prosta, półprosta, odcinek
trójk ˛
at, wielok ˛
at
okr ˛
ag, elipsa
Podstawowe poj ˛ecia
punkt
prosta, półprosta, odcinek
trójk ˛
at, wielok ˛
at
okr ˛
ag, elipsa
Podstawowe poj ˛ecia
punkt
prosta, półprosta, odcinek
trójk ˛
at, wielok ˛
at
okr ˛
ag, elipsa
Odległo´s´c
(x
1
,
y
1
)
(x
2
,
y
2
)
x
2
− x
1
y
2
− y
1
q
(x
2
−
x
1
)
2
+
(y
2
−
y
1
)
2
Iloczyn skalarny
(x
0
,
y
0
)
(x
2
,
y
2
)
(x
1
,
y
1
)
d
1
d
2
(
x
1
− x
0
) · (
x
2
− x
0
) + (
y
1
− y
0
) · (
y
2
− y
0
) =
=
d
1
· d
2
· cos α
Iloczyn wektorowy
(x
0
,
y
0
)
(x
2
,
y
2
)
(x
1
,
y
1
)
d
1
d
2
(
x
1
− x
0
) · (
y
2
− y
0
) − (
x
2
− x
0
) · (
y
1
− y
0
) =
=
d
1
· d
2
· sin α
Równanie prostej
Jest kilka charakteryzacji prostych:
A · x + B · y + C = 0
y = a · x + b
(
x
0
+
t · x
d
,
y
0
+
t · y
d
)
dwa ró˙zne punkty le˙z ˛
ace na niej
Równanie prostej
Jest kilka charakteryzacji prostych:
A · x + B · y + C = 0
y = a · x + b
(
x
0
+
t · x
d
,
y
0
+
t · y
d
)
dwa ró˙zne punkty le˙z ˛
ace na niej
Równanie prostej
Jest kilka charakteryzacji prostych:
A · x + B · y + C = 0
y = a · x + b
(
x
0
+
t · x
d
,
y
0
+
t · y
d
)
dwa ró˙zne punkty le˙z ˛
ace na niej
Równanie prostej
Jest kilka charakteryzacji prostych:
A · x + B · y + C = 0
y = a · x + b
(
x
0
+
t · x
d
,
y
0
+
t · y
d
)
dwa ró˙zne punkty le˙z ˛
ace na niej
Trójk ˛
at
Iloczyn wektorowy jest dokładnie tym czego chcemy!
Wielok ˛
at
Pomysł
dzieli´c na trójk ˛
aty
Wielok ˛
at
Pomysł
dzieli´c na trójk ˛
aty
p
Wielok ˛
at
Pomysł
dzieli´c na trójk ˛
aty
p
Oboj ˛etnie, gdzie le˙zy punkt p!
Opis problemu
punkty na płaszczy´znie
sznurek wokół gwo´zdzi
Opis problemu
punkty na płaszczy´znie
sznurek wokół gwo´zdzi
Rozwi ˛
azanie brutalne
Dla ka˙zdego odcinka, sprawdzamy czy wszystkie pozostałe
punkty le˙z ˛
a po tej samej stronie. O(n
3
)
.
Rozwi ˛
azanie optymalne
Otoczka dolna i górna
dzielimy problem na dwoje
Rozwi ˛
azanie optymalne
Otoczka dolna i górna
dzielimy problem na dwoje
Sortowanie punktów od lewej do prawej.
Rozwi ˛
azanie optymalne
Otoczka dolna i górna
dzielimy problem na dwoje
Sortowanie punktów od lewej do prawej.
Trzeba skorzysta´c z iloczynu wektorowego!
Podsumowanie
druga połówka – analogicznie
poprawno´s´c
zło˙zono´s´c – O(n log n)
przydatno´s´c ogólnej idei tego algorytmu
Podsumowanie
druga połówka – analogicznie
poprawno´s´c
zło˙zono´s´c – O(n log n)
przydatno´s´c ogólnej idei tego algorytmu
Podsumowanie
druga połówka – analogicznie
poprawno´s´c
zło˙zono´s´c – O(n log n)
przydatno´s´c ogólnej idei tego algorytmu
Podsumowanie
druga połówka – analogicznie
poprawno´s´c
zło˙zono´s´c – O(n log n)
przydatno´s´c ogólnej idei tego algorytmu
Document Outline
Wyszukiwarka
Podobne podstrony:
czlony dynamiczne id 128806 Nieznany
Program umiarkowany id 395519 Nieznany
Lab5 Modelowanie dynamiki id 25 Nieznany
Narodowy Program Zdrowia1 id 31 Nieznany
Narodowy Program Zdrowia id 314 Nieznany
Dynamika id 145246 Nieznany
Program cw3 id 395618 Nieznany
Programowanie GUI id 395885 Nieznany
Program zjazdu id 395614 Nieznany
Program cw2 id 395617 Nieznany
Modele dynamiczne id 305054 Nieznany
Dynamika a id 145299 Nieznany
Program cw5 id 395619 Nieznany
Dynamika I id 145322 Nieznany
Program cz1 id 395054 Nieznany
Program cz10 id 395055 Nieznany
program zajec id 395592 Nieznany
Analiza dynamiki id 59972 Nieznany
dynamika 4 id 145261 Nieznany
więcej podobnych podstron