1 > {-# OPTIONS -syslib exts #-}
2 > module Euclid
4         Module contains definitions of Points and Lines and related
5         functions relating to Euclidean Geometry
8 >       (       Point(..),Halfspace(..),Line,
9 >               Face(..),mkFace,getSegment,getMyLine,
10 >               Faces,Segment,eqn,solve,space,
11 >               convert,invert,triangleArea,
12 >               mkPoint,mkPolygon,drawSegment)
14 > where
15 > import Stdlib (map2,splitAt_YORK,pair,between,numval)
16 > import GeomNum
17 > import MGRlib (line)
18 > import Params (mouseDispx,mouseDispy,gap)
19 > import Char(isDigit)--1.3
20 > import Int( Num(fromInt) )
23         The data type Line is used to describe a line.
24                 Ln a b c represents the line : ax + by + c = 0
26 > data Line = Ln Numb Numb Numb deriving (Show{-was:Text-},Eq)
28         The data type Point defines a point in Euclidean space
29                 Pt x y  represents the point x units along the
30                         horizontal and y units down the vertical.
32 > data Point = Pt Numb Numb deriving (Eq,Show{-was:Text-})
35         The Halfspace type enumerates the possible classifications of
36         a point with respect to a line.
38 > data Halfspace = Fore | Coin | Rear deriving (Eq,Show{-was:Text-})
40         The type Face defines a line segment by its two end points.
41                 It also stores its line equation
43 > data Face = Fc Segment Line deriving (Eq,Show{-was:Text-})
45         The type synonym Segment defines a line segment by its two end points.
46                 (pt1,pt2) is the line commencing at pt1 and finishing
47                           at pt2.
49 > type Segment = (Point,Point)
51         The type synonym Faces just abbreviates a list of Face.
53 > type Faces = [Face]
55         mkFace: function constructor generates line automatically
57 > mkFace :: Segment -> Face
58 > mkFace (x,y) = Fc (x,y) (convert x y)
60 > getSegment :: Face -> Segment
61 > getSegment (Fc segment _) = segment
63 > getMyLine :: Face -> Line
64 > getMyLine (Fc _ line) = line
66         space : determines the halfspace of pt w.r.t. line
67                 eqn returns a value representing the dot product of point/line
68                 zerO,positive are GeomNum class methods.
70 > space :: Line -> Point -> Halfspace
71 > space line pt = if zerO val then Coin else
72 >                 if positive val then Fore
73 >                 else Rear
74 >                       where val = eqn line pt
76         eqn produces the dot product value of a point in a line equation.
78 > eqn :: Line -> Point -> Numb
79 > eqn (Ln a b c) (Pt x y) = a*x + b*y + c
82         convert : Takes two points and produces the line equation of the line
83                 those points lie on. Note that ratio produces
84                 diffx and diffy at the most reduced form ensuring that
85                 the Line definition is a canonical form.
86                 This makes comparing lines for equality trivial and
87                 is space preserving.
89 > convert :: Point -> Point -> Line
90 > convert (Pt x1 y1) (Pt x2 y2) = Ln (diffy) (-diffx) (diffx*y1-diffy*x1)
91 >                                 where
92 >                                       dy=y2-y1
93 >                                       dx=x2-x1
94 >                                       (diffx,diffy) = ratio dx dy
97         invert takes a line and inverts the orientation of its normal.
98         NB: The convention is that a line ax+by+c has normal (a,-b).
100 > invert :: Line -> Line
101 > invert (Ln a b c) = (Ln (negate a) (negate b) (negate c))
104         solve : Takes two line equations and produces the point at which
105                 they intersect. The point (Pt 0 0) is currently returned
106                 if the two lines are parallel.
108 > solve :: Line -> Line -> Point
109 > solve (Ln a b c) (Ln d e f) | zerO ((a*e)-(b*d)) = (Pt 0 0)
110 >                           | not (zerO a)      = solveAux (Ln a b (-c)) (Ln d e (-f))
111 >                           | otherwise         = solveAux (Ln d e (-f)) (Ln a b (-c))
113 > solveAux :: Line -> Line -> Point
114 > solveAux (Ln a b c) (Ln 0 e f) = (Pt x y)
115 >                                       where y = f/e
116 >                                             x = (c-b*y)/a
118 > solveAux (Ln a b c) (Ln d e f) = solveAux (Ln a b c) (Ln 0 (e-b*g) (f-c*g))
119 >                                       where g = d/a
122         triangleArea computes the area of a triangle defined by three
123         points.
125 > triangleArea :: [Point] -> Numb
126 > triangleArea [p1,p2,p3] = abs ((1/2) * (x1*y2-y1*x2))
127 >                               where
128 >                               (Pt x1 y1) = minus p2
129 >                               (Pt x2 y2) = minus p3
130 >                               minus x = minusPoint p1 x
132         minusPoint performs vector subtraction
134 > minusPoint :: Point -> Point -> Point
135 > minusPoint (Pt x y) (Pt u v) = Pt (u-x) (v-y)
139         mkPoint: Takes a string of the form "x y" and creates
140                         the point (Pt x y) where x and y are
141                         number conversions of the strings x and y.
142                         If x or y are not digits the Null point is returned.
143                         Note use of mouse displacement corrections.
145 > mkPoint :: String -> Point
146 > mkPoint l = if and (map isDigit (a++b)) then
147 >                  Pt (fromIntegral (numval a-mouseDispx))
148 >                               (fromIntegral (numval b-mouseDispy))
149 >                 else (Pt 0 0) -- Null Point
150 >                                         where
151 >                                         (a,b)= splitAt_YORK gap l
154         mkPolygon: converts a list of points of the form
155                         [p1,p2,p3..pn] representing the vertices of
156                 a polygon,
157                 to the B-rep form [(p1,p2),(p2,p3),..,(pn,p1)]
159 > mkPolygon :: [Point] -> Faces
160 > mkPolygon [] = []
161 > mkPolygon (a:l) = map2 f (a:l) (l++[a])
162 >                       where f x y = mkFace (x,y)
167         drawface: Returns the escape string required to plot the
168                         face on the screen. Note that each of the
169                         co-ords is rounded to the nearest pixel
170                         position.
172 > drawSegment :: Segment -> String
173 > drawSegment ((Pt x1 y1),(Pt x2 y2)) = line (map rnd [x1,y1,x2,y2])
176         inRange: tests whether the point a b lives in the box with
177                 origin (top left corner) at (x,y) with height h and
178                 width w.
180 > {- UNUSED: (an illegal name, too)
181 > inRange :: [Integer] -> Point -> Bool
182 > inRange [x,y,w,h] (Pt a b) = between (fromInteger x) (fromInteger w) a
183 >                                         && between (fromInteger y) (fromInteger h) b
184 > -}