Handmade Hero»Forums»Code
Manish
6 posts
None
Line and Polygon intersection point
Is there is a quick way to find the intersection point of a line segment with a given polygon. Polygon vertices is limited to max 32.

Currently I am using below line segment intersection algorithm from Graphics Gems III. Algorithms takes two lines at a time. I am just looping the line segment over each polygon edges.

http://www.realtimerendering.com/...rces/GraphicsGems/gemsii/xlines.c

Wondering if there is a better way of doing it?

Thanks!
Mārtiņš Možeiko
2559 posts / 2 projects
Line and Polygon intersection point
Usually that is good enough. Is that slow for your use case? How many polygons against do you have to calculate the line segment intersection?
Manish
6 posts
None
Line and Polygon intersection point
Thanks for quick reply.

There is only one polygon with maximum 32 vertices. I have close to 10k lines in a tight look to compare against that polygon.

I am not sure if the approach i am taking is the best in terms of performance so i started this thread to discuss an alternative against which i can time and compare.
Mārtiņš Možeiko
2559 posts / 2 projects
Line and Polygon intersection point
Maybe quick broadphase can help you. Calculate AABB of polygon, and then do quick test for line segments vs rectangle. If that test fails then its 100% that this particular segment doesn't interesect polygon.
Manish
6 posts
None
Line and Polygon intersection point
Yea, that's a nice optimization. I will try that!