QuestionBank

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.