Segment.hs

{-# LANGUAGE FlexibleContexts
           , FlexibleInstances
           , UndecidableInstances
  #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Diagrams.TwoD.Segment
-- Copyright   :  (c) 2012 diagrams-lib team (see LICENSE)
-- License     :  BSD-style (see LICENSE)
-- Maintainer  :  diagrams-discuss@googlegroups.com
--
-- Segments in two dimensions are special since we may meaningfully
-- compute their point of intersection with a ray.
--
-----------------------------------------------------------------------------

module Diagrams.TwoD.Segment where

import Control.Applicative (liftA2)

import Data.AffineSpace
import Data.Monoid.PosInf hiding (minimum)
import Data.VectorSpace

import Diagrams.Core
import Diagrams.Core.Trace

import Diagrams.Segment
import Diagrams.Solve
import Diagrams.TwoD.Transform
import Diagrams.TwoD.Types
import Diagrams.TwoD.Vector
import Diagrams.Util

instance Traced (Segment R2) where
  getTrace = getTrace . mkFixedSeg origin

instance Traced (FixedSegment R2) where

{- Given lines defined by p0 + t0 * v0 and p1 + t1 * v1, their point of
   intersection in 2D is given by

     t_i = (v_(1-i)^ . (p1 - p0)) / (v1^ . v0)

   where v^ denotes the perpendicular to v, i.e. v rotated by
   -tau/4.

   This can be derived by starting with the parametric equation

     p0 + v0 t0 = p1 + v1 t1

   and rearranging to get the matrix equation

     [v0 -v1] [ t0 ]  =  (p1 - p0)
              [ t1 ]

   Working out the product of the inverse of [v0 -v1] with (p1 - p0)
   results in the above formulas for t_i.
-}

  getTrace (FLinear p0 p0') = mkTrace $ \p1 v1 ->
    let
      v0     = p0' .-. p0
      det    = perp v1 <.> v0
      perp v = rotateBy (-1/4) v
      p      = p1 .-. p0
      t0     = (perp v1 <.> p) / det
      t1     = (perp v0 <.> p) / det
    in
      if det == 0 || t0 < 0 || t0 > 1
        then PosInfty
        else Finite t1

{- To do intersection of a line with a cubic Bezier, we first rotate
   and scale everything so that the line has parameters (origin, unitX);
   then we find the intersection(s) of the Bezier with the x-axis.

   XXX could we speed this up by first checking whether all the
   control point y-coordinates lie on the same side of the x-axis (if so,
   there can't possibly be any intersections)?  Need to set up some
   benchmarks.
-}

  getTrace bez@(FCubic {}) = mkTrace $ \p1 v1 ->
    let
      bez'@(FCubic x1 c1 c2 x2) =
        bez # moveOriginTo p1
            # rotateBy (negate (direction v1))
            # scale (1/magnitude v1)
      [y0,y1,y2,y3] = map (snd . unp2) [x1,c1,c2,x2]
      a  = -y0 + 3*y1 - 3*y2 + y3
      b  = 3*y0 - 6*y1 + 3*y2
      c  = -3*y0 + 3*y1
      d  = y0
      ts = filter (liftA2 (&&) (>= 0) (<= 1)) (cubForm a b c d)
      xs = map (fst . unp2 . fAtParam bez') ts
    in
      case xs of
        [] -> PosInfty
        _  -> Finite (minimum xs)