Module 7 : Géométrie algorithmique

23/7/2007 Géométrie algorithmique 2

Plan du module Aire d’un triangle Problème 361

23/7/2007 Géométrie algorithmique 3

Aire d’un triangle Dans espace 2D

2 ( ( ))

( ( )) ( )( ) ( )( )

v v

w w

B A B AB A C A C A B A

C A C A

AB AC Aire ABC

x yv w

x y

x x y yAire ABC x x y y x x y y

x x y y

����������������������������

������������� � AB

C

23/7/2007 Géométrie algorithmique 4

Aire d’un triangle Avantages :

Calcul efficace Signe de l’aire :

> 0 si C est à gauche de AB (counterclockwise) < 0 si C est à droite de de AB (clockwise) = 0 si colinéaires

23/7/2007 Géométrie algorithmique 5

Distance Distance entre deux points A et B

2 2( ) ( )A B A Bd x x y y

23/7/2007 Géométrie algorithmique 6

Aire d’un polygone convexe La surface d’un polygone convexe est

donnée par la formule :

1

1 10

1( ) ( )

2

n

i i i ii

A p x y x y

23/7/2007 Géométrie algorithmique 7

Convex Hull

Po

P1

P3

P10

P12

P11

P9

P6

P7

P8

P5

P4

P2

23/7/2007 Géométrie algorithmique 8

Convex Hull – Graham scan

Po

P1

P3

P10

P12

P11

P9

P6

P7

P8

P5

P4

P2

23/7/2007 Géométrie algorithmique 9

Convex Hull – Graham scan As shown, Graham’s

scan starts from a point (p0) and calculates all the angles it makes to all the points and sorts the angles in polar order

23/7/2007 Géométrie algorithmique 10

Convex Hull – Graham scan It selects the point

with the least angle and starts traversing (P0-P1).

Then P1 to P2 From P2 to P3 it

realizes that it takes a right turn, so it backtracks and selects P1 – P3 directly, otherwise polygon not convex

23/7/2007 Géométrie algorithmique 11

Convex Hull – Graham scan The algorithm

continues, based on the above mentioned conditions till it reaches back to the initial point. Hence forming the Convex Hull as shown:

23/7/2007 Géométrie algorithmique 12

Convex Hull – Graham scan

23/7/2007 Géométrie algorithmique 13

Convex Hull – Graham scan

23/7/2007 Géométrie algorithmique 14

Convex Hull – Graham scan Once the initial point

is reached the algorithm self terminates, and the Convex Hull is formed.