Что не так с моей функцией сканирования Грэма?

Я почти закончил третью главу Real World Haskell. Последнее упражнение блокирует меня. Мой код вылетит во время работы. Кто-нибудь может сказать мне, какая часть неверна в моем коде? Спасибо.

Вопрос: Используя код из предыдущих трех упражнений, реализуйте алгоритм сканирования Грэма для выпуклой оболочки набора двумерных точек. Вы можете найти хорошее описание того, что такое выпуклая оболочка и как должен работать алгоритм сканирования Грэма, в Википедии.

Отвечать:

-- Graham Scan, get the convex hull.
-- Implement the algorithm on http://en.wikipedia.org/wiki/Graham_scan

import Data.List
import Data.Ord

data Direction = TurnLeft | TurnRight | GoStraight deriving (Eq, Show)

-- Determine if three points constitute a "left turn" or "right turn" or "go straight".
-- For three points (x1,y1), (x2,y2) and (x3,y3), simply compute the direction of the cross product of the two vectors defined by points (x1,y1), (x2,y2) and (x1,y1), (x3,y3), characterized by the sign of the expression (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1). If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn", otherwise a "right turn".
direction a b c = case compare ((x2 - x1) * (y3 - y1)) ((y2 - y1) * (x3 - x1)) of
    EQ -> GoStraight
    GT -> TurnLeft
    LT -> TurnRight
    where   x1 = fst a
            y1 = snd a
            x2 = fst b
            y2 = snd b
            x3 = fst c
            y3 = snd c

grahamScan points = scan (sort points)
            -- For each point, it is determined whether moving from the two previously considered points to this point is a "left turn" or a "right turn". If it is a "right turn", this means that the second-to-last point is not part of the convex hull and should be removed from consideration. This process is continued for as long as the set of the last three points is a "right turn". As soon as a "left turn" is encountered, the algorithm moves on to the next point in the sorted array. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.)
    where   scan (a : (b : (c : points)))
                | (direction a b c) == TurnRight    = scan (a : (c : points))
                | otherwise                         = a : (scan (b : (c : points)))
            scan (a : (b : []))                     = []
            -- Put prime to the head.
            sort points                             = prime : (reverse (sortBy (compareByCosine prime) rest))
                        -- Sort a list to compute. The first step is to find a point whose y-coordinate is lowest. If there are more than one points with lowest y-coordinate, take the one whose x-coordinate is lowest. I name it prime.
                where   compareByYAndX a b
                            | compareByY == EQ  = comparing fst a b
                            | otherwise         = compareByY
                            where   compareByY  = comparing snd a b 
                        prime                   = minimumBy compareByYAndX points
                        -- Delete prime from the candidate points. Sort the rest part by the cosine value of the angle between each vector from prime to each point. Reverse it and put prime to the head.
                        rest                    = delete prime points
                        compareByCosine p a b   = comparing cosine pa pb
                            where   pa          = (fst a - fst p, snd a - snd p)
                                    pb          = (fst b - fst p, snd b - snd p)
                                    cosine v    = x / sqrt (x ^ 2 + y ^ 2)
                                        where   x = fst v
                                                y = snd v

person Sieg    schedule 05.06.2011    source источник
comment
Не могли бы вы дать более подробную информацию о том, как код терпит неудачу? Сообщение об ошибке, бесконечный цикл, ...? Возможно, образец ввода и ожидаемый результат. Просто сделайте так, чтобы нам было легко воспроизвести проблему.   -  person luqui    schedule 05.06.2011
comment
Просто примечание к стилю: вам действительно следует писать (x1,x2) = a и т. д. в предложениях where вместо использования fst и snd.   -  person Landei    schedule 05.06.2011
comment
@Landei, или просто direction (x1,y1) (x2,y2) (x3,y3) = ...   -  person luqui    schedule 05.06.2011
comment
Это не сбой, это просто дает неверные ответы (для моих тестов). Возможно, вам следует переформатировать код, чтобы другие могли его прочитать (устранить вложенные предложения where и добавить сигнатуры типов) в дополнение к перефразировке вопроса.   -  person Thomas M. DuBuisson    schedule 05.06.2011
comment
Я даже не знал, что вы можете делать вложенные where.   -  person MatrixFrog    schedule 02.08.2011


Ответы (1)


Когда вы выполняете сканирование на отсортированном наборе точек, когда вы закончите, вы отбрасываете точки, которые должны быть в корпусе. В этой строке

scan (a : (b : [])) = []

вы удаляете последние две точки в корпусе. На самом деле это должно быть

scan (a : (b : [])) = [a, b]

или даже лучше,

scan ps = ps

который охватывает случаи только с одной точкой.

person gereeter    schedule 02.11.2011