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.
Re: Determine Points within a target semi-circle (2D)
Quote:
Originally Posted by
khayman218
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.
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.
