# Approximation search source reconstruction localization algorithm

Goal

To determine the coordinates of some signal source in a 3D space, given the coordinates of four observers and the time at which each saw the signal, as well as the velocity of the signal.

Algorithm

The algorithm is more-or-less comprised of two pieces: the approximation search algorithm, and the localization algorithm. Approximation search can be described simply as follows:

Suppose we have some function, f(x), and we want to find an x such that f(x) = y. We begin by choosing some search interval, [xi, xf], and we probe some evenly-spaced points along this interval with some step, da. We remember the point with the least error, and feed that error back into the algorithm. We recursively increase accuracy, reducing da and restricting the search interval to around each progressively better solution. We stop when we've reached the maximum number of iterations (configurable).

The localization bit is simply the computation of the error. I could explain it, however I find that the code does so itself far better than I could hope to in words.

Issues

In my opinion, the code is a bit messy and slightly more difficult to read than I'd like. Similarly, I'm not sure how I feel about the nested loops. Of course, I don't want to overcomplicate things simply to get rid of nested loops, however if there's a nicer way to do this, I'm all ears.

It's also slow. This is Python, of course, so I shouldn't expect it to perform like a similarly implemented algorithm in, say, C/C++, however I'm certainly interested in increasing search speed.

Lastly, it's been a while since I've done anything in Python, so I'm interested in a critique of my style. The goal is readability, and not necessarily 'standards' compliance.

Tear it apart. Don't hold back!

import math
from dataclasses import dataclass

@dataclass
class Approximate:

ai: float;  af: float
da: float;   n : int

# Default values
aa: float = 0
ei: float = -1
a : float = 0
e : float = 0
i : int   = 0

done: bool = False
stop: bool = False

def step(self):

if (self.ei < 0) or (self.ei > self.e):

self.ei = self.e
self.aa = self.a

if (self.stop):

self.i += 1

if (self.i >= self.n):

self.done = True
self.a = self.aa

return  # Max iter

# Restrict to window around 'solution'
self.ai = self.aa - self.da
self.af = self.aa + self.da

self.a = self.ai

# Increase accuracy
self.da *= 0.1
self.ai += self.da
self.af -= self.da

self.stop = False

else:

# Probe some points in [ai,af] with step da
self.a = self.a + self.da

if (self.a > self.af):

self.a = self.af
self.stop = True

def localize(recv):

ax = Approximate(0, 5000, 32, 10)
ay = Approximate(0, 5000, 32, 10)
az = Approximate(0, 5000, 32, 10)

dt = [0, 0, 0, 0]

while not ax.done:
ay = Approximate(0, 5000, 32, 10, 0, 0)

while not ay.done:
az = Approximate(0, 5000, 32, 10, 0, 0)

while not az.done:

for i in range(4):
x = recv[i][0] - ax.a
y = recv[i][1] - ay.a
z = recv[i][2] - az.a

baseline = math.sqrt((x * x) + (y * y) + (z * z))

dt[i] = baseline / 299800000

# Normalize times into deltas from zero
baseline = min(dt[0], dt[1], dt[2], dt[3])

for j in range(4):
dt[j] -= baseline

error = 0

for k in range(4):
error += math.fabs(recv[k][2] - dt[k])
ay.e = error
ax.e = error

az.step()

ay.step()

ax.step()

# Found solution
print(ax.aa)
print(ay.aa)
print(az.aa)

• Sample input and output would be helpful. Commented Oct 24, 2020 at 6:35
• For a closed form solution (e.g., non-iterative) search for "Bancroft's Algorithm". Commented Apr 21, 2022 at 5:36
• Years later: why not just use scipy? Commented Aug 22, 2023 at 20:33

Remove empty lines after if/else. Remove empty lines in general, this has too many. Use the new math.dist. Add comments about how the approximation works. Add docstrings.