0
\$\begingroup\$

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 triangulating the polygons could be an idea?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ and what about understand if segments are inside or outside? \$\endgroup\$
    – nkint
    May 8, 2012 at 12:00
  • \$\begingroup\$ @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 \$\endgroup\$
    – user13213
    May 8, 2012 at 12:06
1
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – danijar
    Jan 9, 2013 at 17:58
  • 1
    \$\begingroup\$ Thank you very much for pointing it out! :) I fixed it :) \$\endgroup\$ Jan 9, 2013 at 23:52
  • 1
    \$\begingroup\$ I really like that. \$\endgroup\$
    – danijar
    Jan 10, 2013 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .