November 23, 2006

Line–Line Intersection

I decided to represent lines as two distinct points. Two lines can either:
  1. Intersect at a single point
  2. Be coincident (i.e. identical)
  3. Be parallel

I created an Intersection function on my Line type. It takes another Line and returns an Intersection value. “Intersection” is a union type representing the above three cases.

Here’s the code:

#pragma indent

using System
using System.Console
using System.Math
using Nemerle.Utility

namespace Prototype

    static class DoubleExtensions
        public static IsTiny(this d : double) : bool
            -double.Epsilon < d && d < double.Epsilon

    [Record] struct Point
        [Accessor] _x : double
        [Accessor] _y : double

        public override ToString () : string
            $"($_x, $_y)" 

        public static @:( pt : int * int ) : Point
            | (x,y) => Point(x,y)

        public static @:( pt : double * double ) : Point
            | (x,y) => Point(x,y)

    [Record] struct Line
        [Accessor] _point1 : Point
        [Accessor] _point2 : Point

        public Intersect (other : Line) : Intersection
            def Det (a,b,c,d)
                a * d - b * c

            def (x1,x2,x3,x4) = (Point1.X, Point2.X, other.Point1.X, other.Point2.X)
            def (y1,y2,y3,y4) = (Point1.Y, Point2.Y, other.Point1.Y, other.Point2.Y)

            def d1 = Det(x1, y1, x2, y2)
            def d2 = Det(x3, y3, x4, y4)
            def denom = Det(x1 - x2, y1 - y2, x3 - x4, y3 - y4)

            if (denom.IsTiny())
                def x = Det(d1, x1 - x2, d2, x3 - x4)
                def y = Det(d1, y1 - y2, d2, y3 - y4)
                if (x.IsTiny() && y.IsTiny())
                    Intersection.Coincident()
                else
                    Intersection.Parallel()
            else
                def x = Det(d1, x1 - x2, d2, x3 - x4) / denom
                def y = Det(d1, y1 - y2, d2, y3 - y4) / denom
                Intersection.Point(Point(x,y))

        public variant Intersection
            | Parallel
            | Coincident
            | Point
                pt : Prototype.Point

using Prototype
def l1 = Line((1,1), (10,10))
def l2 = Line((0,1), (12,13))
def l3 = Line((5,1), (1,5))
def l4 = Line((0,0), (12,12))

def foos = [l1.Intersect(l2), l1.Intersect(l3), l1.Intersect(l4)]

foreach (i in foos)
    | Line.Intersection.Point(pt) => WriteLine($"Point $pt")
    | Line.Intersection.Coincident => WriteLine("Coincident")
    | Line.Intersection.Parallel => WriteLine("Parallel")

P.S.
Some Nemerle gems:
1) Implicit cast from (int * int) to Point. This lets me use (1,3) in place of Point(1,3) – cuts down on the visual noise when building up lists of points!
2) match inside foreach

foreach (x in xs)
  | Foo => ...
  | Bar => ...

very cool!!


- No comments Not publicly viewable


Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.

Trackbacks

Google Ads

Search this blog

Most recent comments

  • I scratched my eye while i was holding some kind of plastic packaging.. Anyways the corner of the pl… by Ercan on this entry
  • About a year ago my contacts that i was wearing, i guess were fautly, because shortly after they wer… by Jon on this entry
  • I got shower gel in my eye 4 and a half days ago, and becasue i rubbed my eyes a lot, i have scratch… by Chris on this entry
  • This website may help http://www.webmd.com/eye–health/tc/Eye–Injuries–Home–Treatment by S on this entry
  • I somehow got dirt, or debris in my eye. The terrible pain sent me in a tailspin. I was afraid of sa… by Bobbi on this entry

Tags

November 2006

Mo Tu We Th Fr Sa Su
Oct |  Today  | Dec
      1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30         

Galleries

Blog archive

Loading…
Not signed in
Sign in

Powered by BlogBuilder
© MMXIV