How to find points "clockwise" relative to origin?

I have a collection of points that defines a polygon. For example, let's say the blue square bounded by these points: 20 x -30, 70 x -30, 70 x 20, 20 x 20:

http://lab.wx3.com/temp/shadowcaster_simply.png

I want to find the two points in the polygon that define its edges relative to an observer at the origin. That is, if you were standing at 0,0 which two points would you say were the most clockwise and the most counter-clockwise?

I'm having a hard time thinking of a clean solution that handles all cases, such as the blue square where some of its points have a negative angle relative to origin and some have a positive angle.

• This is for a shadow casting algorithm.
• The origin is not expected to fall within the polygon.

Is it safe to assume the origin will be outside the polygon's convex hull?

I think you can use the 2D cross product. Define it for 2 vectors A and B:

Code:

---

cross2D(A,B) := A.x*B.y - B.x*A.y

---

I'm assuming your coordinates are right handed, you might need to twiddle the sign if it's not.

You want to find the pair of points that maximizes the cross product (measured from the origin). In psuedocode:

Code:

---

Number best_cross = 0.0;
Array[2] best_vertex_pair;
for (a = first vertex to last)
  for (b = first vertex to last)
    if (a != b)
      {
      Number current_cross = cross2D(a,b);
      if (current_cross > best_cross)
        { best_cross = current_cross; best_vertex_pair = [a,b]; }
      }

---

Upon completion, I think best_vertex_pair will have the info you want.

Hope it works! :cap:

Edit, actually thats not right. When the best pair subtends and angle greater than 90 degrees I think it will break down. I will give it more thought.

You pretty much got the answer I was thinking -- but you can search for the largest angle instead of cross-product. It should work as long as you aren't inside the polygon's convex hull (meaning it works for angles up to 180 degrees).

http://i31.tinypic.com/2gumo7a.png

To get it easily, calculate the absolute angle from the origin to each point.

Code:

---

vert[];
angles[];
for(i = 0; i < vert.length; ++i)
  angles[i] = Math.atan2(vert[i].y, vert[i].x);

---

Then calculate the difference between each pair of absolute angles, being careful with overflows. The pair of points with the largest angleDiff is your answer.

Code:

---

angleDiff(a, b) {
  diff = abs(a-b);
  if(diff > pi) return diff-pi;
  return diff;
}

---

I gave it some more thought, and I think you can avoid the winding/overflow issues by minimizing the dot product over the pairs which have positive cross product. New pseudocode:

Code:

---

Number smallest_dot = 1.0;
Array[2] best_vertex_pair;
for (a = first vertex to last)
  for (b = first vertex to last)
    if (a != b && cross2D(a,b) > 0)
      {
      Number current_dot = dot2D( normalize(a), normalize(b) );
      if (current_dot < smallest_dot)
        { smallest_dot = current_dot; best_vertex_pair = [a,b]; }
      }

---

if your polygons are convex, the 2 vertices will each contribute to one edge whose normal points toward the origin and one whose normal points away from it. this assumes, as you've stated, that the vertices are defined relative to light's origin.

Code:

---

extremeVertices = [];

for vertex in vertices
{

  edge 1 = vertex - vertex.prev
  edge 2 = vertex.next - vertex
 
  edge normal 1 = perp( edge 1 )
  edge nomral 2 = perp( edge 2 )

  if( !areSameSign( dot( vertex, edge normal 1 ), dot( vertex, edge normal 2 ) ) )
  { 
      extremeVertices.push( vertex )
  } 

}

Boolean areSameSign( Number n1, Number n2 ) { return n1 * n2 >= 0 }
Vector2D perp( Vector2D v ) { return Vector2D( -v.y, v.x ) }

---

if a polygon isn't convex, you can use its convex hull for the shadow it casts NOT onto itself.

I found the answer I was looking for with front-face culling based on the dot product. Which turned out not to be the answer I wanted because it looked strange when an occlusion shades a nearby object, but not itself:

http://lab.wx3.com/temp/frontface_prob.png

Note the triangle of shadow a wall casts on its neighbors looks bizarre because the wall itself is illuminated. I eliminated this by instead casting shadows from the front faces.

This added the new problem that although the lighting looked right, the walls were basically completely black. But I think I'll be able to produce a good compromise by rendering walls and other occluders on top of the shadow stencil with their luminosity based on surrounding squares.