Point in circle segment

Question

I have a circle I want to divide up in to a number of segments all defined by X and Y coordinates. How to I test to see if a point (X, Y) is in a particular segment?

A code example would be preferable.

Explain on which basis you want to divide into smaller sagments?And btw this might be helpful. [equation-for-testing-if-a-point-is-inside-a-circle](http://stackoverflow.com/questions/481144/equation-for-testing-if-a-point-is-inside-a-circle) — eMad, Nov 29 '14 at 17:18
In addition to the above, the way this is solved could be vary by programming language. If this is not a programming question, please see [math stackexchange](http://www.math.stackexchange.com) — AdamMc331, Nov 29 '14 at 17:41
@haz hazzz You clicked the ✓ to accept my answer, which implies it solved your problem. If it didn't you should un-click it and clarify whether it is segments or sectors you want, and how they are laid out. — Boann, Nov 30 '14 at 12:15

score 2 · Answer 1 · answered Nov 29 '14 at 17:41

2

You don't need to use trigonometry for this (and in general, trigonometry should be avoided whenever possible... it leads to too many precision, domain, and around-the-corner problems).

To determine whether a point P is counter-clockwise of another point A (in the sense of being in the half-plane defined by the left side of a directed line going through the origin and then through A), you can examine the sign of the result of Ax*Py - Ay*Px. This is generally known as the "perpendicular dot product", and is the same as the Z coordinate of the 3D cross product.

If there are two points A and B (with B defining the CCW-most extent) defining a sector, and the sector is less than half the circle, any point which is CCW of A and CW of B can be classified as in that sector.

That leaves only a sector which is more than half of the circle. Obviously, a given set of points can only define at most one such sector. There's clever things you can do with angle bisection, but the easiest approach is probably just to classify points as in that sector if you can't classify them as being in any other sector.

Oh, forgot to mention -- determining the order of the points for the purposes of pairing them up for sectors. Not to go against my previous advice, but the most straightforward thing here is just to sort them by their atan2 (not atan... never ever use atan).

answered Nov 29 '14 at 17:41

Sneftel

40,271
12
71
104

Very insightful, thanks for posting (+1). What's an *around-the-corner problem*? :-) – NPE Nov 29 '14 at 17:44
@NPE For instance, with the atan2 method, needing to remember that P is in the AB sector if its angle is greater than B's and less than A's and the AB sector includes where the angle goes around the corner from +pi to -pi. – Sneftel Nov 29 '14 at 18:13
Don't sort points by the angle of the tangent (`atan(x/y)` or `atan2(x/y)`), but by the tangent (`x/y`) directly. You have to sort the two halves of the plane (x<0 and x>0) separately, and then simply concatenate the two sub-lists (in whichever order). – Cimbali Nov 29 '14 at 18:48
@Cimbali sorting by `x/y` will cause problems with y's near zero. To go that route, it's best to split into quarters based on `x <> y` and `|x| <> |y|`, and sort either by `x/y` or `y/x`. – Sneftel Nov 30 '14 at 15:30
I meant y/x, not x/y btw. @Sneftel There's one corner case when `x==0` and then you know exactly (from the sign of y) where your point is. I don't think that's a problem, not so hard. – Cimbali Nov 30 '14 at 17:34
@Cimbali Coordinates near 0 are problematic too, as their reciprocals can drive the quotient to infinity. – Sneftel Nov 30 '14 at 18:13
@Sneftel yeah, that means they are close the the vertical in polar representation. Just because the division is done inside `atan2` (followed by a call to `tan` and some logic on quarters) doesn't make it less or more valid -- less confusing if you need the angle, I'll grant you that. `tan` (thus `atan`) is monotonous, so its equivalent for the sorting to use the angle or the tangent. – Cimbali Nov 30 '14 at 18:41
1

@Cimbali `atan2` implementations are more clever than that... they compare magnitudes before performing the division. Mathematically the two are of course equivalent. But deferring to the existing algorithm is a useful way to avoid the tricky cases. – Sneftel Nov 30 '14 at 19:21

score 0 · Answer 2 · answered Nov 29 '14 at 17:32

0

Use the polar coordinate system centred at the centre of the circle, and examine the angular coordinate (φ in the Wikipedia article).

What exactly you do with φ depends on how your segments are defined. For example, if you have n equal segments that start at 0 radians, floor(φ * n / (2 * π)) will give you the segment number.

answered Nov 29 '14 at 17:32

NPE

486,780
108
951
1,012

1

The angle will give you a sector, not a segment. – Cimbali Nov 29 '14 at 18:50

helloflash · Answer 3 · 2014-12-01T13:00:28.000

Your segment is defined by two intersections between the circle and a line. You just have to know if:

The angle between the center of your circle and your point is between the angles formed by the two previous points and the center.
the point is in the circle (the length from this point to the center is smaller than the radius)
from what side is the point compared to the line (it must be beyond the line).

Remark

In geometry, a circular segment (symbol: ⌓) is a region of a circle which is "cut off" from the rest of the circle by a secant or a chord.

Here is a segment:

enter image description here

score -1 · Accepted Answer · answered Nov 29 '14 at 17:41

If x & y are not already relative to the center of the circle, subtract the coordinates of the center of the circle:
```
x -= circle.x
y -= circle.y
```
Use atan2 to get the angle of the point about the origin of the circle:
```
angle = atan2(y, x)
```
This angle is negative for points below the x-axis, so adjust to always be positive:
```
if (angle < 0) angle += 2 * pi
```
Assuming your segments are equally spaced, use this formula to get the index of the segment:
```
segment = floor((angle * numSegments) / (2 * pi))
```

If you find the result is referring to a segment on the opposite side of the circle to what you want, you might have to do y = -y in the beginning or a segment = (numSegments - 1) - segment at the end to flip it round the right way, but it should basically work.

The angle will give you a sector, not a segment. – Cimbali Nov 29 '14 at 18:51 — Cimbali, Nov 29 '14 at 18:51
A sector is not a segment! – helloflash Nov 29 '14 at 21:35 — helloflash, Nov 29 '14 at 21:35

Point in circle segment

4 Answers4