CODEWITHSUNDEEP
geometryintersection
ChosenOne
ChosenOne

Reputation: 11

How to determine if line intersect simple polygon?

I need to know how to determine fast if line intersects simple polygon. It should work in O(log n) time, where n is number of polygon's vertexes. I searched in google, but I didn't find anything useful, maybe I'm blind. ;) Edit: I'm using C++ but I think language isn't a problem, and it isn't homework, just doing some algorithms training. Geometry is sick. ;) Oh. I forgot it's only in 2d. Thanks for future and actual help.

Upvotes: 1

Views: 2620

Answers (1)

Bigbohne
Bigbohne

Reputation: 1356

I've found a paper who solves this problem really fast:

"Fast MinimumStorage RayTriangle Intersection"

http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf

EDIT: It even contains code :)

Upvotes: 1

Related Questions