[PDF] [PDF] Les deux points les plus proches - Inria

[PDF] La distance entre deux points dans le plan cartésien

La distance entre deux points dans le plan cartésien Étant donné deux points ( x1, y1) La longueur de cette droite représente la distance qui sépare les deux points (x1, y1) et (x2, y2) Il ne s'agit que de calculer d = √(c − a)2 + (d − b)2

[PDF] Les deux points les plus proches - Normale Sup

Considérons deux points p et p de coordonnées res- pectives (x, y) et (x ,y ) Leur distance euclidienne est donnée par la formule p−p = √ (x − x )2 + (y − y )2

[PDF] Distance entre deux points [bs10] - Exercice - Unisciel

points / pgdistance 2 1 1 Calcul de la distance Cet exercice calcule la distance entre deux points du plan ainsi que la cote de chacun des points dans 

[PDF] Les deux points les plus proches - Inria

Considérons deux points p et p de coordonnées res- pectives (x, y) et (x ,y ) Leur distance euclidienne est donnée par la formule p−p = √ (x − x )2 + (y − y )2

[PDF] Distance de deux points dans un repère orthonormal

Calculer AB et AC Calcul de AB : Il est inutile de refaire la démonstration Il suffit d'appliquer la formule Afin d 

[PDF] La distance entre deux points

Pour calculer la distance entre deux points d'une droite graduée, on calcule la différence entre la plus grande abscisse et la plus petite Attention, une distance  

[PDF] Coordonnées - Labomath

la valeur absolue indique la distance entre l'origine et le point en utilisant On considère une droite munie d'un repère (O,I) et deux points A(xA) et B(xB) tels On se propose de calculer la distance AB en utilisant les abscisses de A et de B

[PDF] Calculs topométriques - UPHF

points 1 Calcul gisement et distance entre 2 points 1 1 Conversion Polaire --> Rectangulaire Calcul des coordonnées d'un point M inconnu par la donnée 

[PDF] Ch11 : Nombres relatifs - Calculs 1 Addition 2 Soustraction 3

Déterminer la distance de deux points d'abscisses données 1 Addition Règle ( Nombres ayant le même signe) Pour trouver la somme de deux 

[PDF] ET3 - RESEAUX: Présentation et dimensionnement des installations

[PDF] DONNEES TECHNIQUES

[PDF] Le pH 6 Le dosage des solutions d 'acides et des bases faibles

[PDF] LE SALAIRE

[PDF] Caisse Nationale de l 'Assurance Maladie - Cnamts

[PDF] La mesure de la pauvreté - Insee

[PDF] Pauvreté - Insee

[PDF] Calcul du stock de sécurité dans un contexte de - HEC Montréal

[PDF] La vacance et la mobilité résidentielle

[PDF] Modélisation de la variation annuelle des trafics routiers - Calcul des

[PDF] Électromagnétisme, TD 13 Polytech 'Nice Sophia, CiP 2

[PDF] Méthode de calcul du volume des ouvrages de rétention ou d

[PDF] Jauge d 'une cuve `a Mazout - CultureMath

[PDF] EBE ou EXCEDENT BRUT D 'EXPLOITATION - Fnogec

[PDF] analyse financiere - Free

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"