Trian_mon(P)

Input: y-monotoniczny wielokąt zapamiętany jako zbiór boków,
Output: triangulacja D jako zbiór krawędzi.

1. Wyodrębnij prawy i lewy łańcuch punktów,
2. Uporządkuj zbiór wierzchołków ze względu na współrzędną y

},

,

{

2

1

u

u

S

3.

4. For j=3 until n-1 do
5. If

j

u

oraz ostatni punkt w S są na różnych łańcuchach then
wstaw przekątną od do punktów z S, tak aby
odciąć trójkąt od wielokąta.
wstaw oraz do S.
else
usuń ostatni wierzchołek z S.

j

u

1



j

u

j

u

6.

Trian_mon(P) c.d.

7. Usuń kolejne wierzchołki S jeśli tylko przekątna z

j

u

do tego wierzchołka zawiera się wewnątrz wielokąta.
Wstaw te przekątne do D. Wstaw ostatni wyrzucony z S
wierzchołek spowrotem do S.
8. Wstaw do S.
Endif
9. Dodaj przekątne poprowadzone do wszystkich
Wierzchołków z S za wyjątkiem pierwszego i ostatniego.

j

u

n

u

Tw. Wielokąt monotoniczny może być striangularyzowany
w czasie O(n log n) z wykorzystaniem O(n) pamięci.

Zawieranie się odcinka

w wielokącie

A

B

Jeśli odcinek przecina się z brzegiem na
pewno nie zawiera się w wielokącie.
Jeśli końcami odcinka są wierzchołki
wielokąta to obowiązują
tutaj te same zasady.

Odcinek nie zawiera się w wielokącie, nie jest przekątną.
Przecina brzeg wielokąta.

Odcinek nie zawiera się w wielokącie,
pomimo tego, że nie przecina brzegu.

Zawieranie się odcinka

w wielokącie - c.d.

Zachodzi następujące twierdzenie:

Tw. Odcinek zawiera się w wielokącie wtedy i tylko wtedy,
gdy nie przecina brzegu oraz przynajmniej jeden jego punkt
wewnętrzny należy do wnętrza wielokąta

.

Dowód: Jest oczywistym, że jeśli odcinek zawiera się w
wielokącie to nie przecina brzegu i każdy jego punkt
wewnętrzny zawiera się w wielokącie w szczególności
jakiś wybrany.
Z drugiej strony, jeśli odcinek nie przecina brzegu i jeden
z jego punktów wewnętrznych zawiera się wewnątrz wielokąta
to wszystkie jego punkty też muszą się w nim zawierać, bo w
przeciwnym razie ten odcinek przecinałby brzeg wielokąta. c.n.d.

Przynależność punktu do

wielokąta

Zachodzi następująca własność:

Punkt P należy do wnętrza wielokąta wtedy i tylko wtedy, gdy
półprosta pozioma wychodząca z tego punktu przecina
nieparzystą liczbę razy brzeg tego wielokąta.

P

Q

Punkt Q nie należy do wielokąt,
natomiast P należy.

A

Przecięcie odcinka z

półprostą

A

B

P

Przecięcie półprostej l z odcinkiem [A,B]

l={X=P+t[1,0]: t>0}

X

,

),

,

(

),

,

(

____

AB

v

y

x

B

y

x

A

B

B

A

A







Równanie prostej m przechodzącej przez punkty A, B:
m={X=A+sv, s jest liczbą rzeczywistą}.
Jeśli X jest punktem wspólnym l i m to:
X=P+t[1,0]=A+sv, czyli t[1,0]-sv=PA. Niech

],

,

[

y

x

v

v

v 

wtedy

),

,

(

]

,

[

P

A

P

A

y

x

y

y

x

x

sv

sv

t











stąd

.

,

P

A

x

y

P

A

x

x

sv

t

v

y

y

s













Jeśli t>0 oraz 0<s<1 jest
przecięcie
W przeciwnym razie nie ma.

Przecięcie odcinka z

półprostą c.d.

P

Bardzo często w zastosowaniach odcinki
brzegu są równoległe do osi układu
współrzędnych. W sytuacji jak na rysunku

A

B

0



y

v

wobec czego powyższe wzory nie
mają zastosowania.

l

.

,

P

A

x

y

A

P

x

x

sv

t

v

y

y

s











Przecięcie odcinka z

półprostą c.d.

Jeśli





|

|

y

v

wtedy możemy uznać, że prosta l i odcinek
[A,B] są równoległe. Przecięcie z brzegiem
jest, jeśli

.

|

)

(

|





A

l

Zwykle przyjmujemy

].

10

,

10

[

8

14









W obliczeniach numerycznych zwykle układ punktów przeskalowywuje
się i przesuwa, tak aby punkty mieściły się w kwadracie K=[0,1]×[0,1]
i tak, żeby kwadrat K był najmniejszy ze wszystkich kwadratów
o bokach równoległych do osi układu współrzędnych spełniających
tą własność.

Przeskalowanie układu

punktów

Niech

.

,

,

1

,

,

},

,

,

1

:

)

,

(

{

}.

,

max{

,

max

,

min

,

max

,

min

},

,

,

1

:

)

,

(

{

min

'

min

'

'

'

'

'

min

max

min

max

1

max

1

min

1

max

1

min

n

i

y

y

y

x

x

x

gdzie

n

i

y

x

P

P

y

y

x

x

y

y

y

y

x

x

x

x

n

i

y

x

P

P

i

i

i

i

i

i

i

i

n

i

i

n

i

i

n

i

i

n

i

i

i

i

































































Podział Dirichleta

.

,

,

,

1

,

j

i

N

i

P

P

m

i

P











Def. Wielościanem Voronoi stowarzyszonym z punktem

m

i

dla

P

i

,

,

1



nazywamy zbiór:

.

)

,

,

,

(

,

||

||

}.

,

,

1

,

||

||

||

||

:

{

2

1

1

2

N

N

N

i

i

j

i

N

i

x

x

x

x

x

x

i

j

m

j

P

x

P

x

x

V



































Lemat: Niech

||}.

||

||

||

:

{

,

,

,

B

x

A

x

x

U

B

A

B

A

N

N



















wówczas U jest hiperpłaszczyzną o normalnej

AB

n

oraz

.

2

U

B

A

C







Dowód

N=3

N=2

A

B

C

C

A

U

U

.

0

||

||

||

||

)

,

(

2

,

)

(

2

,

2

2

,

)

(

)

(

),

,

,

(

),

,

,

(

),

,

,

(

||,

||

||

||

,

2

2

1

2

1

2

1

1

2

1

1

2

1

2

1

1

2

1

2

1

2

1

1

1























































































B

A

AB

x

albo

b

a

b

a

x

czyli

b

b

x

x

a

a

x

x

rozpisaniu

po

b

x

a

x

b

b

B

a

a

A

x

x

x

B

x

A

x

U

x

N

i

i

N

i

i

N

i

i

i

i

N

i

i

N

i

i

i

N

i

i

N

i

i

N

i

i

i

N

i

i

N

i

i

i

N

i

i

i

N

N

N







Lemat c.d.

.

.

.

.

0

)

,

(

,

0

)

,

(

2

,

0

)

,

(

2

,

0

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

2

,

0

)

,

(

)

,

(

)

,

(

)

,

(

2

,

0

)

,

(

)

,

(

)

,

2

(

2

)

,

(

2

,

0

||

||

||

||

)

,

(

2

)

,

(

2

)

,

(

2

,

,

2

,

2

2

d

n

c

n

CX

AB

CX

AB

CX

czyli

B

B

A

A

B

B

B

A

B

A

A

A

AB

CX

B

B

A

A

A

B

B

A

AB

C

X

B

B

A

A

AB

B

A

AB

C

X

B

A

n

C

n

C

AB

X

mamy

U

C

B

A

C

AB

n

Niech

































































Własności wielościanów

Voronoi

Własności wielościanów
Voronoi

Własności wielościanów

Voronoi

||}.

||

||

||

:

{

)

(

},

{

},

,

,

1

:

{

,

1

j

i

k

i

j

j

N

i

i

P

x

P

x

x

V

i

k

k

i

P

P

































Wzór ten wynika
bezpośrednio z definicji.

i

V

ii)

(

- są zbiorami otwartymi,



k

j

N

j

V

iii

1

_

,

)

(







Dowód: na pewno



k

j

N

j

V

1

_

,







wykażemy, że



k

j

N

j

V

1

_

,







niech

||},

||

,

||,

min{||

||

||

,

1

,

1

k

i

N

P

x

P

x

P

x

k

i

i

x





















wówczas

k

j

P

x

P

x

j

i

,

,

1

||,

||

||

||













stąd

.

N

x 



c.n.d.

Własności wielościanów

Voronoi

(iv) Brzeg wielościanu Voronoi składa się z części hiperpłaszczyzn
wyznaczonych przez przecięcia z częściami półprzestrzeniami
przestrzeni n-wymiarowej.

A

B

)

(

_

_

B

A

A

B

B

A

















||}

||

||

||

:

{

,

1

j

i

k

i

j

j

N

i

P

x

P

x

x

V



















||}

||

||

||

:

{

j

i

N

P

x

P

x

x

A













Własności wielościanów

Voronoi

(v)

.

,

j

i

V

V

i

i











Dowód: Hipoteza

.

||,

||

||

||

||

||

||

||

j

i

P

x

P

x

P

x

P

x

V

x

V

x

V

V

x

i

j

j

i

j

i

j

i

































Co prowadzi do sprzeczności. C.n.d.

(vi)



i

V

wypukłe.

Dowód:

},

0

)

,

(

:

{

,

1













n

Cx

x

H

H

V

N

j

k

j

j

i



C

n

niech

.

.

.

.

0

)

,

(

)

,

(

0

)

,

(

,

0

)

,

(

.

0

,

,

1

,

0

)

,

(

,

0

)

,

(

,

d

n

c

n

Cy

n

Cx

n

Cy

n

Cx

n

Cy

n

Cx

H

y

x

j









































Układy punktów w

przestrzeni a

„wędrująca kula”

Tw. Z)

N

N

P

P

P





,

,

,

1

0



Układ punktów nie

leżących na jednej hiperpłaszczyźnie.
T) Istnieje dokładnie jedna sfera przechodząca
przez te punkty.

Dowód:Szukamy punktu X, który spełnia:

.

,

,

1

||,

||

||

||

0

N

i

P

X

P

X

i











)].

,

(

)

,

[(

2

1

)

,

(

),

,

(

)

,

(

)

,

(

2

),

,

(

)

,

(

2

)

,

(

)

,

(

)

,

(

2

)

,

(

),

,

(

)

,

(

0

0

0

0

0

0

0

0

0

0

0

P

P

P

P

X

P

P

P

P

P

P

P

P

X

P

P

P

X

X

X

P

P

P

X

X

X

P

X

P

X

P

X

P

X

i

i

i

i

i

i

i

i

i

i

i































Układy punktów w

przestrzeni a

„wędrująca kula” c.d.

W postaci macierzowej:

.

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

2

1

)

(

)

(

)

(

0

0

0

0

2

2

0

0

1

1

2

1

0

2

0

1

0





















































































P

P

P

P

P

P

P

P

P

P

P

P

x

x

x

P

P

P

P

P

P

N

N

N

T

N

T

T







Na podstawie lematu układ wektorów

N

P

P

P

P

P

P

0

2

0

1

0

,

,

,



jest układem liniowo niezależnym co oznacza, że macierz tego
układu jest nieosobliwa. C.n.d.

Układy punktów w

przestrzeni a

„wędrująca kula” c.d.

Lemat:

część wspólna dwóch przecinających się sfer zawiera się

w jednoznacznie wyznaczonej płaszczyźnie.

2

O

1

O

x

Dowód: Punkt wspólny x leżący na przecięciu
obu sfer spełnia:

,

||

||

,

||

||

2

2

2

2

2

1

2

1

r

O

x

r

O

x









,

)

,

(

)

,

(

2

)

,

(

,

)

,

(

)

,

(

2

)

,

(

2

2

2

2

2

2

1

1

1

1

r

O

O

O

x

x

x

r

O

O

O

x

x

x













Po odjęciu stronami:

,

||

||

||

||

)

,

(

2

2

1

2

2

2

1

2

2

2

1

r

r

Q

Q

O

O

x









czyli

.

||

||

||

||

)

,

(

2

2

1

2

2

2

1

2

2

2

1

Q

Q

r

r

O

O

x













c.n.d.

I twierdzenie Delaunay’a

Z) (i)







1

}

{

i

i

T

T

rodzina sympleksów dzielących

,

N



to znaczy

.

1

_



















j

i

i

i

N

T

T

j

i

oraz

T



(ii) Dowolny zbiór ograniczony ma część wspólną tylko ze
skończoną liczbą sympleksów z

.

T

(ii) Niech







1

}

{

i

i

P

P

będzie zbiorem wszystkich punktów

sympleksów rodziny

.

T

Niech

i

T

K

oznacza kulę przechodzącą przez wszystkie wierzchołki

danego sympleksu

.

N

i

T





T)

i

T

j

i

K

P

T

T

,

, 



nie zawiera wierzchołków w swoim wnętrzu i

odwrotnie

j

T

i

T

j

i

j

i

K

sympleks

wymiarowy

n

T

T

j

i

T

T

}

1

{

,













nie zawiera wierzchołków

j

T

w swoim wnętrzu i odwrotnie.

I twierdzenie Delaunay’a

c.d.

Spełnione założenia
tw. Delaunay’a

Nie spełnione założenia
tw. Delaunay’a

Def. Układ punktów
nazywamy układem osobliwym, jeśli k>N+1 oraz wszystkie jego
punkty należą do jednej sfery w

N

k

P

P

P

P

S









}

,

,

,

{

2

1



.

N



Przykład N=1

N

P

P

P

P

P

S









}

,

,

,

{

3

2

1

0

Konstrukcja

triangularyzacji

Delaunay’a

Def. Zbiór punktów

N

P 



nazywamy osobliwym jeśli istnieje

osobliwy podukład

.

P

S

1. Startujemy z dowolnego punktu

.

k

P

2. Znajdujemy punkt

m

P

leżący na okręgu

o środku

k

P

I nie zawierający wewnątrz innego
punktu z P.

3. Znajdujemy punkt

s

P

leżący okręgu przechodzącym przez

m

P

,

k

P

nie zawierający w swoim wnętrzu innych punktów.

Konstrukcja

triangularyzacji

Delaunay’a N=2 c.d.

4. Konstruujemy trójkąt o wierzchołkach

.

,

,

s

m

k

P

P

P

5. Startujemy z dowolnego boku tego tego trójkąta. Prowadzimy
okrąg przechodzący przez końce tego boku i punkt SP, tak aby

ten okrąg nie zawierał w swoim wnętrzu innych punktów z P.

6. Proces kontynuujemy aż do wyczerpania punktów.