ANN: polyclip.go - library for Boolean operations on 2D polygons.

[Mateusz Czaplinski]

Package polyclip provides pure Go implementation of an algorithm by F. Martínez et al. for Boolean operations on 2D polygons (also with holes etc.).
The library is available under MIT/X11-like license.

Download options:
    goinstall github.com/akavel/polyclip.go  # git repo at http://github.com/akavel/polyclip.go

    goinstall bitbucket.org/akavel/polyclip.go  # hg mirror repo at http://bitbucket.org/akavel/polyclip.go

Documentation currently viewable at:

    http://gopkgdoc.appspot.com/pkg/github.com/akavel/polyclip.go

    (big thanks to Gary Burd for providing this excellent service for free!)

    (although seems to be some not-so-new version of godoc there, as the example code in Polygon.Construct doesn't seem to get rendered)

The library is actually a Go port of the as3polyclip library (http://code.google.com/p/as3polyclip, MIT), which is apparently an ActionScript3 port of the public domain C++ code by Martínez (see http://wwwdi.ujaen.es/~fmartin/bool_op.html).

The code seems to be compatible with the current weekly (I'm usually working on tip).

The original paper describes the algorithm as performing in time O((n+k) log n), where n is number of all edges of all polygons in operation, and k is number of intersections of all polygon edges. I didn't perform any analysis, benchmarks or comparisons, I just wanted some polygon clipping algorithm with liberal license, and now I have this need satisfied. The as3polyclip lib's site specifically suggests that it showed *not* to be faster than Vatti's algorithm, but for the latter I couldn't easily find any sensible MIT/BSD-licensed code, other than the GPC library, which is free only for non-commercial use.

I've done some visual testing of the code with dozens of sample polygons from Martínez's page, which helped me kill some bugs, now it seems to be working pretty well. I'll try to attach some sample image, hope it gets through to the mailing list. I can upload the code for a helper webapp for easy visualization of the operations, but I'm not sure where to put it in the repositories, and a bit tired fighting with github+bitbucket+hg+goinstall. Shall you be interested in this code, *please* do nudge me, knowing someone wants it will hopefully help me get through that again.

Have fun!

cheers

/Mateusz Czapliński.

[Brad Fitzpatrick]

Two minor style points, just looking at the godoc:

func (c Contour) BoundingBox() (bb Rectangle)

You should avoid naming return values in exported methods if it doesn't add clarity about what the values are. In this case it's obvious that it's a bounding box, since the method is named that.  The "bb" and parens are just stutter & noise.

Also, even if you're not going to be modifying the receiver in some of these functions (like BoundingBox, Clone, Contains), it's still much more idiomatic to take a pointer receiver (c *Contour) instead of a value (c Contour).  It won't affect the appearance of existing caller code, and it'll mean that people can still call the methods when they have pointers to the values.

[Mateusz Czaplinski]

On Tue, Dec 27, 2011 at 4:42 AM, Brad Fitzpatrick <brad...@golang.org> wrote:

Two minor style points, just looking at the godoc:

func (c Contour) BoundingBox() (bb Rectangle)

You should avoid naming return values in exported methods if it doesn't add clarity about what the values are. In this case it's obvious that it's a bounding box, since the method is named that.  The "bb" and parens are just stutter & noise.

Hm, that sounds reasonable, thanks. Will try to update when I have some time for that.
 

Also, even if you're not going to be modifying the receiver in some of these functions (like BoundingBox, Clone, Contains), it's still much more idiomatic to take a pointer receiver (c *Contour) instead of a value (c Contour).  It won't affect the appearance of existing caller code, and it'll mean that people can still call the methods when they have pointers to the values.

Hmh, here I'm not quite sure what do you mean. I believe these methods can still be called on pointers to values, I've written some small snippet to verify this concept and it seems to be working ok:
    http://play.golang.org/p/TuffeFV-VF
but maybe I misunderstood something about your suggestion?
And as for other arguments, I don't see why a pointer receiver would be considered more idiomatic; currently I believe quite the opposite, that there's no need to introduce address of a receiver when the methods are clearly read-only, and the receiver when passed as a value is just three words (a slice). Also it seems to me that there are similar cases in the standard packages, like: http://golang.org/pkg/image/#Rectangle.Empty

----
As an unrelated "bonus", I wanted to show an usage example for the library, which isn't properly displayed on the gopkgdoc site, but would be displayed on a local godoc instance (hope the formatting won't get squashed now):

// [{1 1} {1 2} {2 1}]
func ExamplePolygon_Construct() {
    subject := Polygon{{{1, 1}, {1, 2}, {2, 2}, {2, 1}}} // small square
    clipping := Polygon{{{0, 0}, {0, 3}, {3, 0}}}        // overlapping triangle
    result := subject.Construct(INTERSECTION, clipping)

    // END OF EXAMPLE, just printing the result in reproducible order now:
    out := []string{}
    for _, point := range result[0] {
        out = append(out, fmt.Sprintf("%v", point))
    }
    sort.Strings(out)
    fmt.Println(out)
}

Thanks,
/Mateusz Czapliński.