Just for fun, I want to see whether I can speed up the search of the linearized Bezier object. With a change in structure we may be able to binary search it. Result: Not enough improvement.
We have an object BezierSplitter that splits Beziers, and an object PolylinePath that searches them and returns what it finds. The splitter returns an array of vector points (we call them nodes sometimes). The PolylinePath builds a supporting structure for searching, like this:
function PolylinePath:init(polyline)
self._points = polyline
self._lengths, self._length = self:_create_lengths(self._points)
end
function PolylinePath:_create_lengths(points)
local lengths = {0}
local total_length = 0
for p0, p1 in self:do_by_pairs() do
local len = p0:dist(p1)
table.insert(lengths, len)
total_length += len
end
return lengths, total_length
end
The table _lengths contains the individual lengths of each segment, from Node N-1 to Node N. When we search for a value, we do so by searching forward from the beginning of the table, counting down the length we’re searching for until we find the first length less than what we’re (then) looking for:
function PolylinePath:_find_distance(d)
local remaining_distance = d
for i, len in self._lengths do
if remaining_distance < len then
return i, remaining_distance/len
end
remaining_distance -= len
end
return nil
end
That was the best idea I had at the time. But if we had the cumulative lengths, there would be only one cell whose length value was greater than what we seek, and whose preceding value was less. So we should be able to binary search that.
There will be 25 entries in our table, if I’m not mistaken. So our average linear search will be 12 probes. A binary search should be able to do it in no more than um 4? 5? Fewer, anyway.
This morning I propose to try it and find out. More for the exercise than anything else: I’m not sure we’ll ever use this. But I am here to work out.
We’ll begin by building a second lengths table in PolylinePath, the one with cumulative values.
Let’s test that. First a basic check, make that work, then add in the additional checks:
_:test("polyline path cumulative lengths", function()
local pp = PolylinePath(splitter:polyline(3))
_:expect(#pp._lengths).is(25)
end)
That works. There are 25 elements in the path. Now we want a new member, let’s call it _distances, that is the accumulation of _lengths:
_:test("polyline path cumulative lengths", function()
local pp = PolylinePath(splitter:polyline(3))
_:expect(#pp._lengths).is(25)
local total = 0
for i, length in pp._lengths do
total += length
_:expect(pp._distances[i]).is(total)
end
end)
That looks right to me. Test fails miserably, of course. We code:
function PolylinePath:init(polyline)
self._points = polyline
self._lengths, self._distances, self._length = self:_create_lengths(self._points)
end
function PolylinePath:_create_lengths(points)
local lengths = {0}
local distances = {0}
local total_length = 0
for p0, p1 in self:do_by_pairs() do
local len = p0:dist(p1)
table.insert(lengths, len)
total_length += len
table.insert(distances, total_length)
end
return lengths, distances, total_length
end
Our test passes. Now let’s test a new search. I wonder if I remember how to do a binary search. Anyway:
_:test("binary search", function()
local pp = PolylinePath(splitter:polyline(3))
local at100 = pp:at(100)
local bat100 = pp:binary_at(100)
_:expect(bat100).is(at100)
end)
I just picked a not very random value less than the length of the path, which is 344 and change. This test may be too large, by which I mean it may take too much code in one go to make it work. If that seems to be happening, we’ll try something easier.
Let’s just do it:
I’ll show you what I’ve got in a moment: it seems to have worked. But the returned vector is off by a tiny fraction. I think we have a checker for that.
This test is passing:
_:test("binary search", function()
local pp = PolylinePath(splitter:polyline(3))
local at100 = pp:at(100)
local bat100 = pp:binary_at(100)
verify_vectors(at100, bat100)
end)
verify_vectors checks to see if the vectors are approximately equal, and they are, within 0.001.
Let’s write a more comprehensive test:
_:test("lots of binary search", function()
local pp = PolylinePath(splitter:polyline(3))
local length = pp._length
for d = 1, length, 0.1 do
local at_got = pp:at(d)
local bat_got = pp:binary_at(d)
verify_vectors(bat_got, at_got)
end
end)
Well, that didn’t take long to fail: it fails on 1. I think my binary search, hacked out, isn’t so good. For one thing, we can’t allow it ever to probe at the first location in our list.
OK, I confess that I looked up how to do it and adapted what I found. Here’s what’s working:
function PolylinePath:binary_at(d)
local idx, frac = self:_binary_find_distance(d)
local p0 = self._points[idx-1]
local p1 = self._points[idx]
return p0*(1 - frac) + p1*frac
end
function PolylinePath:_binary_find_distance(d)
local ds = self._distances
local low = 1
local high = #ds
while low <= high do
mid = math.ceil((low + high) / 2)
d_low = ds[mid-1]
d_high = ds[mid]
if d_low <= d and d_high >= d then
return mid, (d-d_low)/(d_high-d_low)
end
if d_low > d then
high = mid - 1
else
low = mid + 1
end
end
error(`{d} not found`)
end
And by working, I mean that it is getting answers within 0.001 of the linear lookup for over 3000 probes into the list, more than 12,000 individual value checks.
Is it faster? Let’s find out.
_:test("time searches", function()
local pp = PolylinePath(splitter:polyline(3))
local length = pp._length
local n = 100
local t_start = os.clock()
local at
for i = 1,n do
for d = 0, length, 0.1 do
at = pp:at(d)
end
end
local t_at = os.clock()
for i = 1,n do
for d = 0, length, 0.1 do
at = pp:binary_at(d)
end
end
local t_binary = os.clock()
print(t_at-t_start, t_binary-t_at)
end)
Results are not good:
0.3033688750001602 0.3198898333357647
The binary search value is a bit slower than the linear. Let’s see if we can tighten it up, make sure it’s not doing any extra work. I try everything I can see. Most significant was that mid, d_low and d_high were not declared local. I wind up with this:
function PolylinePath:_binary_find_distance(d)
local dd = d
local ds = self._distances
local low = 1
local high = self._n
local d_low, d_high, mid
while low <= high do
mid = math.ceil((low + high) / 2)
d_low = ds[mid-1]
d_high = ds[mid]
if d_low <= dd and d_high >= dd then
return mid, (d-d_low)/(d_high-d_low)
end
if d_low > dd then
high = mid - 1
else
low = mid + 1
end
end
error(`{d} not found`)
end
My final comparison very slightly favors the binary search:
0.30307120829820633 0.2963937083259225 0.9779672242382275
With all that clever code, I save 2.3% of the cost. I think we can let this one go.
Fun, though, and a concern lifted from my mind. We might revisit the creation of the polyline part at some future time. But we need not worry about the binary search possibility any more.
I’ll save the code this way and then remove the binary search from the final save, so we have it in git if we ever want it.
A worth-while exercise. It was a decent bet that binary search would be faster even at the scale of a dozen probes. It seems to be a bit faster, but not enough to justify the complexity. The linear search obviously works and the binary one … well, it passed a very comprehensive test.
I was taught not to optimize without a measurable payoff. So it was second nature (beaten into me by my betters) to test the result. And given the small difference, I don’t mind tossing it out.
I am somewhat curious to know why the binary search didn’t do better, but I don’t see a likely place to start looking, given that I got everything moved into locals and such. If I do get an idea, I can always get the code back for further work. But I don’t think that will happen.
Tried an idea, found out that it wasn’t worth using. That’s a win of some kind.
Safe paths!