Polygon clipping

Description

Richard Suchenwirth 2004-09-22 - Here's very simple code for subtracting one polygon from another, in which it is fully enclosed. Say the big polygon has corners A B C D, the smaller one to be subtracted is E F G H, then the clipped/subtracted polygon has the sequence

 A E H G F E A B C D

where one sees that the corners of the inner polygon are traversed in reverse order. The visual effect is that the bigger polygon has a hole in it, which makes it useful for clipping other canvas contents:

proc poly'clip {p1 p2} {
    set res [lrange $p1 0 1]
    lappend res [lindex $p2 0] [lindex $p2 1]
    foreach {x y} $p2 {
        set res [linsert $res 4 $x $y]
    }
    concat $res $p1
}

On second thought, this version is simpler and makes the algorithm clearer:

proc poly'clip {p1 p2} {
    set p2_ {}
    foreach {x y} $p2 {set p2_ [linsert $p2_ 0 $x $y]}
    concat [lrange $p1 0 1] [lrange $p2 0 1] $p2_ $p1
}

That's all. On a canvas where a picture of JO was already in place, this example code

set poly1 {155 83 424 81 424 288 155 288}
set poly2 {228 147 330 147 334 222 228 222}
$canvas create poly [poly'clip $poly1 $poly2] -fill pink

made John look out of the box like this:

WikiDbImage polyclip.gif

See Also

Iris animation for polygon clipping at work.

Tcl implementation of the Martínez-Rueda-Feito polygon clipping algorithm: [L1 ]

Tcl implementation of Greiner-Hormann polygon clipping algorithm: [L2 ]