[PDF] Les deux points les plus proches





Previous PDF Next PDF



Les deux points les plus proches

distance euclidienne séparant deux points. cisse est comprise entre xmin et xmax. ... permet de « calculer » la racine carrée d'un flottant et.



Distance entre deux points [bs10] - Exercice

1 Distance entre deux points / pgdistance. 1.1 Calcul de la distance. Écrivez un algorithme qui saisit les coordonnées de deux points du plan (x1y1) dans.



Distance entre deux points [bs10] - Exercice

Unisciel algoprog – Distance entre deux points [bs10]. 2. 1 Distance entre deux points / pgdistance. 1.1 Calcul de la distance.



Distance entre deux points [bs10] - Exercice

Unisciel algoprog – Distance entre deux points [bs10]. 2. 1 Distance entre deux points / pgdistance. 1.1 Calcul de la distance.



Distance entre deux points [bs10] - Exercice

Unisciel algoprog – Distance entre deux points [bs10]. 2. 1 Distance entre deux points / pgdistance. 1.1 Calcul de la distance.



NOMBRES RELATIFS I vocabulaire

Deux nombres relatifs qui ne diffèrent que par leur signe sont opposés. Pour calculer la distance entre deux points sur une droite graduée ...



Comment obtenir la distance entre deux points connus en longitude

1 févr. 2019 Connaissant la position de deux points A et B sur une sphère calculer la distance entre eux revient donc à calculer l'abscisse curviligne S ...



Distance entre deux points [bs10] - Exercice

Unisciel algoprog – Distance entre deux points [bs10]. 2. 1 Distance entre deux points / pgdistance. 1.1 Calcul de la distance.



Distance de deux points dans un repère orthonormal

ci-dessus ) et sur les calculs suivants. SAVOIR DEMONTRER QU'UN TRIANGLE EST RECTANGLE. Exemple : Soient dans un repère orthonormal ( O 



1 Dans chaque cas mesure et calcule la distance entre les deux

distance entre les deux points de la droite graduée. 2 Pour chaque cas calcule la distance entre les deux points A et B. ... Nombres et calculs 47.

IMPSI - Option Informatique

Ann´ee 2001, Deuxi`eme TP Caml

Vincent Simonet (http://cristal.inria.fr/~simonet/)

Les deux points les plus proches

Lors de cette s´eance, nous allons nous int´eresser au probl`eme suivant : ´etant donn´e un ensemble de points du plan, indentifier le couple de points les plus proches au sens de la distance euclidienne. Ce type d"algorithme voit son utilit´e dans les transports a´eriens ou maritimes par exemple. Nous repr´esenterons un point en Caml par un couple de flottants(x,y)repr´esentant ses coordonn´ees dans un rep`ere orthonorm´e. L"ensemble des points consid´er´es sera quant `a lui stock´e dans un tableaut. Nous supposerons toujours que tous les couples stock´es danstsont distincts. OO _ __ x 0

1 Une premi`ere solution

Consid´erons deux pointspetp?de coordonn´ees res- pectives (x,y) et (x?,y?). Leur distance euclidienne est donn´ee par la formule?p-p??=p (x-x?)2+ (y-y?)2. IQuestion 1´Ecrivez une fonctiondistqui calcule la distance euclidienne s´eparant deux points. Une m´ethodepermettant de d´eterminer les deux points les plus proches dans un tableautconsiste `a consid´erer successivement tous les couples de points possibles, ce qui peut se faire facilement `a l"aide de deux bouclesfor.

IQuestion 2´Ecrivez une fonctionplus

prochesqui prend pour argument un tableau de pointstet retourne un couple de points((x,y),(x?,y?))situ´es `a une distance minimale l"un de l"autre.

Vous pourrez

- Commencer par cr´eer une r´ef´erenced(initialis´ee par exemple avecdist t .(0) t.(1)) qui contiendra tout au long du d´eroulement de l"algorithme la plus petite dis- tance trouv´ee; ainsi que deux r´ef´erencessietsjconte- nant les indices des points qui permettent d"atteindre cette distance. - Utiliser deux boucles imbriqu´ees pour consid´erer tous les couples de points communs.- Mettre `a jour les trois r´ef´erences `a chaque fois qu"un couple(i,j)tel que?t.(i)-t.(j)?2 Tri d"un tableau Soitt= [|x0;x1;...;xn-1|] un tableau. Triertconsiste `a permuter le contenu des cases du tableautde fa¸con `a ob- x L"algorithme detri par s´electionadopte le principe sui- vant : pourivariant de 0 `an-2, chercher l"indicek≥i de la case de la partie du tableau situ´ee `a droite de la caseicontenant le plus petit ´el´ement; puis permuter le contenu des casesketi. c ?Vincent Simonet 2001 Ce document est distribu´e selon les termes de la GNU Free Documentation License. Par exemple, pour trier le tableau [|4;3;1;2|], on passe par les ´etapes suivantes :[|4;3;1;2|]i= 0k= 2[|1;3;4;2|]i= 1k= 3 [|1;2;4;3|]i= 2k= 3 [|1;2;3;4|]

IQuestion 4´Ecrivez une fonctionswapqui prend

pour argument un tableaut, deux entiersaetbet per- mute le contenu des cases d"indicesaetb. Votre fonction ne cr´eera pas un nouveau tableau, elle se contentera de modifiersur placele tableaut. Elle sera donc de type ?a vect→int→int→unit. IQuestion 5´Ecrivez une fonctionselqui prend pour argument un tableaut; deux entiersaetbet re- tourne l"indice de la case du sous-tableaut.(a)...t.(b) qui contient le plus petit ´el´ement pour l"ordre<. IQuestion 6D´eduisez-en une fonctiontriqui effec- tue le tri d"un tableau. La fonction que vous venez d"´ecrire vous permet de trier un tableau pour la relation d"ordre<. Sur les couples, cet ordre est enCamll"ordre lexicographique. On peut cependant imaginer d"autres relations d"ordre sur des couples, comme par exemple : letordre x (x , y) (x ' , y') = xIQuestion 7Adaptez les fonctionsselettride sorte qu"elle prennent ´egalement en argument une fonction implantant une relation d"ordre (commeordre xou ordre y).

3 Diviser pour r´egner

Nous revenons maintenant `a notre premier probl`eme, d´eterminer parmi un ensemble de points un couple de points situ´es `a une distance minimale. Nous supposons que nous disposons de deux copies de l"ensemble desn points : - un tableautx, tri´e par abscisses croissantes, - un tableauty, tri´e par ordonn´ees croissantes. On posek=n/2 et on consid`ere les deux sous-tableaux t

1= [|t.(0);...;t.(k)|] ett2= [|t.(k+ 1);...;t.(k+ 2)|].

Soitx0un flottant plus grand que les abscisses des points det1et plus petit que les abscisses des points det2. Le plan est divis´e en deux parties : OO x

0Notonsp1= (x1,y1) etp?1= (x?1,y?1) les deux points

quep2= (x2,y2) etp?2= (x?2,y?2) deux points les plus proches danst2. On noted= min(?p1-p?1?,?p2-p?2?). Si deux points du tableautsont `a une distance stricte- ment inf´erieure `adalors n´ecessairement l"un fait partie det1et l"autre det2et ils sont dans la bande d"abscisses [x0-d;x0+d]. OO p1•p?

1•

p? 2 p2 x 0Â ood// IQuestion 8´Ecrivez une fonction qui prend pour ar- gument un tableautyainsi que deux flottantsxmin,xmax et qui s´electionne dans ce tableau les points dont l"abs- cisse est comprise entrexminetxmax. Le r´esultat sera rendu dans un tableautz. Notonstzle tableau des points situ´e dans la bande, ob- tenu grˆace `a un appel `a la fonction pr´ec´edente. Dans chaque tranche de hauteurdde cette bande, il ne peut y avoir plus de 7 points. On en d´eduit que si deux points detzsont `a une distance inf´erieure ou ´egale `adalors ils sont situ´es `a au plus sept cases l"un de l"autre dans le tableautz. OO x 0Â

²²dOO

IQuestion 9´Ecrivez une fonctionplus

proches centre qui prend pour argument le tableautzet retourne le couple de points les plus proches, tels que ces deux points soient situ´es `a au plus 7 cases l"un de l"autre dans le tableautz. Vous pourrez vous inspirer de la fonction plus prochespr´ec´edente. On d´eduit de ce qui pr´ec`ede un algorithme r´ecursif per- mettant de trouver les deux points les plus proches `a partir des deux tableauxtxetty:

1. D´ecouper le tableautxen deux tableauxtx,1et

t x,2de longueur moiti´e.

2. D´eterminerp1= (x1,y1),p?1= (x?1,y?1),p2=

(x2,y2) etp?2= (x?2,y?2) ainsi que la distanced.

3. Calculertz. S"il contient au moins deux points, ap-

pliquer la fonctionplus proches centre`atzpour obtenirp= (x,y) etp?= (x?,y?). 2

4. Retourner le r´esultat, c"est `a dire la paire de points

`a distance minimale parmip1,p?1;p2,p?2etp,p?.IQuestion 10´Ecrivez en appliquant ce proc´ed´e une

nouvelle fonctionplusproches.´Evaluez sa complexit´e en fonction du nombre de points. 3

IMPSI - Option Informatique

Ann´ee 2001, Deuxi`eme TP Caml

Vincent Simonet (http://cristal.inria.fr/~simonet/)

Les deux points les plus proches

Un corrig´e

IQuestion 1On utilise la fonctionsqrtdeCamlquipermet dela racine carr´ee d"un flottant etl"op´erateur??.d"exponentiation.

letdist (x , y) (x " , y") = sqrt ((x-. x")??. 2.0 +. (y-. y")??. 2.0)

IQuestion 2Notre fonction se contente d"envisager

`a l"aide de deux bouclesforimbriqu´ees. La r´ef´erenced contient `a chaque instant la plus petite distance trouv´ee et les r´ef´erencessietsjles indices des deux points la r´ealisant. letplus proches t = letn = vect length t andd = ref ( dist t .(0) t .(1)) andsi = ref 0 andsj = ref 1 in fori = 0to(n-1)do forj = i + 1to(n-1)do ifdist t .( i ) t .( j )IQuestion 4 letswap t a b = letx = t .(a)in t .(a)<-t .(b); t .(b)<-x;

IQuestion 5La r´ef´erencercontient `a chaqueit´eration l"indice de la case contenant le plus petit

´el´ement parmit.(a)...t.(i).

letsel t a b = letr = ref ain fori = a + 1tobdo ift .( i )IQuestion 6 lettri t = letn = vect length tin fori = 0to(n-1)do letk = sel t i (n-1)in swap t i k done;

IQuestion 7

letsel comp t a b = letr = ref ain fori = a + 1tobdo ifcomp t .( i ) t .(! r )thenr := i done; ! r lettri comp t = letn = vect length tin fori = 0to(n-1)do letk = sel comp t i (n-1)in swap t i k done;

IQuestion 8

letselectionne ty x min x max = letn = vect length tyin letresultat = ref [ ]in fori = n-1downto0do ifx min<= fst ty .( i ) && fst ty .( i)<= x max thenresultat := ty .( i ) : : ( ! resultat ) done; vect of list (! resultat )

IQuestion 9Notre fonctionplusprochescentreest

tr`es semblable `a la fonctionplusproches. La seule diff´erence r´eside dans la borne sup´erieure de la boucle index´ee parj: il n"est plus n´ecessaire de poursuivre jusqu"`aj=n-1 mais on peut se limiter `aj= min(n-1,i+ 7). letplus proches centre t = letn = vect length t andd = ref ( dist t .(0) t .(1)) andsolution i = ref 0 andsolution j = ref 1 in fori = 0to(n-1)do forj = i + 1tomin (n-1) ( i + 7)do ifdist t .( i ) t .( j )IQuestion 10 let recplus proches ' tx ty = letn = vect length txin ifn<= 3then( plus proches tx) else begin lettx1 = sub vect tx 0 (n/2) andtx2 = sub vect tx (n/2) (n-n/2) andx0 = fst tx .(n/2-1)in letp1 , p1" = plus proches ' tx1 ty andp2 , p2" = plus proches ' tx2 tyin letp12 , p12" = if( dist p1 p1")<( dist p2 p2") then(p1 , p1") else(p2 , p2") in letd = dist p12 p12 "in lettz = selectionne ty (max (x0-. d) ( fst tx .(0))) (min (x0 +. d) ( fst tx .(n-1))) in ifvect length tz<= 1then(p12 , p12") else begin letp, p" = plus proches centre tzin ifdist p p"