- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 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
--Поиск минимальной выпуклой оболочки
import Data.List; import Data.Ord
--общие функции и типы
data Point = P{x::Float,y::Float}
deriving (Show,Eq)
getRotate a b c = baX * cbY - baY * cbX
where baX = x b - x a; baY = y b - y a;
cbX = x c - x b; cbY = y c - y b;
sortFunc a b c
|k < 0 = LT
|k == 0 = compare (long a c) (long a b)
|k > 0 = GT
where k = getRotate a b c
long a b = (x b - x a)*(x b - x a) + (y b - y a)*(y b - y a)
getLeftPoint = minimumBy (comparing x)
--Джарвис
getMBOJarvis l = mboJ fp l fp
where fp = getLeftPoint l
mboJ current list fp
|getRotate current next fp > 0 = []
|True = current : mboJ next listWOC fp
where listWOC = filter ((/=)current) list;
next = minimumBy (sortFunc current) listWOC;
--Грехем
getMBOGragam = tail.throwGraham.sortGraham
sortGraham list = fp:sortBy (sortFunc fp) list
where fp = getLeftPoint list
throwGraham (f:s:t) = mboG (s:f:[]) t
mboG fs@(f:s:st) sn@(h:t)
|sortFunc s f h == GT = mboG (s:st) sn
|True = mboG(h:fs) t
mboG fs@(f:st) sn@(h:t) = mboG(h:fs) t
mboG l [] = l
--тесты
testList1 = [P 0 (-1), P (-1) 0, P 0 1,P 1 0,P (-0.5) (-0.5),P 0.5 (-0.5),P (-0.5) 0.5,P 0.5 0.5,P 0 0]
testList2 = [P 0 0, P 1 0, P 0 1,P 2 0,P 1 1,P 0 2,P 2 1,P 1 2,P 2 2]
testJ1 = mapM_ print $ getMBOJarvis testList1
testG1 = mapM_ print $ getMBOGragam testList1
testJ2 = mapM_ print $ getMBOJarvis testList2
testG2 = mapM_ print $ getMBOGragam testList2
Follow us!