Re: Efficient way to search for overlapping circles of varying radii?

Jonathan Greenberg <usenet@xxxxxxxxxxxxx> wrote:
I apologize in advance if this is a fairly elementary problem -- I'm an
ecologist, not a computer scientist so I've no background in geometric
searching. I have the following problem that I'd like to code up, and my
first attempt is as slow as it goes:

Given a set of x,y,r which represent points at coordinates x,y and a radius
r, I want to output a new set of x,y,r such that (given two points
p1={x1,y1,r1} and p2={x2,y2,r2}):

If the distance between p1 and p2 is less than the radius of p2 AND the
radius of p1 is less than the radius of p2, remove p1. In practice, this
means that I want to remove all circles whose center is within the area of a
LARGER circle, as long as that larger circle has not already been removed.

That's a somewhat strange way of stating a problem. Instead of
defining what you want as the result, you state an incomplete
algorithm for getting there. That's putting the horse before the
carriage.

For all we can know your existing algorithm, while catastrophically
inefficient, may be needed to fulfil some extra expectation you have
about the result, but failed to state here.

Generally said sorting by radius is quite unlikely to help you here.
You'll have to split up the problem into geometrically smaller
regions, i.e. divide and conquer. Get an algorithms textbook if you
don't have one yet, and look up k-d trees and related algorithms for
sorting and searching in datasets of more than 1 dimension.

--
Hans-Bernhard Broeker (broeker@xxxxxxxxxxxxxxxxxxxxx)
Even if all the snow were burnt, ashes would remain.
.

Relevant Pages

  • Re: Confession
    ... maybe it's just me;) Whatever the language I just push back on that algorythm, so, could any one have the kindness to create me a function where I just pass x, y, radius and I get back an array of coordinates that fall within the circle that is generated by x,y and radius? ... I will port it myself to whatever language I fall in love with. ... I'm not exactly sure what the Bressenham algorithm is, but the one Jim just gave you works pretty fast, - I'm using something similar in my dungeon generation, no noticeable performance decrease as opposed to just using square rooms. ... for a circle: ...
    (rec.games.roguelike.development)
  • Algorithm for minimizing distance between points in two sets.
    ... Suppose I have a circle in 2 dimensions with a radius 1. ... I can only think of a brute force algorithm. ... minimal distance between each pi and p`i. ...
    (comp.graphics.algorithms)
  • Diagonal vectors for BSP trees
    ... I was reading the paper "Refinements to nearest-neighbor searching in k ... He mentions that using planes of arbitrary direction speeds up nearest ... "An Optimal Algorithm for Approximate Nearest in Fixed Dimensions", ...
    (comp.graphics.algorithms)
  • Re: smallest disk covering a set of points
    ... > to steps: ConvHull and MaxDist. ... > worst case time Ocan be achived but the algorithm will be ... >> radius and moved the centre closer to that outermost point, ... >> circumference, ...
    (comp.programming)
  • Re: smallest disk covering a set of points
    ... > Is there a fast algorithm for finding the smallest disk that covers a set ... > circle till I hit the outermost point, ... Find the minimal set of points which generates the convex hull ... Which looks like a linear time minimum circle finding algorithm to me. ...
    (comp.programming)