CODEWITHSUNDEEP
algorithmcomputational-geometry
drb
drb

Reputation: 738

Is there an algorithm to find nearby points using only polar coordinates?

Suppose I have a vector of points as polar coordinates.

Suppose one of those points acts as a probe for which I want to find all the other points within a certain distance.

Is there an algorithm to do this without converting them to Cartesian form?

Upvotes: 6

Views: 773

Answers (2)

Laurent Grégoire
Laurent Grégoire

Reputation: 4146

Be careful, if you plan to scale up your algorithm to many points, probing for points nearby is better done using a spatial index. I'm not aware of the existence of spatial indexes using polar coordinates, and I'm sure they would be a bit complex to implement/use. So if you have:

  • lots of points,
  • probe more frequently than moving points,

ask yourself the question whether you should use Cartesian coordinates and a spatial index.

Do the math yourself according to your typical use case:

  1. Using cartesian alongside polar coordinates:

    • Converting polar to cartesian is done only when a point moves, and involve two trigonometric functions;
    • Finding points nearest than a certain distance to another point may be done in O(1) time (depending on the average distance, the size of the spatial index, the number of points...), and does not involve anything other than adds/multiplies (not even square roots, you compare the distance squared).

  2. Using polar coordinates only:

    • Scanning for all points w/o spatial index is O(n);
    • This involves one trigonometric function per comparison (thus n trig calls per probe).

Be aware that trigs are bloody expensive in computation time.

Upvotes: 2

sch
sch

Reputation: 27536

You are looking for the distance for polar coordinates. You can find the formula in this link.

The distance between points (r1, a1) and (r2, a2) is:

D = sqrt(r1*r1 + r2*r2 - 2*r1*r2*cos(a1-a2))

Upvotes: 7

Related Questions