manishsharma
Manish 6 posts

#12906
Line and Polygon intersection point 3 months ago
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! 
mmozeiko
Mārtiņš Možeiko 1503 posts
1 project

#12908
Line and Polygon intersection point 3 months ago
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?

manishsharma
Manish 6 posts

#12910
Line and Polygon intersection point 3 months ago
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. 
mmozeiko
Mārtiņš Možeiko 1503 posts
1 project

#12911
Line and Polygon intersection point 3 months ago
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.

manishsharma
Manish 6 posts

#12912
Line and Polygon intersection point 3 months ago
Yea, that's a nice optimization. I will try that!
