Determine if a point is inside a polygon made of perfect arcs

Question

I was wondering if there is a simplified way to determine if a point lies inside a polygon shape if the shape is represented only by circular arcs (not bezier or other complicated curves).

My current approach is dividing the curves into small line segments and checking the winding number - which is a common approach although requires thousands of segments for very large curves and high accuracy.

But given i have arcs I am wondering if i can simplify this checking.

I provided a sample image of a shape made of arcs (each arc alternating in color).

Some current observations I found when testing but doesn't succeed for all cases:

If the arcs are ordered for an overall CCW direction of the complete polygon, then you know you're in the shape if you overlap an arc sector and the given arc is also CCW.

You're also not in the shape if you overlap an arc that is going CW (in the case of the concave area of the shape).

However this doesn't quite cover everything after some further testing because you can overlap a CCW and a CW arc area at the same time (see image below):

Wondering if any one has some insights on how this might be solvable to avoid using thousands of line segments to get a winding number which is an expensive calculation to do.

Answer 1

Your winding number idea seems promising: except instead of computing it by cutting each arc into segments, why not find the winding number in closed form?

Let $\mathbf{p}$ be the query point, $\gamma$ one of your circular arcs, and let's say it's parameterized by

$$\gamma(\theta) = \mathbf{c} + r(\cos\theta,\sin\theta)$$ for $\theta\in [\theta_0,\theta_1]$. The contribution of $\gamma$ to the winding number is given by $$w = \frac{r}{2\pi} \int_{\theta_0}^{\theta_1} \frac{1}{\| \gamma(\theta) - \mathbf{p}\|^2}(\gamma(\theta)-\mathbf{p})\cdot \mathbf{n}\,d\theta$$ or $$w = \frac{1}{2\pi} \int_{0}^{\theta_0} \frac{(\gamma(\theta)-\mathbf{p})\cdot(\gamma(\theta)-\mathbf{c})}{\| \gamma(\theta) - \mathbf{p}\|^2}\,d\theta.$$

Simplifying a bit,

$$w = \frac{1}{2\pi} \int_{\theta_0}^{\theta_1} \frac{r^2 + r (c_x-p_x)\cos\theta + r(c_y-p_y)\sin\theta}{\|\mathbf{c}-\mathbf{p}\|^2 + r^2 + 2 r (c_x-p_x) \cos\theta + 2 r (c_y-p_y)\sin \theta}\,d\theta.$$

This is not the world's most pleasant integral, but since it's a trigonometric rational function it has a closed form via tangent half-angle substitution. Mathematica claims it evaluates to $$w = \left[\frac{\theta}{2} + \arctan \left(\frac{(c_y-p_y)\cos \frac{\theta}{2} + (r - c_x + p_x)\sin \frac{\theta}{2}}{(r + c_x-p_x)\cos\frac{\theta}{2} + (c_y-p_y)\sin\frac{\theta}{2}}\right)\right]_{\theta_0}^{\theta_1}$$ but I would take it with a healthy dose of salt and derive it yourself, carefully accounting the possibility that $\theta$ wraps around the fourth to first quadrant, etc.

Answer 2

Shoot a ray from your test point in some direction (like maybe the +X direction). Count the number of times this ray intersects your circular arcs. The test point is inside your contour iff this count is an odd number.

The code has to be written carefully to avoid miscounting in corner cases. For example, store each joint point once, and nudge these points slightly so that none of them lie on your ray.