I have a set of vertices that form a curve in x and y. The curve is smooth, not convex, doesn't intersect and there are no vertical or beyond vertical parts. The x values are unique integers. The picture below illustrates an exemplary curve. You can also see the point light source above the curve. This light is always well above the curve.

Now I want to calculate which of the vertices are shadowed by the mesh. If possible I want to avoid casting rays and calculating where they possibly intersect with the mesh. Since the mesh is a simple line I'm guessing there is an easier way to find the shadowed vertices.

What I tried is calculating the angle between the y-axis and the ray from the light to each vertex with angle = arctan((y_point - y[i]), (x_point - x[i])). This represents the angle between a ray to the left of the light source to each vertex. I Have drawn the rays in the image below. As you can see, the points at x==[3,5,21,22,23] should be shadowed, that's why I have manually coloured them green. Now if the curve was flat, for each point of increasing x the angle calculated above should also be increasing. If it however decreases compared to the previous point, either this point or the previous point are in shadow. The results from this are shown below: As you can see it correctly detects vertices at x==[21,22], but it misses x==23 and it only detects the neighbours of the shadowed vertices on the left.

For x==23 I thought I could calculate the cummax(angle) for each point and compare the point's angle to this cummax angle. If angle < cummax(angle) then that point is shadowed. This now also catches the vertex at x==23, but still fails on the left side.

How can I fix the left side?

I'm working with python but this should apply to any language. If possible I want to avoid casting rays and calculating every edge where the ray could intersect the curve. If you want to replicate the curve the coordinates are

"x": [ 1, 2,  3, 4, 5,6,7,8,13,18,19,20,21,22,23,24,]
"y": [-2,-3,-10,-1,-2,2,3,4, 7, 5, 5, 5, 3, 1, 1, 1,]
"point": (11, 16)

解决方案

Following your own idea, you just need to check the left and right sides of the light separately:

import matplotlib.pyplot as plt
import numpy as np

x = np.array([ 1, 2,  3, 4, 5,6,7,8,13,18,19,20,21,22,23,24,])
y = np.array([-2,-3,-10,-1,-2,2,3,4, 7, 5, 5, 5, 3, 1, 1, 1,])
point = (11, 16)

xp, yp = point
n = len(x)
# find the "index" of the light point: xp will be between x[ip-1] and x[ip]
for ip in range(n):
    if x[ip] >= xp:
        break

angles = np.arctan2(yp-y, xp-x)
cummax = np.maximum.accumulate
cummin = np.minimum.accumulate
shadow_R = angles[ip:] < cummax(angles[ip:])
shadow_L = (angles[ip:None:-1] > cummin(angles[ip:None:-1]))[::-1]
shadow = np.hstack((shadow_L, shadow_R))


plt.figure(1).clf()
plt.plot(x, y, 'o-b')
plt.plot(*point, 'o')
for xi,yi,s in zip(x,y,shadow):
    s = 'r:' if s else 'g'
    plt.plot([xi,xp], [yi,yp], s)