Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Very nice. Thank you. –  Steve Apr 21 '12 at 3:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.