How can I cut a graph representing 2D positions into two sub-graphs?

Question

I have a graph where each node is associated with a 2D position. I would like to use a finite line to "cut" this graph into two halves, as shown below:

Note that the cutting line does have a direction. All vertices in that direction remain and aren't cut away.

How can I implement this?

Answer 1

Here's the algorithm I see happening in your question: (I use "inside" meaning specifically not ON the cut line but only inside it)

P = Plane To Cut Across.
For every edge in the graph as Line A->B {
    A_inside = Is point A inside plane P?
    if (point B is on line P && !A_inside) return nothing;

    B_inside = Is point B inside plane P?
    if (point A is on line P && !B_inside) return nothing;

    if (A_inside == B_inside) {
        return Line A->B
    }
    Q = Intersection of line P and line A->B
    if (A_inside) {
        return Line A->Q
    } else {
        return Line Q->B
    }
}