Algorytmy geometryczne

Oznaczenia

•

Punkt

, , ,

•

współrzędne punktu na
płaszczyźnie

,

•

odcinek o początku i końcu
odpowiednio w punktach i

•

wektor o początku i końcu
odpowiednio w punktach i

•

prosta zawierająca punkty i

•

półprosta zaczynająca się w
punkcie p i zawierająca punkt

....

•

okrąg o środku w punkcie

i

promieniu

Podstawowe algorytmy
geometryczne

Problem sprawdzania przynale

ż

no

ś

ci

punktu do wielok

ą

ta

Operacje elementarne

•

Operacje arytmetyczne: dodawanie,
odejmowanie, mnożenie, dzielenie,
pierwiastkowanie, itp

Założenia i uwagi

•

rozważane są obiekty geometryczne na
płaszczyźnie w kartezjańskim układzie
współrzędnych

•

algorytmy powinny realizować jak najmniej
operacji powodujących przybliżenia

Prymitywne algorytmy geometryczne

Algorytm sprawdzania, po której stronie prostej
leży punkt

WarPocz:

Trzy punkty:

, ,

, ,

,

WarKonc:

Odpowiedź na pytanie: Po której stronie

prostej

leży punkt

Punkt leży po lewej stronie prostej

Punkt leży po prawej stronie prostej

Punkty , i są współliniowe

Algorytm

Obliczamy wartość wyznacznika

, , , którego

znak jest równy znakowi sinusa kąta nachylenia
wektora

do wektora

.

, ,

1

1

1

Jeżeli

, ,

0 to sin $ 0 i wówczas punkt

leży po lewej stronie prostej

.

Jeżeli

, , % 0 to sin $ % 0 i wówczas punkt

leży po prawej stronie prostej

.

Jeżeli

, ,

0 to sin $ 0 i wówczas punkt

leży na prostej

.

Algorytm sprawdzania, czy dwa dane punkty leżą
po tej samej stronie prostej

WarPocz: Cztery punkty:

, , , , & ', ( , ,

WarKonc: Odpowiedź na pytanie, czy punkty

a i '

leżą po tej samej stronie prostej

.

Algorytm

Przypomnijmy funkcję znaku liczby:

sgn

+

1 gdy

0

0 gdy

0

.1 gdy % 0

Punkty

& i leżą po tej samej stronie prostej

wówczas, gdy:

/

, , &

/

, ,

Algorytm sprawdzania, czy punkt należy do
odcinka

WarPocz: Trzy punkty:

, , , , ,

WarKonc: Odpowiedź na pytanie , czy punkt czy punkt
r należy do odcinka

.

Algorytm

Jeżeli punkt r należy do odcinka

, to rzuty

prostokątne na osie (

0 i 1) "zawierają się" w

rzutach prostokątnych odcinka

. Wynika stąd, że

należy do odcinka

wtedy i tylko wtedy gdy:

/

, ,

0

oraz

2

2

przy założeniu, że

2

a także

2

2

∧ /

, , )) = 0

przy założeniu, że

( ) ≤ ( )

Algorytm sprawdzania, czy dwa odcinki się
przecinają

WarPocz

: Cztery punkty:

, , , , & ', ( , ,

wyznaczające dwa odcinki:

i

& .

WarKonc:

Odpowiedź na pytanie , czy odcinki

i

&

przecinają się.

Algorytm

Rozwiązanie opiera się na spostrzeżeniu, że dwa
odcinki przecinają się wtedy i tylko wtedy, gdy:

•

punkty i leżą po przeciwnych stronach
prostej

& i punkty & i leżą po przeciwnych

stronach prostej

•

któryś z końców jednego z odcinków należy do
drugiego.

Czyli mamy warunki:

/ 4

, , )5 ≠ / 4

( , , & )5

∧

/ 4

(&, , )5 ≠ / 4

(&, , )5

oraz (jeżeli początek lub koniec jednego z odcinków
należy do drugiego):

/ 4

( , , &)5 = 0

∧

4( ( ) < (&) < ( )

∧

( ) < (&) < ( )5

lub:

/ 4

( , , )5 = 0

∧

4( ( ) < ( ) < ( )

∧

( ) < ( ) < ( )5

lub:

/ 4

(&, , )5 = 0

∧

4 (&) < ( ) < ( )

∧

( & ) < ( )

< ( )5

lub:

/ 4

(&, , )5 = 0

∧

4 (&) < ( ) < ( )

∧

(&) < ( ) < ( ) 5

przy założeniu, że

2

∧

2

w przypadku, gdy punkt

& lub należy do oraz

& %

∧

& %

w przypadku, gdy punkt lub należy do

&

Problem przynależności punktu do wielokąta

WarPocz

: Dany jest ciąg punktów:

7

8

, 7

9

, . . . , 7

;<9

określający n-wierzchołkowy wielokąt

= i taki, że dla

każdego

> 0,1, . . . , . 1 odcinek 7

?

7

? @9

jest

bokiem wielokąta

= (> A 1 jest wyliczane modulo

). Dany jest również punkt .

WarKonc:

Odpowiedź na pytanie, czy punkt należy

do wielokąta

=. Jeżeli punkt leży na boku

wielokąta, to stwierdzamy, że należy do wielokąta

Algorytm

Algorytm rozwiązujący problem przynależności opiera
się na zależności pomiędzy liczbą przecięć dowolnej
półprostej o początku w punkcie , a bokami
wielokąta.

Punkt należy do wielokąta

= wtedy i tylko wtedy,

gdy półprosta

. B przecina boki wielokąta nieparzystą

liczbę razy. Zachodzą przy tym

dwa przypadki

szczególne

:

•

Półprosta

. B przechodzi przez wierzchołek

wielokąta

•

Półprosta

. B zawiera bok wielokąta.

Uwaga !!!

Zanim zaczniemy wyznaczać liczbę punktów przecięcia
półprostej z bokami wielokąta, sprawdzamy, czy punkt

nie zawiera się w którymś z boków wielokąta.

Prosta

. B zawiera bok &

C

&

D

wielokąta. Niech

&

E

&

C

oraz

&

D

&

F

będą bokami sąsiadującymi z bokiem

&

C

&

D

, a

punkty

&

E

i

&

F

będą końcami tych boków. Jeżeli

punkty

&

E

i

&

F

leżą po tej samej stronie prostej

. B,

to przyjmujemy, że liczba punktów przecięcia

. B z

bokami

&

C

&

D

,

&

E

&

C

i

&

D

&

F

wynosi

0. W przeciwnym

razie

przyjmujemy, że liczba ta

wynosi

1.

Prosta

. B zawiera wierzchołek &

G

wielokąta. Niech

&

9

&

G

oraz

&

G

&

E

będą bokami sąsiadującymi z

wierzchołkiem

&

G

, a punkty

&

9

i

&

E

będą końcami

tych boków. Jeżeli punkty

&

9

i

&

E

leżą po tej samej

stronie prostej

. B, to przyjmujemy, że liczba punktów

przecięcia

. B z bokami &

9

&

G

i

&

9

&

G

wynosi

0. W

przeciwnym

razie

przyjmujemy, że liczba ta

wynosi

1.

Ponieważ koszt obliczeń związanych z każdym bokiem i
wierzchołkami n - kąta jest stały,

złożoność

obliczeniowa

sprawdzenia, czy punkt leży w jego

wnętrzu, jest

( ).