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.