# 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? – MickLH Jan 16 '14 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. – Quonux Jan 16 '14 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) – Quonux Jan 16 '14 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. – MickLH Jan 16 '14 at 16:34