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:

2d Graph

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?

  • \$\begingroup\$ 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? \$\endgroup\$ – MickLH Jan 16 '14 at 16:09
  • \$\begingroup\$ 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. \$\endgroup\$ – 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
  • \$\begingroup\$ thx, what about the connections that are cutted (notice the lines on the cut line) \$\endgroup\$ – Quonux Jan 16 '14 at 16:34
  • \$\begingroup\$ 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. \$\endgroup\$ – MickLH Jan 16 '14 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.