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 pP pP

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

], vn

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;}
}}
}