# Polygon: Internal Rays

Suppose I have an arbitrary non-self-intersecting polygon.

I want to generate a list of points which lie on the edges of this polygon according to the following procedure:

I iterate over each edge of the polygon and extend a ray from each vertex on the end of the edge until it intersects another edge.

However, I want to limit the rays to the interior of the polygon.

I'm not sure how to achieve this last part (limiting the rays to the interior of the polygon).

EDIT:

For example, in the picture below, I want the extra point in the green circle, but NOT the extra point under the green "X".

-
Could you show us a picture of what you're trying to find? –  lhf Apr 20 '12 at 18:38
@lhf, ok, supplied! Thanks! –  Steve Apr 20 '12 at 19:21

For each interior angle larger than $\pi$, you will have two such interior rays, while angles less than $\pi$ do not produce rays. You can check the obtuseness of $\angle ABC$ via the sign of the area formula $$\left| \begin{array}{ccc} 1 & 1 & 1 \\ A_x & B_x & C_x \\ A_y & B_y & C_y \end{array} \right|$$ which is fast, needing only six multiply-and-add instructions.
To see where a ray $\stackrel{~~\longrightarrow}{AB}$ first hits another side, you will in general need to check the distance to each edge that $\stackrel{~~\longrightarrow}{AB}$ hits, and keep track of the closest one.
$\stackrel{~~\longrightarrow}{AB}$ hits edge $CD$ iff $B$ is inside $\triangle ACD$. Again, you can check this by checking whether the area formula signs of $ABC$, $CBD$, and $DBA$ all match. (Note that two of these calculations are shared with the edges neighboring $CD$.)
If $\stackrel{~~\longrightarrow}{AB}$ does hit $CD$, compute their intersection point and its distance to $B$. The closest of all such intersection points for $\stackrel{~~\longrightarrow}{AB}$ should then be added to the list that you say you want to generate.