#
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)
_finished = (next.DistanceTo(_end) < _radius)
(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:- Intersect at a single point
- Be coincident (i.e. identical)
- 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!!