ID:1380878
 
(See the best response by Zaoshi.)
So I've been developing a lighting system that uses the new features in the BYOND v500 beta.

One of the goals of this lighting system is to be able to draw shadows for circular objects, and polygonal objects (of arbitrary shape and orientation). The shadows for circular objects were easy enough to compute, but I'm having some problems with the polygonal ones.

Right now, these polygonal objects have a list of vector objects (in clockwise order) for the vertices. These vectors point from the center of the polygon to the vertex, with pixels being the unit of distance.

In order to draw these shadows, I need to be able to determine which vertices are the "extreme points", that is which vertices are the ones that define the shadow's silhouette. This is necessary to determine how to skew, scale, and rotate the shadows with atom.transform

Here's a screenshot example: http://puu.sh/4w6zi.png
Notice that the top left and bottom right vertices in this case are the "extreme points".

The way I'm doing this right now is I'm looping through each of the vertices and finding the angle from the light source to each vertex. I then pick the two vertices that are farthest apart according to their angles relative to the light source. While this does work, it's not exactly fast because of the number of trigonometric functions I am using (arctan). There is the possibility that I screwed up the implementation of my algorithm for this as well; it doesn't always yield the correct result. It's also possible that my transformations are incorrect.

I am wondering if anyone here has any better alternative algorithms or suggestions.
Best response
Are you sure your light source is outside polygon?

As for algorithm, you could try something along these lines:
1. Get angle from light to polygon
2. Make -angle rotation matrix (or inverse +angle rotation matrix)
3. Transform all vertices
4. Pick left-most and right-most vertices as silhouette points

Though this method won't work correctly for concave polygons.
I am not designing for concave polygons. I am also not planning to compensate for light within a polygon. All of my screenshots thus far are lights outside of the polygons.

Ill try your algorithm tonight and post an update