Math find number of points of intersection between polygon and horizontal line segment with length x2-x1

Math find number of points of intersection between polygon and horizontal line segment with length x2-x1,math,geometry,Math,Geometry,How to find number of points of intersection between a horizontal line segment(many) and a polygon(convex) with n sides in fastest way possible.Thanks for answering.

How to find number of points of intersection between a horizontal line segment(many) and a polygon(convex) with n sides in fastest way possible.Thanks for answering.


#1

In the simplest case - just check for intersection with all sides that has y-coordinates of ends at different sides of horizontal line.

If you want to use the same polygon with some horizontal segments - build sorted list of edges (or even interval tree) to find candidates fast (in log(n) time with binary search)


#2

can u please explain in detail how to do it.code posted will be helpful.thanks again.

#3

Code that checks intersection of polygon edges with inifinite horizontal line at testy. Instead of c != c calculate intersection with limited segment.