What algorithm can I use to determine points within a semi-circle?

Question

How can I do this on a grid with several "centers", and therefore, having coincident points that I want to count only once?

What is the most efficient way to do this?

Answer 1

To find out if a point, P, is within a semi-circle I would consider a two part test:

1. Is P within the radius, R, of the center, C?
2. Is P in the correct (i.e. occupied) half plane?

Part (1) is easy: compare (P_x-C_x)^2 + (P_y-C_y)^2 (in 2d, add the Z direction in 3d, of course) with R^2 (don't bother with the square-roots, they take time and don't add anything).

Part (2) is almost as easy: define the vector b = B - C that bisects the semi circle pointing into the occupied half plane. Then compute vector v = P - C and take the dot product with b. If the result is positive the point is in the occupied half plane, if negative the point is in the unoccupied half place and if 0 the point falls on the dividing line. The dot product in 2d is v*b = v_x*b_x + v_y*b_y as usual.