Determine if the extension cut is dominated (see definition below)

[dreamy grail]

Hey guys I’m really struggling with this problem and can not figure out how to do it if my life depended on it. It seems to be rather easy but I am just missing something. I have some resources on it and some code I’ve been working on that I can send if needed. Here is the description.

I'm given a simple polygon and extension cuts (seen below), and I need to find out which of the extension cuts are essential/ no dominated. Definitions: Given a point p of a polygon, we say that an extension cut c is forward with respect to p if p lies to the left of the cut c. Otherwise c is backward with respect to p; see Fig. 2(a).

An extension cut c dominates another extension cut c' if all points in P to the left of
c are also to the left of c'. We say that an extension cut is an essential cut if it is not dominated by any other extension cut. We can view the essential cuts as having a cyclic ordering specified by the start points of the cuts as they are encountered during a counterclockwise scan of the polygon boundary. In this way each cut has a predecessor and a successor. The set of essential cuts of the polygon P will henceforth be denoted C. We can view the essential cuts as having a cyclic ordering specified by the start points of the cuts as they are encountered during a counterclockwise scan of the polygon boundary. In this way each cut has a predecessor and a successor. The set of essential
cuts of the polygon P will henceforth be denoted C.

I really would appreciate the help.
If you need more resources please ask. The final form of this project will be the Watchman route problem. I’m attaching two photos. The first one is an example of extension cuts (I already have those) and the second is an example of essential cuts (the black lines).

[dreamy grail]

I think we may be able to do it in a way that modifies depth first search? Like seeing if one polygon contains the other and we split it at every cut?

[dreamy grail]

Notes for myself or anyone else: the polygon is drawn with directed angles counter clockwise. When we make the extension cuts, we need to give them a direction as well. This is to ensure that we can determine that what is on left of the cut because head and tail that follows the direction of the polygon.

[dreamy grail]

If the (left set of points) L(c) is contained in L(c’) then Cut c dominates Cut c’

I need to make a code to make these subsets. (Do they contain the endpoints?)

[dreamy grail]

I’ll check to see if the two cuts intersect first as long as the point of intersection is not equal to either cuts’ start or end point

If the cuts do not intersect then I check then I can check to see if one subset contains the other

[severe laurel]

Interested to know what is going on.. but I'm struggling to comprehend.. it's a very mathsy way of describing things which makes it a bit harder for me to comprehend.

[dreamy grail]

problem solved

If you view the polygon as a directed graph, you can get the left subsets of each cut in the polygon and compare them