algorithms
geometry
computational geometry
point detection
semi-circle

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:

text
(x - cx)^2 + (y - cy)^2 <= r^2

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:

python
1def in_upward_semicircle(x, y, cx, cy, r):
2    dx = x - cx
3    dy = y - cy
4    inside_circle = dx * dx + dy * dy <= r * r
5    return inside_circle and y >= cy
6
7print(in_upward_semicircle(1, 1, 0, 0, 2))   # True
8print(in_upward_semicircle(1, -1, 0, 0, 2))  # False

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.

text
1dx = x - cx
2dy = y - cy
3
4inside half if dx * dir_x + dy * dir_y >= 0

That condition means the point lies on the same side of the diameter as the facing direction.

General Python Implementation

python
1def in_semicircle(x, y, cx, cy, r, dir_x, dir_y):
2    dx = x - cx
3    dy = y - cy
4
5    if dx * dx + dy * dy > r * r:
6        return False
7
8    return dx * dir_x + dy * dir_y >= 0
9
10print(in_semicircle(1, 1, 0, 0, 2, 0, 1))      # Upward semicircle
11print(in_semicircle(1, -1, 0, 0, 2, 0, 1))
12print(in_semicircle(1, 0, 0, 0, 2, 1, 0))      # Right-facing semicircle

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:

python
points = [(0, 1), (1, 1), (1, -1), (3, 0)]
inside = [p for p in points if in_semicircle(p[0], p[1], 0, 0, 2, 0, 1)]
print(inside)

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 x or y comparison.
  • 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.

Course illustration
Course illustration

All Rights Reserved.