CODEWITHSUNDEEP
algorithm2d
nightin_gale
nightin_gale

Reputation: 831

Quickly find circles from an array after clicking on Canvas

I have an array of circles on my canvas. They are randomly located. I want to find the circle after clicking on the canvas very fast. I don't want to go thought all array and compare coords of each circle and cursor coord. I don't want to sort the array by X-coord or Y-coord and realize quick or binary search. Is there any exist algorith to simplify my request od finding hitted circle?

Upvotes: 2

Views: 127

Answers (2)

Gary Drocella
Gary Drocella

Reputation: 337

You could consider using a PM quad tree spatial data structure. A PM Quadtree recursively partitions the euclidean n space where each sub tree is an origin with 4 children on the plane, 8 children in 3 space, etc. As a technical note, the quadtree is the case of the plane when the root has 4 children, the 3 space is called an oct-tree, etc.

Typically for a 2d plane, the dimensions are written as all points (0,0) to (2^k, 2^k) for k in Z (the set of integers). That way the partitions are "nice" in the sense that each origin is divisible by 2.

The idea is that no two points or polygons can lay in the same quadrant. If there is more than one point in the quadrant, then you must keep recursively partitioning until the point or polygon can be placed, all by itself in a quadrant, that is, until you reach the minimum 1x1 bucket that holds one point. The root is typically the largest origin, which has four children. Each child is a quadrant in the plane, so that the first child is Quadrant I, second child quadrant II, etc.

If you store your circles in the pm quad tree, then you can quickly find the nearest circle by starting at the quadrant associated with the selected point p. once you have located the quadrant of the selected point, then you look for the first ancestor that is a circle.

This nearest neighbor algorithm can run no worse than the height of the pm-quad tree, which is log base 4 of (2^k * 2^k) = log base 4 of (4^k) = O ( k ) where k was our "nice" upper bound.

They are also fun to implement.

http://en.wikipedia.org/wiki/Quadtree

Upvotes: 2

Nicolas78
Nicolas78

Reputation: 5144

You are looking for a QuadTree which lets you store two-dimensional coordinates very efficiently. Since you are running in the browser, I'd recommend the d3.js implementation, which even comes with a very nice example.

Upvotes: 2

Related Questions