Geometria obliczeniowa
zaj ˛ecia 8.
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:
GEOMETRIA OBLICZENIOWA I
Geometria Obliczeniowa III
Geometria obliczeniowa — lista 5, zadanie 4
Geometria Obliczeniowa V
Geometria obliczeniowa — lista 5, zadanie 4
Geometria obliczeniowa Wprowadzenie
Geometria Obliczeniowa II
Geometria obliczeniowa – przecinanie się odcinków 2
geometria, 2.0 B-U-D-O-W-N-I-C-T-W-O, 2.2 OBLICZENIA, 2.2.1 Geometria Wykreślna
Geometria Obliczeniowa IV
GEOMETRIA OBLICZENIOWA I
Geometria obliczeniowa Wprowadzenie geobli
Geometria obliczeniowa Wprowadzenie
Geometria obliczeniowa Wprowadzenie 2
Geometria Obliczeniowa Diagramy Voronoi
Geometria obliczeniowa Wprowadzenie geobli
więcej podobnych podstron