eviter ce genre d'algo trivial & inutilisable mon ami. Reprend l'exemple des max cités + haut, c'est + rapide. Néanmoins ta soluce a le merite de "resoudre" le probleme, des qu'un ordinateur quantique sera dispo (cf la taverne :mouarf: )
Version imprimable
eviter ce genre d'algo trivial & inutilisable mon ami. Reprend l'exemple des max cités + haut, c'est + rapide. Néanmoins ta soluce a le merite de "resoudre" le probleme, des qu'un ordinateur quantique sera dispo (cf la taverne :mouarf: )
?? 8OCitation:
Envoyé par Ulmo
Meme dans le cas d'un losange avec une des 2 diagonales tres petite ?
Ah oui, bonne boulette là !
Ca augmente encore la taille de la recherche, Nemerle ne va pas me rater (et à raison).
Non, je vais te rater ;) mais l'exemple d'un losange n'est pas le bon: prend plutôt un RECTANGLE applati (et même dans ce cas, il existe un cercle "maximal" avec 3 points d'intersection --> celui qui colle à droite ou a gauche)
pas compris :
*pour un rectangle le cercle minimal est celui passant par les 4 sommets, non ? Donc j'ai bien au moins 3 points.
*pour un losange strict (i.e. pas carré), le cercle minimal sera centré sur le centre de symétrie du losange, et ne passera que par 2 sommets.
Ou voulais-tu dire autre chose ?
Mea culpa, j'ai inversé le problème dans ma caboche: je cherchais le plus grand cercle inscrit... :fou:
Encore plus simple : 3 points alignés. Là, il n'existe carrément pas de cercle qui passe par les 3 points (sauf si on considère un rayon infini, mais ça commence à faire grand pour un cercle minimal...:aie: )
Bonjour,
j'avais marqué :resolu:, mais j'avais oublié de dire quel algorithme j'avais finalement choisis :
- le vainqueur est donc l'algorithme proposé par PseudoCode avec en plus du code :P
- il fonctionne très bien et surtout très vite.
je voulais rajouter 2 choses :
Code C associé :Citation:
* Algorithm taken from comp.graphics.algorithm
*
*
* The circumscribing circle of a triangle is computed with the following
* formulae :
* Let the three given points be a, b, c. Use _0 and _1 to represent
* x and y coordinates. The coordinates of the center p=(p_0,p_1) of
* the circle determined by a, b, and c are:
*
* A = b_0 - a_0
* B = b_1 - a_1
* C = c_0 - a_0
* D = c_1 - a_1
*
* E = A*(a_0 + b_0) + B*(a_1 + b_1)
* F = C*(a_0 + c_0) + D*(a_1 + c_1)
*
* G = 2.0*(A*(c_1 - b_1)-B*(c_0 - b_0))
*
* p_0 = (D*E - B*F) / G
* p_1 = (A*F - C*E) / G
*
* If G is zero then the three points are collinear and no finite-radius
* circle through them exists. Otherwise, the radius of the circle is:
*
* r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2
*
:DCode:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59