GeomPredicates (empty) → 0.1

raw patch · 5 files changed

+144/−0 lines, 5 filesdep +basesetup-changed

Dependencies added: base

Files

GeomPredicates.cabal +22/−0
LICENSE +25/−0
Numeric/Geometric/Predicates/Rational.hs +65/−0
Numeric/Geometric/Primitives.hs +29/−0
Setup.lhs +3/−0

+ GeomPredicates.cabal view

@@ -0,0 +1,22 @@+name:                GeomPredicates+version:             0.1+synopsis:            Geometric predicates +description:         Exact computation of common geometric predicates. +category:            Math+license:             BSD3+license-file:        LICENSE+author:              Neal Alexander+maintainer:          NHAlxr@gmail.com+Build-Type:          Simple+Cabal-Version:       >=1.6+   +Library+  Build-Depends:     base >= 3 && < 5+  Exposed-modules:   Numeric.Geometric.Predicates.Rational, Numeric.Geometric.Primitives  +  ghc-options:       -Wall ++source-repository head+  type:     darcs+  location: http://code.haskell.org/~hexpuem/GeomPredicates++

+ LICENSE view

@@ -0,0 +1,25 @@+Copyright (c) 2010, Neal Alexander <NHAlxr@gmail.com>+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:+    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.+    * Redistributions in binary form must reproduce the above copyright+      notice, this list of conditions and the following disclaimer in the+      documentation and/or other materials provided with the distribution.+    * Neither the name of the <organization> nor the+      names of its contributors may be used to endorse or promote products+      derived from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY+DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND+ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+

+ Numeric/Geometric/Predicates/Rational.hs view

@@ -0,0 +1,65 @@+{-# LANGUAGE UnicodeSyntax #-}++module Numeric.Geometric.Predicates.Rational where+import Numeric.Geometric.Primitives+++-- | Counter-clockwise orientation test. Classifies p3 in relation to the line formed by p1 and p2.++ccw ∷ Vector2 Rational → Vector2 Rational → Vector2 Rational +    → Ordering -- ^ LT=Right, GT=Left, EQ=Coincident ++ccw (x1,y1) (x2,y2) (x3,y3) = compare result 0+    where+      result = (x1*y2) + (x2*y3) + (x3*y1) - (x1*y3) - (x2*y1) - (x3*y2)+++-- | Test the relation of a point to the circle formed by (p1..p3).++incircle ∷ (Vector2 Rational, Vector2 Rational, Vector2 Rational) -- ^ 3 points on the circle, must be in counterclockwise order. +         → Vector2 Rational                                       -- ^ Query point +         → Ordering                                               -- ^ GT=inside, EQ=border, LT=outside +incircle (p1,p2,p3) p4 = compare result 0++       where+         result = (d p1) * (ccw' p2 p3 p4) +                - (d p2) * (ccw' p1 p3 p4) +                + (d p3) * (ccw' p1 p2 p4) +                - (d p4) * (ccw' p1 p2 p3)++         d (x,y) = (x*x) + (y*y)++         ccw' (x1,y1) (x2,y2) (x3,y3) = (x1*y2) + (x2*y3) + (x3*y1) - (x1*y3) - (x2*y1) - (x3*y2)++-- | Test if Point is within the closed interval specified++cintt ∷ Rational -- ^ Lo +      → Rational -- ^ Hi+      → Rational -- ^ Point +      → Bool      ++cintt x1 x2 p | x1 == x2 = p == x1+              | otherwise = t >= 0 && t <= 1++          where+            t = (u - p) / (-v)+            u = x1+            v = x2 - x1++++-- | Calculate the point of intersecton. Assumes the input lines are already known to be intersecting,++isctp ∷ LineSegment (Vector2 Rational) → LineSegment (Vector2 Rational) → Vector2 Rational+isctp ((ax,ay),(bx,by)) ((cx,cy),(dx,dy)) = (x,y)++    where++      rtop = (ay-cy)*(dx-cx)-(ax-cx)*(dy-cy)+      rbot = (bx-ax)*(dy-cy)-(by-ay)*(dx-cx)++      r = rtop/rbot++      x = ax + r * (bx - ax)+      y = ay + r * (by - ay) +

+ Numeric/Geometric/Primitives.hs view

@@ -0,0 +1,29 @@+module Numeric.Geometric.Primitives where++type Vector2 a = (a,a)+type LineSegment a = (a,a)++lOrigin :: LineSegment a -> a +lOrigin = fst++lDestination :: LineSegment a -> a+lDestination = snd++flipLine :: LineSegment a -> LineSegment a+flipLine (a,b) = (b,a)++data IntersectionPoint = Endpoint0 | Endpoint1 | Between deriving (Eq,Read,Show,Enum)++type IntersectionPair = (IntersectionPoint,IntersectionPoint)++data LineIntersection = Coincident +                      | Parallel +                      | NINP -- ^ Not intersecting and not parallel +                      | Intersecting IntersectionPair+                          deriving (Eq,Show,Read)++data Slope = ZeroSlope+           | UndefinedSlope+           | NegativeSlope+           | PositiveSlope deriving (Eq,Read,Show)+

+ Setup.lhs view

@@ -0,0 +1,3 @@+#!/usr/bin/env runhaskell+> import Distribution.Simple+> main = defaultMain