Search for the Intersection of Two Lines
by Ted Kaehler
In the previous chapter of the Nine Dots Puzzle, we realized that we need to find the intersection of two lines. Since this essay is about artificial evolution, let's use that hammer to solve this problem also.
Yes, there is a formula for the exact intersection of two lines, but I certainly can't remember what it is. Understanding how that formula was derived is even more complex. We don't need a formula. We can simply define an error function, guess an answer, and start hillclimbing toward the true answer.
If we express a line in parameterized form, then purely vertical or purely horizontal lines will not give us any trouble. There will be no annoying division by zero.
/* Basic arithmetic functions for vector operation */
Array.prototype.plus = function(anArray) {
return [this[0] + anArray[0], this[1] + anArray[1]]
}
Array.prototype.minus = function(anArray) {
return [this[0] - anArray[0], this[1] - anArray[1]]
}
Array.prototype.times= function(aNumber) {
return [this[0] * aNumber, this[1] * aNumber]
}
Array.prototype.dotProduct = function(anArray) {
return this[0] * anArray[0] + this[1] * anArray[1]
}
[1,2].plus([3,4])
[1,2].times(2.5)
[1,2].dotProduct([-2,1]) /* => 0 */
a point on the line = origin + (parameter * ratio)
where origin is a known point on the line, parameter is a number, and ratio is an (x,y) pair. We will use an Array of length two to represent an (x,y) pair. Multiplication and addition a defined on them above. This is like class Point in the Smalltalk language.
Strategy
Let's set up two parameterized lines, one for each segment, and search for the intersection point. We are looking for parameter values that make a point on one line very close to a point on the other line. Let t1 be the parameter for one line, and t2 for the other. The error is the distance between these points:
distance vector = dvec = origin1 + (t1*ratio1) - origin2 + (t2*ratio2)
distance = squareRoot ( dvec dotProduct: dvec )
We will use the distance squared as the error, since it is faster to compute. We will hunt for t1 and t2 that minimize this error. (The dot product is x1*x2 + y1*y2.)
error = dvec dotProduct: dvec
A Parameterized Line
We define objects of class LineParameterized to have two instance variables, origin and ratio.
LineParameterized = function(pt1, other) {
this.origin = pt1
this.ratio = other.minus(pt1)
}
From two points on the line, we need to compute and remember the ratio. Here is the definition of a method to do that.
LineParameterized.prototype.toString = function() {
return "{origin: " + this.origin + " ratio: " + this.ratio + "}"
}
line0 = new LineParameterized([1,1], [2,2])
Given a parameter value, return a point on the line:
LineParameterized.prototype.pointAt = function(parameter) {
/* Return a point on the line for this parameter */
return this.origin.plus(this.ratio.times(parameter))
}
line0.pointAt(2) /* => [3, 3] */
A Parameterized Line for Hill Climbing
Let's define a subclass that remembers the parameter and a delta for how fast we are moving the parameter. Delta remembers the most recent successful move of the parameter, including the direction and the amount.
LineHunting = function(pt1, other) {
LineParameterized.call(this, pt1, other)
this.param = 0
this.delta = 0
}
LineHunting.prototype = new LineParameterized([0,0], [0,0])
LineHunting.prototype.toString = function() {
return "{origin: " + this.origin + ", ratio: " + this.ratio +
", param: " + this.param + ", delta: " + this.delta + "}"
}
line0 = new LineHunting([2,1], [2,2])
An Object Holding the Intersection of Two Lines
Let's define an object that represents the corner of two line segments. We will use it in the solution array instead of "turn". It has two instance variables. 'line1' is the segment before the corner and 'line2' is the one after it.
LineIntersection = function(line1, line2) {
line1.param = 0
line1.delta = 5
this.line1 = line1
line2.param = 0
line2.delta = 5
this.line2 = line2
}
LineIntersection.prototype.toString = function() {
return "{line1: " + this.line1.toString() +
", line2: " + this.line2.toString() + "}"
}
inters0 = new LineIntersection(new LineHunting([0,0], [1,0]),
new LineHunting([2,1], [2,2]))
When we initialize line1 and line2, they will not know their intersection point. Our goal is to change the param of each line to make the point at param be the intersection.
We will change param in various directions. If the distance between the two intersection points is smaller, we will keep the change. The distance squared is computed by this method:
LineIntersection.prototype.errorSquared = function() {
var delta = this.line1.pointAt(this.line1.param).minus(
this.line2.pointAt(this.line2.param))
return delta.dotProduct(delta)
}
inters0.errorSquared() /* => 5 */
Rather than just trying different values of param randomly, we will keep the last change in param. It worked, so maybe a change of that magnitude and direction will work again. The change in param is kept in the lines's delta.
Param corresponds to a postion on the line. Delta corresponds to a velocity. We will try different accelerations, called accel, in this method:
LineIntersection.prototype.changeDelta = function(accel, aLine) {
var oldErr = this.errorSquared()
var oldP1 = aLine.param
var oldD = aLine.delta
aLine.delta = aLine.delta * accel
aLine.param = aLine.param + aLine.delta
if (this.errorSquared() < oldErr) return true
aLine.param = oldP1 /* put it back */
aLine.delta = oldD /* put it back */
return false
}
inters0.changeDelta(0.1, inters0.line1)
inters0.line1
/* => {origin: [0, 0], ratio: [1, 0], param: 0.5, delta: 0.5} */
This method uses accel to make a new delta and uses that to move param. If the new errorSquared is less than before, keep the new delta and param. If not, revert to the old values. Return true if progress was made. We are varying the point on one line and holding constant the proposed intersection point on the other line.
What values of acceleration should we try?
2 = move param twice as far as before.
1 = move param again the same amount as before.
-1 = reverse direction (very useful just after the initial guess for delta).
0.33 = forward at one third speed.
0.005 = creep forward in case we are making changes that are grossly too big.
-0.005 = creep backwards. Did we overshoot?
Loop through the accelerations and look for one that moves the point on the line to a place with a smaller error.
LineIntersection.prototype._makeProgress = function(aLine) {
/* Vary params to try to get closer to the intersection.
Try to reduce the error. Return true if made progress. */
var tryAccels = [2, 1, -1, 0.33, 0.005, -0.005]
for (var i = 0; i < tryAccels.length; i++) {
if (this.changeDelta(tryAccels[i], aLine)) return true
}
return false
}
inters0 = new LineIntersection(new LineHunting([0,0], [1,0]),
new LineHunting([2,1], [2,2]))
inters0._makeProgress(inters0.line1)
inters0.line1
inters0.errorSquared()
Of course to get to the intersection point, we need to adjust the param on each of the two lines.
LineIntersection.prototype.makeProgress = function() {
/* Try to get closer to a good intersection on each line.
Return true if made progress. */
var b1 = this._makeProgress(this.line1)
var b2 = this._makeProgress(this.line2)
return b1 || b2
}
inters0 = new LineIntersection(new LineHunting([0,0], [1,0]),
new LineHunting([2,1], [2,2]))
inters0.makeProgress()
See if the error is small enough, and try one round of moving params if it is not. This is the method that the Nine Dots solver will call repeatedly to find the actual intersection point. When the error is low enough, the intersection point will be near the point given by:
inters0.line1.pointAt(inters0.line1.param)
LineIntersection.prototype.tryForError = function(anError) {
/* Return #parallel if can't make any progress.
Try to reduce the error in the intersection point of the
two lines. Return true if we got under goal error. */
if (this.errorSquared() < anError) return true
if (this.makeProgress()) {
return this.errorSquared() < anError
} else {
return "parallel"
}
}
inters0 = new LineIntersection(
new LineHunting([0,0], [1,0]),
new LineHunting([2,1], [2,2]))
inters0.tryForError(0.09) /* false this time */
inters0.errorSquared() /* 1.1224 */Testing
Here is some test code to make two lines and try to find the intersection.
inters = new LineIntersection(
new LineHunting([0,0], [1,0]),
new LineHunting([2,1], [2,2]))
while(inters.tryForError(0.09) != true)
inters.line1.pointAt(inters.line1.param) /* => almost [2, 0] */
inters.errorSquared()
Here are the two lines, and the candidate intersection points that makeProgress discovered. The vertical line is not the Y axis. There is no red mark at the intersection because we stopped when the distance was less than 0.3 units.
To do:
refineEnds
Nine Dots Essay
The Nine Dots Puzzle
Intersection of Lines
The Error Function
The Population