0votos

Test rápido de intersección entre dos únicos círculos (II) en Haskell

por josejuan hace 5 años

Sabiendo lo lejos que están los círculos y el incremento máximo por iteración, podemos eliminar el test para cierto número de iteraciones. La proporción de iteraciones eliminadas en la práctica indicarán si es mejor aplicar esta estrategia o las del desafío I.

Igual que el desafío (I) pero además se sabe que los círculos no pueden moverse más de D distancia en cada iteración.

1
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
{- 
 
  Si la suma de los radios de los círculos es `rr`, el 
  incremento máximo que pueden desarrollar las posiciones 
  de los círculos por iteración, multiplicada por dos, es 
  `dd` y la distancia actual entre los círculos es `d`, 
  entonces, hasta que no pasen 
 
        i = (d - rr) / dd 
 
  iteraciones, podemos estar seguros que no habrá colisión. 
 
  Así, si el número de iteraciones en que los círculos no 
  colisionan es lo suficientemente elevado (determinado por 
  el coste relativo del cómputo de `i`) la siguiente 
  estrategia mejora el rendimiento. 
 
-} 
 
testCircleCircle (x1, y1) (x2, y2) rr dd i = 
  if i >= 1 
    then (False, i - 1) 
    else (d <= rr, (d - rr) / dd) 
  where d = sqrt $ (x1 - x2)^2 + (y1 - y2)^2 
 
{- 
 
  Aunque yo estoy usando `sqrt` realmente, dependiendo del contexto 
  (tipo de procesador, uso de enteros o coma fija, etc...) se usaría 
  una versión rápida de `sqrt` (¡pero debe dar un valor exacto o 
  cota inferior!). 
 
  Ésto no obstante no siempre será más eficiente que el uso de `sqrt`. 
 
  Ejemplos de `sqrt` rápidas en 
 
  http://stackoverflow.com/questions/1100090/looking-for-an-efficient-integer-square-root-algorithm-for-arm-thumb2 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.