What algorithm can I use to determine points within a semi-circle?
Master System Design with Codemia
Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.
Introduction
To decide whether a point lies inside a semicircle, you need two tests: the point must be inside the full circle, and it must also lie on the correct side of the diameter. For axis-aligned semicircles that is a simple coordinate comparison, and for arbitrarily rotated semicircles a dot-product test is the clean general solution.
Start with the Full Circle Test
A point is inside a circle if its distance from the center is less than or equal to the radius. To avoid an expensive square root, compare squared values instead.
If the center is (cx, cy), radius is r, and point is (x, y), then:
If this is false, the point is definitely outside the semicircle too.
Axis-Aligned Semicircle
For a semicircle pointing upward, the point must satisfy both:
- inside the circle
- '
y >= cy'
For a downward-facing semicircle:
- inside the circle
- '
y <= cy'
For left or right orientations, use x <= cx or x >= cx.
Here is a simple Python implementation for the upward case:
This is an O(1) test per point and is all you need when the semicircle is aligned to the axes.
A Better General Form: Direction Vector
If the semicircle can face any direction, represent its “open” side with a unit direction vector. For example:
- up:
(0, 1) - right:
(1, 0) - diagonal up-right:
(0.707, 0.707)
After confirming the point is inside the circle, compute the dot product between the point-offset vector and the facing direction.
That condition means the point lies on the same side of the diameter as the facing direction.
General Python Implementation
As long as the direction vector points toward the kept half, this works for any rotation.
Why the Dot Product Works
The diameter splits the circle into two halves. The dot product tells you on which side of the split line the point lies relative to the chosen direction.
If the dot product is:
- positive: same half as the direction
- zero: exactly on the diameter
- negative: opposite half
That makes the semicircle test mathematically clean and easy to generalize.
Testing Many Points Efficiently
If you need to check thousands of points, the same formula applies. The total cost is still linear in the number of points, because each point takes constant time.
For example:
This pattern is common in graphics, collision checks, and spatial filtering.
Boundary Behavior
Decide early whether points exactly on the boundary count as inside. Using <= for the circle check and >= for the half-plane check includes boundary points. If your application wants strict interior membership only, use < and >.
That decision matters in games, CAD tools, and geometry engines where edge cases are visible.
Common Pitfalls
One common mistake is checking only the half-plane condition and forgetting the radius check. That turns the test into an infinite half-plane instead of a semicircle.
Another issue is using a non-normalized direction vector inconsistently. The sign of the dot product still works, but keeping the vector normalized makes reasoning clearer.
A third pitfall is not deciding how boundary points should be treated. Ambiguity there leads to inconsistent results in adjacent shapes.
Summary
- A point is in a semicircle only if it is inside the full circle and on the correct side of the diameter.
- For axis-aligned cases, combine the circle test with a simple
xorycomparison. - For arbitrary orientation, use a dot-product test with a facing direction vector.
- Each point check runs in constant time.
- Decide whether boundary points count as inside before implementing the test.

