<commit_before>module Geom where

import Data.List
import Data.Ratio

data Point a = Point { getX :: a
                     , getY :: a
                     } deriving (Eq, Show, Ord)

type PointR = Point Rational
type PointD = Point Double

data Line a = Line { getOrigin :: Point a
                   , getDirection :: Point a
                   } deriving (Eq, Show)

type LineR = Line Rational
type LineD = Line Double

type Polygon a = [Point a]
type PolygonR = Polygon Rational
type PolygonD = Polygon Double

type Segment a = (Point a, Point a)
type SegmentR = Segment Rational
type SegmentD = Segment Double

segmentToLine :: (Num a) => Segment a -> Line a
segmentToLine (a, b) = Line { getOrigin = a
                            , getDirection = b `sub` a
                            }

add, sub :: (Num a) => Point a -> Point a -> Point a
add (Point x1 y1) (Point x2 y2) = Point (x1 + x2) (y1 + y2)
sub (Point x1 y1) (Point x2 y2) = Point (x1 - x2) (y1 - y2)

ort :: (Num a) => Point a -> Point a
ort (Point x y) = Point (-y) x

cross, dot :: (Num a) => Point a -> Point a -> a
cross (Point x1 y1) (Point x2 y2) = x1 * y2 - x2 * y1
dot (Point x1 y1) (Point x2 y2) = x1 * x2 + y1 * y2

lengthSquared :: (Num a) => Point a -> a
lengthSquared (Point x y) = x * x + y * y

getArea :: (Num a) => Polygon a -> a
getArea [] = 0
getArea (origin:points) = sum $ zipWith area points (tail points)
    where area p1 p2 = cross (p1 `sub` origin) (p2 `sub` origin)

getBounds :: (Ord a) => [Polygon a] -> (Point a, Point a)
getBounds polygons = (Point (minimum xs) (minimum ys), Point (maximum xs) (maximum ys))
    where points = concat polygons
          xs = map getX points
          ys = map getY points

isCCW :: (Num a, Ord a) => Polygon a -> Bool
isCCW polygon = (getArea polygon) > 0

ordPoints :: (Num a, Ord a) => Point a -> Point a -> Point a -> Ordering
ordPoints o p1 p2
    | c > 0 = LT
    | c < 0 = GT
    | c == 0 = compare l1 l2
    where p1' = p1 `sub` o
          p2' = p2 `sub` o
          c = cross p1' p2'
          l1 = lengthSquared p1'
          l2 = lengthSquared p2'

convexHull :: (Num a, Ord a) => Polygon a -> Polygon a
convexHull ps = foldl update [] (sortBy (ordPoints o) ps)
    where o = minimum ps
          update [] p = [p]
          update [p1] p2 = [p2, p1]
          update pss@(p2:p1:ps) p3 | cross u v >= 0 = p3:pss
                                   | otherwise = update (p1:ps) p3
              where v = p3 `sub` p2
                    u = p2 `sub` p1

-- Checks whether two polygons are on the same side of the line.
sameSide :: (Num a, Ord a) => Line a -> Polygon a -> Polygon a -> Bool
sameSide (Line o d) a b | all (>= 0) pa && all (>= 0) pb = True
                        | all (<= 0) pa && all (<= 0) pb = True
                        | otherwise = False
    where pa = map (cross d . (`sub` o)) a
          pb = map (cross d . (`sub` o)) b<commit_msg>A fix to the convex hull.<commit_after>module Geom where

import Data.List
import Data.Ratio

data Point a = Point { getX :: a
                     , getY :: a
                     } deriving (Eq, Show, Ord)

type PointR = Point Rational
type PointD = Point Double

data Line a = Line { getOrigin :: Point a
                   , getDirection :: Point a
                   } deriving (Eq, Show)

type LineR = Line Rational
type LineD = Line Double

type Polygon a = [Point a]
type PolygonR = Polygon Rational
type PolygonD = Polygon Double

type Segment a = (Point a, Point a)
type SegmentR = Segment Rational
type SegmentD = Segment Double

segmentToLine :: (Num a) => Segment a -> Line a
segmentToLine (a, b) = Line { getOrigin = a
                            , getDirection = b `sub` a
                            }

add, sub :: (Num a) => Point a -> Point a -> Point a
add (Point x1 y1) (Point x2 y2) = Point (x1 + x2) (y1 + y2)
sub (Point x1 y1) (Point x2 y2) = Point (x1 - x2) (y1 - y2)

ort :: (Num a) => Point a -> Point a
ort (Point x y) = Point (-y) x

cross, dot :: (Num a) => Point a -> Point a -> a
cross (Point x1 y1) (Point x2 y2) = x1 * y2 - x2 * y1
dot (Point x1 y1) (Point x2 y2) = x1 * x2 + y1 * y2

lengthSquared :: (Num a) => Point a -> a
lengthSquared (Point x y) = x * x + y * y

getArea :: (Num a) => Polygon a -> a
getArea [] = 0
getArea (origin:points) = sum $ zipWith area points (tail points)
    where area p1 p2 = cross (p1 `sub` origin) (p2 `sub` origin)

getBounds :: (Ord a) => [Polygon a] -> (Point a, Point a)
getBounds polygons = (Point (minimum xs) (minimum ys), Point (maximum xs) (maximum ys))
    where points = concat polygons
          xs = map getX points
          ys = map getY points

isCCW :: (Num a, Ord a) => Polygon a -> Bool
isCCW polygon = (getArea polygon) > 0

ordPoints :: (Num a, Ord a) => Point a -> Point a -> Point a -> Ordering
ordPoints o p1 p2
    | c > 0 = LT
    | c < 0 = GT
    | c == 0 = compare l1 l2
    where p1' = p1 `sub` o
          p2' = p2 `sub` o
          c = cross p1' p2'
          l1 = lengthSquared p1'
          l2 = lengthSquared p2'

convexHull :: (Num a, Ord a) => Polygon a -> Polygon a
convexHull ps = foldl update [] (sortBy (ordPoints o) ps)
    where o = minimum ps
          update [] p = [p]
          update [p1] p2 = [p2, p1]
          update pss@(p2:p1:ps) p3 | cross u v > 0 = p3:pss
                                   | otherwise     = update (p1:ps) p3
              where v = p3 `sub` p2
                    u = p2 `sub` p1

-- Checks whether two polygons are on the same side of the line.
sameSide :: (Num a, Ord a) => Line a -> Polygon a -> Polygon a -> Bool
sameSide (Line o d) a b | all (>= 0) pa && all (>= 0) pb = True
                        | all (<= 0) pa && all (<= 0) pb = True
                        | otherwise = False
    where pa = map (cross d . (`sub` o)) a
          pb = map (cross d . (`sub` o)) b
{'fraction_non_alphanumeric': 0.12549424101770673, 'fraction_numerical': 0.02544266804194602, 'mean_word_length': 1.9309823677581863, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 69, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6382745', 'n_tokens_mistral': 2096, 'n_tokens_neox': 2006, 'n_words': 836}