Handmade Hero » Forums » Code » Line and Polygon intersection point
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!