CODEWITHSUNDEEP
c#grid
user3148946
user3148946

Reputation: 45

A clever way to find nodes within a radius in a grid c#?

enter image description here

Suppose that we have a grid similar to the one in the image. The grid can also contain rectangular nodes. Now I want to find all the nodes within a radius same as illustrated on that image. A way of doing this is by checking all the nodes starting from 0,0.

For each node I have to calculate the distance to node (i,j). This takes a lot of time especially if the number of nodes is huge.

There should be a better way to do this. Considering that I know the center of the circle (node (i,j)) maybe I can develop a recursive function starting from i,j instead of checking each one of them.

Could you help me with a clever method for this purpose?

The distance measure is Euclidian Distance.

Upvotes: 4

Views: 1295

Answers (2)

Duncan Finney
Duncan Finney

Reputation: 2074

I'm not sure if this would be faster or slower computationally compared to the distance method you mentioned in your post, but Point-In-Polygon is a pretty common in computer science. It would be worth trying the ray-casting algorithm and see if it improves performance.

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

Upvotes: 1

germangb
germangb

Reputation: 46

You could either test all the cells inside the bounding box of the circle or, if you want to be a little more strict, perform a breadth search, using a queue-like data structure.

Upvotes: 1

Related Questions