Sympleksy

Niech P

0

,P

1

,…,P

N

będzie układem n+1

punktów w n-wymiarowej przestrzeni

Euklidesowej i nie leżących na jednej

hiperpłaszczyźnie.

Def. Sympkleksem określonym na zbiorze

punktów P

0

,P

1

,…,P

N

nazywamy zbiór:

}.

0

,

1

:

{

0

0

1

0



















i

i

n

i

i

i

n

i

n

P

P

P

P

P

S









n=2

0

P

1

P

2

P

Tw. Sympleks S jest

zbiorem wypukłym.

Dw. Niech

i

i

n

i

i

i

n

i

P

y

P

x





0

0

,













należy sprawdzić, że

.

1

0

,

)

1

(

















S

y

x

















)

)

1

(

(

)

1

(

0

i

i

i

i

n

i

P

P

y

x













,

]

)

1

(

[

0

i

i

i

n

i

P



























]

)

1

(

[

0

i

i

n

i









,

1

1

)

1

(

1

)

1

(

0

0

































i

n

i

i

n

i

.

0

)

1

(







i

i









c.n.d.

Tw. Zbiór

}

0

,

1

:

{

0

0















i

i

n

i

i

i

n

i

P

S







jest obwiednią wypukłą

zbioru punktów

}.

,

,

,

{

1

0

n

P

P

P

P





Dowód:

 

.

1

,

,

,

1

,

0

,

0

,

,

0

















i

k

k

k

n

k

i

i

k

n

k

dla

P

P

P

con

K









S

K

czyli

S

P





Zał. indukcyjne:



























P

K

P

i

k

i

i

i

k

i

i

i

k

i









1

0

1

0

1

0

,

0

,

1

,

Rozważmy

.

0

,

1

,

0

0















i

i

k

i

i

i

k

i

K

P







,

1

1

1

0

1

1

0























k

k

i

i

k

i

k

k

i

i

k

i

P

P

P

P













,

1

1

0







i

k

i





,

0

,

0















i

k

i

gdzie

,

1

1







k





Ponieważ K wypukły

.

1

1

0

K

P

k

i

i

k

i





















c.n.d.

Twierdzenie o

niezależności układu

wektorów

Tw. Układ wektorów

}

,

,

,

{

0

2

0

1

0

n

P

P

P

P

P

P



jest liniowo

}

,

,

,

{

1

0

n

P

P

P



nie leży na jednej hiperpłaszczyźnie.

Dowód: Hip

.

0

,

0

,

1

0

1

2



















n

i

i

i

n

i

i

i

P

P







W postaci macierzowej:

.

0

,

0

)

,

,

,

(

,

0

2

1













n

H

n

u

gdzie

Hu

T

n













,

0

,

,

,

0

2

0

1

0



n

P

P

P

P

P

P

czyli

T

n



to oznacza, że punkty

n

i

P

i

,

,

1

,

0

,





należą do hiperpłaszczyzny:

.

0

)

,

(

:

0





n

X

P

c.n.d.





,

,

,

,

0

2

0

1

0

n

P

P

P

P

P

P

H





niezależny, jeśli układ punktów

Uwaga:

0

P

1

P

2

P

.

1

,

1

0

1

0

2

1

1

0

0



















P

P

P

Równanie odcinka

]

,

[

1

0

P

P

N=2

N=3

0

P

1

P

2

P

3

P

.

1

,

1

0

3

1

0

3

3

2

1

1

0

0



























P

P

P

P

Powyższe równanie spełniają punkty ścianki przechodzącej
Przez punkty

.

,

,

3

1

0

P

P

P

Natomiast równanie

1

,

1

0

0

1

0

3

2

1

1

0

0





















P

P

P

P

jest równaniem krawędzi

.

,

1

0

P

P

Analogicznie dla pozostałych
ścianek i krawędzi.

Współrzędne

barycentryczne

Def. Jeśli











n

i

i

n

i

i

to

P

P

P

S

P

P

0

1

0







nazywamy współrzędnymi

barycentrycznymi punktu P.

Tw. Współrzędne barycentryczne dowolnego punktu w przestrzeni
n-wymiarowej wyznaczone są w sposób jednoznaczny.





















n

i

i

n

i

i

i

n

i

i

P

X

Dw

1

0

0

0

1

,

1

,

.









.

,

)

1

(

0

0

1

0

0

1

0

1

P

P

P

P

P

P

P

P

P

X

i

i

n

i

i

i

n

i

i

i

n

i

i

































czyli

,

0

1

0

X

P

P

P

n

i

i

i









albo w postaci macierzowej:





.

,

,

0

1

0

1

0

X

P

P

P

P

P

n

n































Na podstawie poprzedniego tw.
macierz tego układu jest nieosobliwa
zatem istnieje dokładnie jedno
rozwiązanie.

Współrzędne

barycentryczne c.d

.

Uwaga: Każdy punkt

n

X





może być jednoznacznie wyrażony

poprzez liniową kombinację

.

0





n

i

i

i

P



Punkt należy do sympleksu,

jeśli dla każdego i

,

0



i



punkt leży na brzegu, jeśli

.

0

0







k

i

oraz





Punkt leży na zewnątrz sympleksu, jeśli

przynajmniej jedno

.

0



i



Przykład N=2

)

,

(

)

,

(

)

,

(

)

,

(

2

2

2

1

1

1

0

0

0

y

x

X

y

x

P

y

x

P

y

x

P













,

,

0

2

1

2

0

1

0

X

P

P

P

P

P



















.

,

0

,

0

2

1

0

2

0

1

,

0

2

,

0

1



















































y

y

x

x

y

y

y

y

x

x

x

x





0

P

1

P

2

P

X

Współrzędne

barycentryczne c.d

.

0

P

1

P

2

P

3

P

X

Współrzędne barycentryczne c.d

.

Przykład N=3

,

)

,

,

(

)

,

,

(

)

,

,

(

)

,

,

(

)

,

,

(

3

3

3

3

2

2

2

2

1

1

1

1

0

0

0

0











































z

y

x

X

z

y

x

P

z

y

x

P

z

y

x

P

z

y

x

P





.

,

,

0

3

2

1

3

0

2

0

1

0

X

P

P

P

P

P

P

P





























.

1

3

2

1

0

















Jeśli

,

0

,

0

,

0

,

0

3

2

1

0

















wówczas punkt X leży we

wnętrzu sympleksu,
jeśli

,

0

,

0

,

0

,

0

3

2

1

0

















wtedy punkt

wewnątrz ścianki

.

3

2

1

P

P

P

Analogicznie jest przy zerowaniu się

kolejnych współrzędnych barycentrycznych. Jeśli na przykład

,

0

,

0

,

0

,

0

3

2

1

0

















wtedy punkt X leży na krawędzi

.

3

2

P

P

W przypadku, kiedy

0

3

1









k

k



punkt X leży na zewnątrz
czworościanu.

Ścianki sympleksu

Def. Ścianką (krawędzią) wymiaru

n

k 



0

sympleksu

n

P

P

P

S



1

0



nazywamy zbiór:

}.

0

,

1

:

{

0

0

1

0

















j

k

j

k

j

j

i

j

i

i

i

j

k

P

P

P

P

P









Dla ścianek (krawędzi) sympleksu S zachodzi następujący wzór:

.

1

0

1

0

0

}

,

,

,

{

k

k

i

i

i

n

k

i

i

i

P

P

P

S



 



 





}

,

,

,

{

1

0

k

i

i

i







jest k+1- elementową kombinacją
ze zbioru {0,1,…,n}.

Przykład N=2

0

P

1

P

2

P

}

{

}

{

}

{

}

{

}

{

}

{

}

{

2

1

0

2

1

2

0

1

0

2

1

0

3

0

}

,

,

,

{

1

0

1

0

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

S

k

k

i

i

i

k

i

i

i



















 



 





Przykład N=3

0

P

3

P

2

P

1

P

}.

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

3

2

1

0

3

2

1

3

2

0

3

1

0

2

1

0

3

2

3

1

2

1

3

0

2

0

1

0

3

2

1

0

3

0

}

,

,

,

{

1

1

0

0

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

P

S

k

k

i

i

k

i

i

i

i

































 













.

4

)!

3

4

(

!

3

!

4

3

4

,

6

)!

2

4

(

!

2

!

4

2

4





































Przykład N=4

.

5

)!

4

5

(

!

4

!

5

4

5

.

10

)!

3

5

(

!

3

!

5

3

5

,

10

)!

2

5

(

!

2

!

5

2

5























































Podział symplicjalny

Def. Podziałem symplicjalnym nazywamy taki podział sympleksu

N

P

P

P

S



1

0



poprzez rodzinę sympleksów, która

pokrywa S i w której każde dwa sympleksy są rozłączne.

Def. Środkiem ciężkości sympleksu nazywamy punkt:

).

(

1

1

)

(

1

0

N

P

P

P

N

S

b













Niech

k

i

i

i

i

P

P

P

S



1

0



oraz

l

j

j

j

j

P

P

P

S



1

0



Def. Mówimy, że

}.

,

,

,

{

}

,

,

,

{

1

0

1

0

l

k

j

j

j

i

i

i

df

j

i

P

P

P

P

P

P

S

S











Twierdzenie o podziale

symplicjalnym

Rodzina sympleksów postaci

),

(

)

(

)

(

1

n

S

b

S

b

S

b



oraz

,

1

0

n

S

S

S

S











stanowi podział symplicjalny

sympleksu S.

N=2

0

P

1

P

2

P

2

1

0

1

0

0

P

P

P

P

P

P





3×2=6

N=3

4×6=24

3

2

1

0

2

1

0

1

0

0

P

P

P

P

P

P

P

P

P

P







Podział symplicjalny

N=2,3

Niech

).

,

,

(

)

,

,

,

(

1

0

,

1

0

k

i

i

i

df

k

P

P

P

b

i

i

i







N=2

N=3

(0,1,2)

(0,1)

(0,2) (1,2)

(0)

(1)

(2)

(0)

(2) (1)

(0,1,2,3)

(0,1,2) (0,1,3) (0,2,3)(1,2,3)

(0,1)

(0,2) (1,2)

(0)

(0)

(2)(1) (2)

Z każdego węzła „wychodzą”
kombinacje o 1 krótsze niż
węźle.

(1)

Przecinanie się prostej z

odcinkiem

W wielu zagadnieniach geometrii obliczeniowej istnieje potrzeba
roztrzygnięcia, czy dana prosta przecina dany odcinek bez potrzeby
wyznaczania tego punktu.

A

B

A

B

L(X)=0

L(X)=0

L(A)L(B)<0

L(A)L(B)>0

Jeśli

L(A)L(B)<0, wówczas odcinek przecina prostą, jeśli

L(A)L(B)>0,

wtedy odcinek i prosta nie przecinają się.

Przecinanie się odcinka z

hiperpłaszczyzną

(płaszczyzną)

Równanie hiperpłaszczyzny w

.

0

)

,

(

)

(

:









n

dX

X

N

d

n

X

A

B

Jeśli

,

0

)

(

)

(







B

A

wówczas odcinek [A,B] nie przecina
hiperpłaszczyzny.

Jeśli natomiast

,

0

)

(

)

(







B

A

wtedy odcinek [A,B] przecina
hiperpłaszczyznę.

A

B

Przecinanie się dwóch

odcinków

A

B

C

D

A

C

D

B

A

B

C

D

Odcinki [A,B] oraz [C,D] nie przecinają, jeżeli punkty A, B leżą po
jednej stronie prostej przechodzącej przez punkty C, D

lub

punkty C, D leżą po jednej stronie prostej przechodzącej
przez punkty A, B.

W postaci matematycznej:

0

)

(

)

(

0

)

(

)

(







D

L

C

L

B

L

A

L

AB

AB

CD

CD

Uwaga

Jeśli któreś z końców dwóch odcinków pokrywają się,
wówczas uznanie czy te odcinki przecinają się, czy też nie
zależy od dziedziny zastosowania. W strukturach danych
współrzędne punktów zapamiętywane są jako zmienne
rzeczywiste, odcinek zaś jest reprezentowany jako para
zmiennych całkowitych. Ponieważ w programie komputerowym
łatwo jest porównywać zmienne całkowite niż rzeczywiste
wobec tego przy badaniu przecięć odcinków należy najpierw
sprawdzić, czy indeksy końców pokrywają się.

Triangularyzacja układu

punktów

.

}

,

,

,

{

1

0

j

i

N

n

P

P

P

P

P

T











Def. Zbiór sympleksów (trójkątów)

T

N

i

i

T

1

}

{



W przestrzeni

N-wymiarowej nazywamy triangularyzacją układu punktów, jeśli:

(i)







T

N

i

i

T

1

_

jest zbiorem wypukłym,

(ii) Wszystkie wierzchołki wszystkich sympleksów są elementami
zbioru punktów

,

P

(iii) Każdy

i

P

jest wierzchołkiem przynajmniej jednego z

sympleksów

.

1

n

k

T

k





(iv)









j

i

T

T

j

i

.

Triangularyzacja układu

punktów

triangulacja

inna triangulacja

A

C

B

Uwarunkowanie trójkąta

.

||

||

||

||

||

||

)

(

3

4

)

(

2

2

2

AC

BC

AB

ABC

pole

ABC













źle uwarunkowany trójkąt

Uwarunkowanie trójkąta

Tw. Współczynnik uwarunkowania trójkąta spełnia nierówność

1

)

(

0







ABC



oraz przyjmuje wartość 1dla trójkąta równobocznego.

A

B

C

x

y





Z rysunku

h

.

,

,

a

y

x

tg

y

h

tg

x

h













Po kolejnych przekształceniach:

).

,

(

)

,

(

)

(











f

funkcja

ABC







Warunek konieczny ekstremum funkcji wielu zmiennych:

.

60

0

,

0

0



























f

f

Wielokąty monotoniczne

Jednym ze sposobów triangularyzacji wielokąta mogłoby być
podzielenie go na tak zwane wielokąty monotoniczne.
a w szczególności wypukłe.

Def. Wielokąt prosty nazywamy momnotonicznym ze względu na
prostą l jeśli dla każdej prostej m prostopadłej do l zbiór

P

m

jest zbiorem spójnym (czyli odcinkiem, punktem bądź zbiorem
pustym).

l

P

Uwaga: Każdy wielokąt wypukły
jest monotoniczny ze względu
na każdą prostą.

Wielokąty monotoniczne

Def. Wielokąt monotoniczny ze względu na oś y (x) nazywamy
y-monotonicznym (x-monotonicznym).

Uwaga: Następująca cecha jest charakterystyczna dla
y-monotonicznych wielokątów:
Jeśli posuwamy się z najwyższego do najniższego wierzchołka
przez lewą lub prawą część brzegu to zawsze posuwamy się
w dół lub poziomo, ale nigdy w górę.

Def. Przekątną wielokąta nazywamy odcinek łączący dwa
wierzchołki i leżący wewnątrz tego wielokąta

.

Triangularyzacja

monotonicznych

wielokątów

Załóżmy, że P jest y-monotoniczny . Uporządkujmy punkty zbioru
P względem współrzędnej y. dla celów roboczych przyjmijmy stos
S, który na początku będzie zbiorem pustym. W trakcie realizacji
będzie zawierał te wierzchołki, z których można poprowadzić
przekątne, poczynając od najwyższego wierzchołka.

Ta część wielokąta która jest sukcesywnie odcinana
od góry jest już striangularyzowana. Na stosie
pierwszym punktem jest punkt zaznaczony na
kolorowo, wszystkie powyżej są wyrzucone.
Następnym punktem będzie punkt z prawego albo
lewego łańcucha.

Triangularyzacja

monotonicznych

wielokątów

I.

Jeśli punkt jest po lewej stronie

łączymy go z kolejnymi wierzchołkami
z prawego łańcucha. Kształt nie pokrytej
trójkątami części wielokąta będzie
przypominał odwrócony komin to znaczy,
że kąty wewnętrzne będą rozwarte (po odcięciu
trójkątów z ostrymi wierzchołkami).

Punkty, które są całkowicie odcięte przez przekątną są
usuwane ze stosu a dokładane kolejne. Procedura kończy
do wyczerpania wszystkich punktów.

Triangularyzacja

monotonicznych

wielokątów

W drugim przypadku punkt będzie znajdował się po tej samej
stronie łańcucha, pomimo tego jeden z punktów refleksywnych
da się połączyć przekątną z bieżącym punktem stosu.

Przesuwamy się o jeden punkt w dół
jako, że nasz bieżący punkt jest już
połączony z bokiem wielokąta.
Tak wybrany sprawdzamy, czy może
tworzyć przekątną z kolejnymi.
(dwie przekątne koloru czerwonego).
Dalej postępujemy podobnie.