1
$\begingroup$

my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my image after processing it are shown in green. As you can see I get many more points from the image than just the black ones, due to other structures inside the picture. So I've got a set of points and I know that there are at least three of them that are on a curve which is approximately a line and the approximate distance between the points is also known. I need to find these three points from my set.

The algorithm should be able to detect whether there is such a structure in the picture or there isn't one.

enter image description here

$\endgroup$
1
$\begingroup$

A simple algorithm is to iterate over all ways to choose 3 of the points, and test whether those 3 satisfy your criteria (are approximately colinear, have the appropriate distances, etc.). There are ${n \choose 3}$ such triples, so the running time of this algorithm is $O(n^3)$.

It is possible to improve on that. Here is an algorithm whose running time is $O(n^2 \log n)$:

  • For each point $p$:

    • Sort the points by their slope to $p$. In other words, for each point $q$, calculate the slope of the line connecting $p$ and $q$, and use this as the key to help you sort the points.

    • Look for two points $q_1,q_2$ such that the slope of the line connecting $p$ and $q_1$ is approximately the negative of the slope of the line connecting $p$ and $q_2$. You can check whether such a pair of points $q_1,q_2$ exist by a linear scan over the sorted list built in the previous step. For each such pair, test whether $q_1,p,q_2$ satisfy your criteria (are approximately colinear, have the appropriate distances, etc.); if they are, output them.

The running time is $O(n^2 \log n)$, since for each iteration of the outer loop you do $O(n \log n)$ work, and the outer loop does $n$ iterations.

The above algorithm sorts the list of points by their slope, to make it easier to find 3 points that are approximately colinear. You could also sort the list of points by their distance to $p$, to make it easier to find 3 points at the prescribed distances. It's hard to say a priori which one might work better, but you could certainly try them both.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.