February 10th, 2009, 07:53 PM
Determine Points within a target semi-circle (2D)
I have a list of two-dimensional points and I want to obtain which of them fall within a semi-circle.
Originally, the target shape was a rectangle aligned with the x and y axis. So the current algorithm sorts the pairs by their X coord and binary searches to the first one that could fall within the rectangle. Then it iterates over each point sequentially. It stops when it hits one that is beyond both the X and Y upper-bound of the target rectangle.
This does not work for a semi-circle as you cannot determine an effective upper/lower x and y bounds for it. The semi-circle can have any orientation.
Worst case, I will find the least value of a dimension (say x) in the semi-circle, binary search to the first point which is beyond it and then sequentially test the points until I get beyond the upper bound of that dimension. Basically testing an entire band's worth of points on the grid. The problem being this will end up checking many points which are not within the bounds.
February 18th, 2009, 04:47 AM
Re: Determine Points within a target semi-circle (2D)
Seems to me that the smallest square containing the (full) circle gives you pretty good bounds.
Originally Posted by khayman218
That being said, it might be more effective to first test if a point is within the full circle (as determined by the distance to the center point of the circle) and then test if it is in the right half, which is a simle linear inequality.
Cheers, D Drmmr
Please put [code][/code] tags
around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
Tags for this Thread
Click Here to Expand Forum to Full Width