Longest Distance in a cloud of polar points=> best algo

General Discussion
1

Hello … this is the totally out of context questions …

I have a cloud of points (known only by their polar coordinates) and i’m looking for an efficient algorithm to get the longest distance between 2 points in this cloud.

I also need to keep track of the two points that provide this longest distance.

I’m able to do so with a brute force algorithm but i would need some hints on how to prune the points… (or to discard some pair of points without really calculating the cartesian distance between them)

Currently i cannot process more than 200 points in less than 10 minutes
I have very little processing power (think mobile phone !!)

All inputs welcome…

2

Perhaps someting like a bsp, but for polar coordinates? So, divide your space in sections and assign each point to the section in which it lies. If there are points in a section far away, you can skip all points in sections that are closer.

I hope this explanation makes sense :slight_smile: .

3

I dont think i get your problem. You have 200 2D points in polar or cartesian system. And it takes you 10 minutes to do 40,000 computations? thats .012ms per computations. I don’t think any thing could be this slow.

from random import *
from math import *
from pandac.PandaModules import *
polar_points = [ Vec2(random()*2*pi,random()*2*pi) for p in xrange(1000)]
points = [ Vec2(sin(p[0]),cos(p[1])) for p in polar_points ]
big = 0
final = None
for a in points:
    for b in points:
        l = (a-b).length()
        if l > big:
            big = l
            final = a,b
print big,final
4

Don’t curse me :slight_smile:
I’m trying to help a friend so i’m starting from its results right now.

In fact it is slow because
a) it is written as an vba macro
b) it run inside an XLS Worksheet
c) that is run inside a nokia mobile phone
(first generation that get access to XLS worksheet)
d) polar angles are given with a precision of 6 digits …

But i’ll check if he can execute python on its mobile phone… It would be easier …

5

Yes using Python and Panda, even the brute force is damm fast !!
I’ll check if i can use python on this damm mobile phone…

6

The fastest algorithm (or at least a much faster algorithm for almost any dataset) is probably to find the convex hull of the set of points, and then do your brute force pair testing against only the points on the convex hull (hopefully, but not necessarily a small fraction of all points).

Finding the convex hull is fairly easy in 2D, there are a number of algorithms that can do it.

Actually, you could get even more speedup by not doing full brute force testing at the end but by testing only a subset.

Example: say you have 100 points on the CH. First you find that the farthest point from 0 is 53 (chances are it will be about halfway around if the points are distributed fairly evenly). Because point 1 is close to point 0 (these indexes are for points on the hull, not for the original point set), its farthest point will be close to point 53. So start testing point 1 against point 53, and then search in both directions from 53 only as long as the distances get bigger. Then store that point and use it as the starting point to search for the point farthest from point 2, etc.