[project @ 1999-11-26 10:29:53 by simonpj]
[nofib.git] / real / bspt / Euclid.lhs
1 > {-# OPTIONS -syslib exts #-}
2 > module Euclid
3
4         Module contains definitions of Points and Lines and related
5         functions relating to Euclidean Geometry
6
7
8 >       (       Point(..),Halfspace(..),Line,
9 >               Face(..),mkFace,getSegment,getMyLine,
10 >               Faces,Segment,eqn,solve,space,
11 >               convert,invert,triangleArea,
12 >               mkPoint,mkPolygon,drawSegment)
13
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) )
21
22
23         The data type Line is used to describe a line.
24                 Ln a b c represents the line : ax + by + c = 0
25
26 > data Line = Ln Numb Numb Numb deriving (Show{-was:Text-},Eq)
27
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.
31         
32 > data Point = Pt Numb Numb deriving (Eq,Show{-was:Text-})
33
34
35         The Halfspace type enumerates the possible classifications of 
36         a point with respect to a line.
37         
38 > data Halfspace = Fore | Coin | Rear deriving (Eq,Show{-was:Text-})
39
40         The type Face defines a line segment by its two end points.
41                 It also stores its line equation
42
43 > data Face = Fc Segment Line deriving (Eq,Show{-was:Text-})
44
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.
48
49 > type Segment = (Point,Point)
50
51         The type synonym Faces just abbreviates a list of Face.
52
53 > type Faces = [Face]
54
55         mkFace: function constructor generates line automatically
56
57 > mkFace :: Segment -> Face
58 > mkFace (x,y) = Fc (x,y) (convert x y)
59
60 > getSegment :: Face -> Segment
61 > getSegment (Fc segment _) = segment
62
63 > getMyLine :: Face -> Line
64 > getMyLine (Fc _ line) = line
65
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. 
69
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
75
76         eqn produces the dot product value of a point in a line equation.
77
78 > eqn :: Line -> Point -> Numb
79 > eqn (Ln a b c) (Pt x y) = a*x + b*y + c
80
81
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.
88
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
95
96
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).
99
100 > invert :: Line -> Line
101 > invert (Ln a b c) = (Ln (negate a) (negate b) (negate c))
102
103
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. 
107
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))
112
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
117
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   
120
121
122         triangleArea computes the area of a triangle defined by three
123         points.
124         
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
131         
132         minusPoint performs vector subtraction
133         
134 > minusPoint :: Point -> Point -> Point
135 > minusPoint (Pt x y) (Pt u v) = Pt (u-x) (v-y)
136
137
138         
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.
144
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
152
153
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)]
158          
159 > mkPolygon :: [Point] -> Faces 
160 > mkPolygon [] = []
161 > mkPolygon (a:l) = map2 f (a:l) (l++[a])
162 >                       where f x y = mkFace (x,y)
163
164
165
166
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.
171
172 > drawSegment :: Segment -> String
173 > drawSegment ((Pt x1 y1),(Pt x2 y2)) = line (map rnd [x1,y1,x2,y2])
174
175
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.
179
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 > -}