All entries for Thursday 23 November 2006

November 23, 2006

Line Follower

My initial line follower is working! It was tricky working out which end of a line segment, created by best fitting points, to follow each time. The code is still not perfect since tight hair-pin corners confuse it. The main assumption is that a line only changes direction gradually. So the line follower always try to continue in a direction close to the previous heading.
Here is a sample of a vectorized line (shown in red):

To improve performance when turning sharp corners I think the algorithm needs to be able to look at the image at different levels. Perhaps it can start with a small radius to capture points and grow it a few times to get a sample of possible headings. This would probably require the erasure of “used” points from the image.

In fact maintaining multiple possible paths could make the algorithm more adaptive. This would make junction handling easy. Both routes are taken, only one has to succeed.

Here is the NextSegment function so far:

``````        public NextSegment (prevPoint : Point, prevLine : Line) : (Point * Point * Line)
def points = GetColoredPointsInCircle(prevPoint)
def (centroid, angle) = BestFit(points)

def rCosA = Cos(angle) * _radius
def rSinA = Sin(angle) * _radius
def startPoint = Point(centroid.X - rCosA, centroid.Y - rSinA)
def endPoint = Point(centroid.X + rCosA, centroid.Y + rSinA)
def line = Line(startPoint, endPoint)

def betterStartPoint = match (line.Intersect(prevLine))
| Line.Intersection.Point (pt) =>
if (PointInLineSegment(pt, startPoint, endPoint))
pt
else
prevPoint
| Line.Intersection.Parallel =>
prevPoint
| Line.Intersection.Coincident =>
prevPoint

def (next,l) = if (Abs(prevLine.AngleTo(line)) > PI/2)
(startPoint, Line(line.Point2, line.Point1))
else
(endPoint, line)

(betterStartPoint, next, l)``````

The code to choose the correct next point on the polyline is a bit of hack. Basically it has to flip the best fit “line” as well to ensure the heading is maintained. This block will be changed in future versions to include the multiple branching.

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!!

Search this blog

• 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

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

Not signed in