algorithm - Finding whether a line segment is completely inside the Polygon or not

Question

How I can find whether a given diagonal(line segment joining two vertices of polygon other than polygon edge) is valid diagonal for a given polygon ..? I am writing code in LEDA. Is there any specific function in LEDA for validating diagonal .? need help.

Answer 1

You can call the intersection method of your polygon which will return the intersections with a segment. If there are other intersections than the two endpoints (i.e. more than 2 intersections) then it is not valid. Here is the function declaration:

list<POINT> Polygon.intersection(const SEGMENT& s)

UPDATE: As j_random_hacker pointed out this can fail if the diagonal is outside the polygon. For weakly simple polygons this could be avoided by checking if an inner point of the segment lies outside the polygon.

bool   Polygon.outside(const POINT& p)

However this could still fail for complex polygons like self-intersecting ones. Depending on what is a valid diagonal it could even fail for weakly simple polygons if there are coincident edges connecting the boundary of a hole and the outside boundary of a polygon.