PODSTAWY GEOMETRII
OBLICZENIOWEJ
Literatura
• F. P. Preparata, M. I. Shamos: Geometria
Obliczeniowa, 1985, Helion, Gliwice.
• M. de Berg, M. van Kreveld, M. Overmars,
O. SchwarzKopf: Computational Geometry
Algorithms and Applications, Springer-
Verlag, 2000.
• H. Pottman, J. Wallner: Computational Line
Geometry, Springer-Verlag, Berlin, 2001.
Zadania konstrukcyjne
1. Umieszczenie nóżki cyrkla w danym punkcie,
2. Umieszczenie nóżki cyrkla na danej prostej,
3. Narysowanie okręgu,
4. Przyłożenie brzegu linijki do danego punktu,
5. Narysowanie prostej.
Łączna liczba takich operacji nazywa się
złożonością konstrukcyjną (podobnie
definiujemy pojęcie złożoności obliczeniowej).
Elementarne konstrukcje
w grafice
komputerowej
• Narysowanie okręgu o danym środku
(ewentualnie zakreślenie lub
wypełnienie kolorem koła),
• Narysowanie okręgu przechodzącego
przez dane trzy punkty,
• Narysowanie łamanej,
• Narysowanie wielokąta (ewentualnie
wypełnienie kolorem).
Zapis algorytmu w
pseudokodzie
Procedure nazwa(parametry)
Instrukcje
Begin instrukcja-1;
…
instrukcja-n;
end
1. przypisanie:=zmienna=źródło
wartości,
2. if warunek then instrukcja else instrukcja,
Ciąg dalszy
3. Pętla
• For zmienna:=wartość until
wartość do instrukcja;
• While warunek do instrukcja;
• Repeat instrukcja until warunek ;
Struktury danych
Struktury danych
S-struktura,
Podstawowe operacje
a)
Czy u
S (odp. TAK, NIE), Member(U,S),
b)
S
S
u
wstaw u do S, INSERT(u,S),
c)
S
S \
u
usuń S z S, DELETE(u,S),
- suma zbiorów,
\ - różnica zbiorów.
Elementy geometrii w
przestrzeni n-wymiarowej
.
)
,
(
|
|
,
)
(
)
)(
(
)
,
(
,
,
,
)
,
(
)
,
(
)
,
(
,
)
,
(
)
,
(
),
0
,
,
0
,
0
(
0
0
)
,
(
,
0
)
,
(
:
,
.
)
,
(
)
,
,
,
(
),
,
,
,
(
)
),
(,
,
,
,
(
_
_
_
1
2
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
1
2
2
1
1
_
_
_
_
2
1
_
2
1
_
x
x
x
y
x
y
x
y
x
y
x
d
z
y
x
y
z
y
x
y
z
x
x
y
y
x
x
x
x
x
x
x
że
sprawdzi
ć
Łatwo
y
x
y
x
y
x
y
x
y
x
y
x
y
y
y
y
x
x
x
x
wektorowa
przestrze
ń
N
i
i
i
N
N
N
i
i
i
N
N
df
N
N
N
Rozmaitości liniowe
}.
:
{
.
0
1
2
.
}.
,
,
,
:
{
:
.
1
,
,
,
,
_
_
1
_
_
2
1
_
_
2
_
2
1
_
1
_
_
2
_
1
_
d
u
u
k
N
PRZYK
Ł
d
u
u
u
zbiór
nazywamy
w
N
k
d
niech
oraz
u
u
u
Niech
k
k
k
k
N
N
N
k
Układ liniowo niezależny w
Płaszczyzną k-wymiarową
u
1
}
:
{
_
_
1
d
u
- prosta w
N
1
_
u
_
2
u
2
2
N
d
Hiperpłaszczyzny
Def. Hiperpłaszczyzną w przestrzeni N-wymiarowej
nazywamy płaszczyznę N-1 – wymiarową.
1
_
1
_
1
1
_
1
_
1
1
_
1
1
,
,
},
,
,
:
{
N
N
N
N
N
u
u
d
u
u
H
Liniowo niezależne
.
1
,
,
1
,
0
,
,
,
,
.
1
,
,
1
0
,
.
ln
,
,
,
_
1
_
1
_
_
1
1
_
_
_
_
_
_
_
_
1
1
_
1
1
_
_
_
_
1
_
1
_
N
j
u
u
u
u
u
u
u
v
N
j
u
v
H
v
u
u
u
v
z
u
u
u
u
j
N
N
j
j
j
j
N
N
N
N
W postaci macierzowej
.
,
,
,
,
,
,
_
1
_
_
1
_
1
1
_
1
_
1
_
1
_
1
_
1
_
1
_
1
_
1
N
N
N
N
N
N
u
u
u
u
u
u
u
u
u
u
u
u
Nieosobliwość macierzy
.
0
0
,
,
,
,
1
1
_
1
_
1
_
1
_
1
_
1
_
1
_
1
_
1
N
N
N
N
N
u
u
u
u
u
u
u
u
Nieosobliwość c.d.
.
1
,
,
1
0
0
0
,
0
,
0
,
,
,
0
,
0
,
0
,
_
1
1
0
0
0
0
_
1
1
0
_
1
1
_
1
1
0
0
_
_
1
1
_
_
_
1
1
N
j
u
z
z
z
z
u
z
u
zatem
u
z
z
u
u
u
u
u
j
j
N
j
j
i
N
i
i
i
N
i
i
j
N
j
j
i
j
N
j
j
i
j
i
N
j
j
Hiperpłaszczyzny c.d.
}
0
,
:
{
_
_
_
_
1
v
x
d
x
N
Zachodzi wzór
Jeśli
0
,
_
_
1
_
_
v
x
d
x
N
Z kolei zaś jeśli:
,
,
0
,
_
_
1
_
_
_
v
u
x
v
x
i
N
i
i
.
0
0
,
0
,
_
_
_
_
v
v
v
x
N
D
Przykład
1
_
u
2
_
u
_
v
Prosta, odcinek
}
:
{
_
_
1
d
u
A
B
odcinek
B
A
B
A
B
A
A
B
A
A
B
A
A
B
A
AB
]}
1
,
0
[
:
)
1
(
{
]
,
[
.
}
:
)
1
(
{
}
:
)
1
(
{
}
:
{
}
:
)
(
{
}
:
{
_
_
_
_
1
_
_
_
_
_
_
_
_
_
_
_
__
1
Zbiory wypukłe
Def. Zbiór
N
D
nazywamy wypukłym, jeśli:
.
]
,
[
,
_
_
_
_
D
y
x
D
y
x
Def. Obwiednią(otoczką) wypukłą zbioru
N
D
nazywamy najmniejszy zbiór wypukły
zawierający D.
conv A
df
obwiednia wypukła.
Tw. Iloczyn dowolnej ilości zbiorów wypukłych jest
zbiorem wypukłym
.
Łamane, wielokąty
Def. Łamaną nazywamy ciąg odcinków w którym
koniec kolejnego jest początkiem następnego:
].
,
[
],
,
[
,
],
,
[
],
,
[
1
1
2
3
2
2
1
n
n
n
n
A
A
A
A
A
A
A
A
1
A
2
A
3
A
4
A
5
A
Def. Łamaną nazywamy zamkniętą, jeśli koniec ostatniego
odcinka pokrywa się z początkiem pierwszego
.
Def. Obszar ograniczony łamaną zamkniętą nazywamy
wielokątem
.
Wielokąty, łamane c.d.
Def. Obszar ograniczony łamaną zamkniętą
nazywamy wielokątem.
Def. Wielokąt nazywamy wielokątem prostym, jeśli
ograniczająca go łamana nie ma punktów
wielokrotnych.
Wielokąt z punktami
wielokrotnymi
Wielokąt prosty
Chmura punktów
Def. Chmurą punktów w
N
nazywamy zbiór punktów
}
,
,
{
_
1
_
n
P
P
nie leżących na jednej hiperpłaszczyźnie.
N=2
Tw. Z)
2
_
1
_
}
,
,
{
n
P
P
- chmura punktów,
,
_
_
j
i
P
P
K={(i,j): wszystkie punkty zbioru
P=
P
po lewej stronie prostej przechodzącej
przez punkty o numerach i,j}.
,
)
,
(
)
(
ij
K
j
i
P
con
T)
gdzie
leżą
i
P
j
P
j
i
P
P
j
i
P
P
K
j
i
P
con
)
,
(
)
(
j
i
P
P
K
j
i
S
)
,
(
j
i
P
P
P
Brzeg
Ponieważ
składa się z odcinków
]
,
[
j
i
P
P
)
(P
con
jest zbiorem wypukłym i zawiera punkty
i
P
wobec tego zawiera odcinki
]
,
[
j
i
P
P
Dowód tw. c.d.
)
(P
con
S
X
Dowolny punkt X ze zbioru S jest punktem odcinka
]
,
[ B
A
gdzie
).
(
,
P
con
S
B
A
A
B
Ponieważ
)
(P
con
jest zbiorem wypukłym, więc
)
(P
con
X
c.n.d.
Algorytm convex
HULL(P)
Input: zbiór P punktów
Output: zbiór K par indeksów
1. K
2. for wszystkich par (i,j) {1,2,…,n} i j do
3. valid true,
4. for wszystkich pP pP
i
p P
j
do
5. if p leży po prawej stronie L
ij,
6. then valid false.
7. end for
8. if valid then K K{(i,j)}.
9. endfor
10. Wyprowadź zbiór K krawędzi wielokąta będącego
con(P).
Znormalizowane
równanie prostej
P
Q
n
v=PQ=[v
x
,v
y
], n=[n
x
,n
y
]=[-v
y
,v
x
], vn
v, n - para zorientowana dodatnio, jeśli:
.
0
y
x
y
x
n
n
v
v
Znormalizowane równanie
prostej
P rzy k ład
v =[1 ,0 ], n=[0 ,1 ].
L
P Q
={X : n (P X ) >0}.
.
0
1
0
0
1
y
x
y
x
n
n
v
v
P
Q
n
X
double line(x,p,q)
{double x[2],p[2],q[2],px[2];
nor[0]=-q[1]+p[1];
nor[1]=q[0]-p[0];
px[0]=x[0]-p[0];
px[1]=x[1]-p[1];
line=skal(nor,px);
return line;
}
double skal(double a[],double b[])
{double zp;
zp=a[0]*b[0]+a[1]*b[1];
return zp;
}
Program otoczka wypukła
Otoczkawyp(x,y,n,K,klen)
{double x[],y[],a[2],b[2],xx[2];
Long n,K[2][],klen,valid;
klen=0;
for (i=0;i<=n;i++)
for(j=0;j<=n;j++)
{ valid=1;
{if i!=j)
{a[0]=x[i];
a[1]=y[i];
b[0]=x[j];
b[1]=y[j];
Program otoczka wypukła
– c.d.
for (k=0;k<=n;k++)
{if(k!=i && k!=j)
{xx[0]=x[k];
xx[1]=y[k];
if (line(xx,a,b)<0) valid=0;}
}
if(valid)
{klen++;
K[0][klen]=i;
K[1][klen]=j;}
}}
}