MantaWeb Science

The cornerstone of MantaWeb is an algorithm for matching mantas by their unique constellation of spots. A constellation is the set of spots (coordinates and radius) on the belly of a manta. The preliminary (un-optimised) algorithm to compute matches is a brute-force search of all constellation translations and rotations.


Match results: / = % computing...

Each execution of the algorithm requires two constellations, the reference and the comparison, with at least three points to each. Note: the algorithm computes only linear transformations. This can still be greatly improved!

\begin{algorithm} \caption{Constellation match} \begin{algorithmic} \State $\mathbf{r}$ := reference constellation \State $\mathbf{c}$ := comparison constellation \State $\mathbf{q}$ := quantified results \Procedure{Match}{$\mathbf{r}, \mathbf{c}$} \ForAll{$r_i \in \mathbf{r}$} \ForAll{$c_j \in \mathbf{c}$} \State $\mathbf{c}^t$ := $\mathbf{c}$ translated to $c_j - r_i$ \ForAll{$r_{-i} \in \mathbf{r} - r_i$} \ForAll{$c_{-j}^t \in \mathbf{c}^t - c^t_j$} \State $\theta$ := rotate $c^t_{-j}$ to $r_{-i}$ with origin $c^t_j$ \State $\mathbf{c}^\theta$ := $\mathbf{c}^t$ rotated by $\theta$ with origin $c^t_j$ \State $h$ := scale $c^\theta_{-j}$ to $r_{-i}$ \State $\mathbf{c}^h$ := $\mathbf{c}^\theta$ scaled by $h$ \State $\mathbf{q}{(r_i, r_{-i}, c_j, c_{-j})}$ := \Call{Quantify}{$\mathbf{c}^h$} \EndFor \EndFor \EndFor \EndFor \Return $\max_{(i, -i, j, -j)}\mathbf{q}$ \EndProcedure \Procedure{Quantify}{$\mathbf{c}^h$} \State $m$ := $0$ \ForAll{$r_i \in \mathbf{r}$} \ForAll{$c_j \in \mathbf{c}^h$} \If{$c_j \in \text{nbd\ } r_i$} \State $m$ := $m + 1$ \EndIf \EndFor \EndFor \Return{$m$} \EndProcedure \end{algorithmic} \end{algorithm}

The result is the maximum number of overlapping points over all transformations. This algorithm can be significantly improved; however, the simplest is the best start.