1votos

Determinar si existe o no existe un rectángulo en una nube de puntos en Haskell

por josejuan hace 4 años

Una sencilla con coste O(n^3/2 log n) o O(n^3/2) si se usan hash.

Dada una nube de puntos en el plano, escribir una función que indique si "SI" o si "NO" hay cuatro puntos que forman un rectángulo.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
{- 
- La existencia de un rectángulo en la nube implica que 
- en alguna fila tenemos dos columnas Xi y Xj tales que 
- en alguna otra fila también tenemos dos columnas Xi y 
- Xj. 
- Bastará entonces, para cada fila, calcular todos los 
- pares (Xi, Xj), ir añadiéndolos a un conjunto y en el 
- caso de que ya exista, deducir que hay un rectángulo. 
- ----------------------------------------------------- 
- La estrategia asintóticamente óptima es usar una tabla 
- de hash para acumular los puntos de cada fila, con coste 
-   O(n)            (con media amortizada según hash) 
- en media para cualquier distribución de puntos, cada fila 
- tiene Raíz(n) puntos con Raíz(n) filas, y la operación 
- tanto de chequeo como inserción en el conjunto toma (con 
- tabla hash) O(1), por lo que el número de combinaciones 
- en cada fila serán O(n) como tenemos Raíz(n) filas, el 
- coste final será 
-     O(n^3/2) 
- Por comodidad, aquí símplemente se ordena el conjunto de 
- puntos y agrupa por coordenada, resultando en 
-     O(n^3/2 log n) 
- En un AMD Phenom(tm) II X6 1045T Processor a 2,7GHz una 
- nube de 10e6 puntos toma 2,7 segundos (sin haber rectángulo). 
- Si el conjunto está ordenado (habitual en una aplicación 
- práctica) toma menos de 1 segundo, por lo que esta implementación 
- no es eficiente (debido al uso de listas), aunque es cómoda 
- y sencilla. 
-} 
{-# LANGUAGE BangPatterns, TupleSections #-} 
import qualified Data.Set as Set 
import Data.List.Extra (groupOn) 
import qualified Data.Vector as V 
import qualified Data.Vector.Algorithms.Intro as I 
import Data.Function (on) 
 
 
 
 
containsRectangle :: [(Int, Int)] -> Bool 
containsRectangle = acc Set.empty               -- Partiendo de un conjunto vacío... 
                  . concatMap (comb2 . map snd) -- ...tomamos las combinaciones 2 a 2... 
                  . groupOn fst                 -- ...de las coordenadas X de cada fila. 
                  . fastSortOn fst 
 
  where acc _     [] = False                    -- Si hemos añadido todos, no hay rectángulo 
        acc !s (p:ps) =                         -- Si queda algún par (x1, x2)... 
          if p `Set.member` s                   -- ...y ya había otro (x1, x2) en otra fila... 
            then True                           -- ...tenemos rectángulo. 
            else acc (Set.insert p s) ps        -- Si no, añadimos (x1, x2) y seguimos. 
 
 
 
 
 
-- Devuelve todas las combinaciones tomando dos a dos 
comb2 :: [a] -> [(a, a)] 
comb2 [ ]    = [] 
comb2 [x]    = [] 
comb2 (x:xs) = map (x,) xs ++ comb2 xs 
 
 
-- Ordena un vector de forma más eficiente que la ordenación de listas Data.List.sortBy 
fastSortOn :: Ord b => (a -> b) -> [a] -> [a] 
fastSortOn f = V.toList . V.modify (I.sortBy (compare `on` f)) . V.fromList 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.