
February 10th, 2009, 06:53 PM
#1
Determine Points within a target semicircle (2D)
I have a list of twodimensional points and I want to obtain which of them fall within a semicircle.
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 upperbound of the target rectangle.
This does not work for a semicircle as you cannot determine an effective upper/lower x and y bounds for it. The semicircle can have any orientation.
Worst case, I will find the least value of a dimension (say x) in the semicircle, 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, 03:47 AM
#2
Re: Determine Points within a target semicircle (2D)
Originally Posted by khayman218
This does not work for a semicircle as you cannot determine an effective upper/lower x and y bounds for it. The semicircle can have any orientation.
Seems to me that the smallest square containing the (full) circle gives you pretty good bounds.
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
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
