All entries for Thursday 23 November 2006
November 23, 2006
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.
- 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")
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 => ...