1
$\begingroup$

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".

enter image description here

  • 0
    @lhf, ok, s$u$pplied! Thanks!2012-04-20

1 Answers 1

1

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.

  • 0
    Very nice. Thank you.2012-04-21