4

We have a legacy program that does some polygon clipping - unions, difference, intersection, exclusive or of polygons and multipolygons.

It uses the University of Manchester's GPC - General Polygon Clipper Library.

We're currently involved in a rewrite. I'd thought that the standard .NET 4.5 libraries might include functionality for manipulating geometries, but I've not been able to find them.

We're considering alternatives to GOC for two reasons:

  1. GPOC depends upon a binary dll, gpc.dll, that needs to be installed on the target machine, and we'd prefer something that was packaged in a .NET assembly.
  2. There is one additional functionality we need that GPC doesn't provide - we need to be expand a polygon by a fixed amount.

To expand upon #2, what we want is a polygon whose borders are just a bit bit beyond the original. Suppose I have a set of old polygons, and I'm drawing a new polygon. I want to clip the new polygon against the union of the old polygons, then I want to expand it by just a bit, so that it overlaps the existing polygons by just a little bit.

In our problem domain, a small overlap is acceptable, but a gap - no matter how small - is not. And given the way floating point comparisons work, having a small overlap is the only way to guarantee that there is not a gap.

In the legacy app, we tried two approaches to creating this expansion:

  1. Write code that walks down each point, determines the direction to the interior, and shift the point to the outside by the desired amount. This turned out to be very complicated code to get right.
  2. Create new polygons that are duplicates of the original, shifted the desired amount north, south, east, and west, then create the final as the union of all the duplicates. This creates polygons with very small spikes at each of the original vertices, significantly increasing the number of points that need to be stored. Since we couldn't get #1 to work reliably, we're currently doing #2.

There are two alternative approaches I can think of:

  1. Some packages allow you to add a buffer to a shape. This would be exactly what we need.
  2. If that doesn't work, if the package allowed for the scaling of polygons, we could just expand the exterior polygons by a calculated amount, and shrink the interior holes by the same.

So, we're looking for geometry libraries that support clipping, and either scaling or buffering, and that are implemented as .NET assemblies, without external DLLs.

Anyone have any pointers?

  • Hi, I've been working on a clipper for a year, and it sounds like you have very painful input data that I would love to throw at my implementation to test with. Would it be possible that you share some sample data to play with? – Wout Dec 25 '17 at 22:21
2

You should give NetTopologySuite a look. We have been using it for 2D geometry operations. It is pure C# and has a lot of functionality, too big to list here. You might have a little bit of trouble finding documentation, but once you get started everything makes sense.

Clipping, buffering, boolean operations and triangulation algorithms (delaunay, voronoi etc.) are elementary stuff in NTS.

  • Can you point me to where it supports expansion and shrinking? – Jeff Dege Oct 2 '15 at 21:00
  • Apart from simple affine transforms (scale, translate, shear, rotate etc.) here's the buffer methods for example: nettopologysuite.github.io/html/… – kagelos Oct 2 '15 at 21:27
2

Have a look at my Clipper library.

Open source freeware library coded in C# (and C++ and Delphi) with very permissive Boost license (which allows use in commercial apps without charge). Can be compiled directly into your applications, so external DLLs aren't needed.

Offsetting (expanding & shrinking) is fully supported.

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.