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

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?

• This is somewhat ambiguous. If the red line were just a tiny bit lower, would you want that dangling edge that would be left? Or does it have a grid structure to maintain? Jan 16, 2014 at 16:09
• This caes is ambiguous, it doesn't have to maintain a grid structure. If the red line were a bit lower there would be an edge to the right top corner. Jan 16, 2014 at 16:15

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
}
}

• thx, what about the connections that are cutted (notice the lines on the cut line) Jan 16, 2014 at 16:34
• I added some logic at the top to account for deleting the lines with one (or more vertices) exactly on the plane, and the other outside it. Jan 16, 2014 at 16:34