Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Hi, I am looking for an elegant way to do ray and polygon intersections in 2d. I don't care about languages.

Now what I'm doing is taking a line that lies on the ray (with a screen length) and testing line-to-line intersections between this derived-ray and all lines formed by each consecutive vertices in the polygon.

This, for now, is good even if I don't know which parts of the ray are inside or outside the polygon (in cases it is concave one). But for now I don't need this information, even if a general approach could maybe give it.

I don't care about self-intersection polygons.

Any advice? maybe triangulizing the polygons could be an idea?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

For 2D, I don't think you can do much better than just intersecting the boundary edges. If you triangulate your polygon, you will end up with more edges to test against, making your test slower.

share|improve this answer
    
and what about understand if segments are inside or outside? –  nkint May 8 '12 at 12:00
    
@nkint if you know whether your ray starts inside our outside, you could count the intersections in distance order. If you start outside, from the first to the 2nd closest intersection must be inside, from the 2nd to the 3rd could be outside (or inside a hole or cavity), 3rd to 4th inside again...etc –  melak47 May 8 '12 at 12:06
add comment

The simplest algorithm is to test ray intersection with each edge. It has linear complexity. You can skip edges, e.g. when ray goes right and both edge points are on the left side from ray origin.

Here is my implementation in JavaScript: http://polyk.ivank.net/?p=demos&d=raycast

There are algorithms with logarithmic complexity for this, but you will have to make some data structure upon your polygon (BVH, KD-tree, octree...).

share|improve this answer
    
I like your demonstration but I just want to point out that there is a bug. There appear wrong rays at each border that is perfectly vertical or horizontal. –  danijar Jan 9 '13 at 17:58
1  
Thank you very much for pointing it out! :) I fixed it :) –  Ivan Kuckir Jan 9 '13 at 23:52
1  
I really like that. –  danijar Jan 10 '13 at 8:39
add comment

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.