11

Supposed that I have many polygons, what is the best algorithm to construct a polygon--maybe with holes- out of the union of all those polygons?

For my purpose, you can imagine each piece of a polygon as a jigsaw puzzle piece, when you complete them you will get a nice picture. But the catch is that a small portion ( say <5%) of the jigsaw is missing, and you are still require to form a picture as complete as possible; that's the polygon ( or polygons)-- maybe with holes-- that I want to form.

My naive approach is to take two polygons, union them, and take another polygon, union it with the union of the two polygons, and repeat this process until every single piece is union. Then I will run through the union polygon list and check whether there are still some polygons can be combined, and I will repeat this process until a satisfactory result is achieved.

But this seems to be like an extremely naive approach. I just wonder is there any other better algorithm?

Graviton
  • 81,782
  • 146
  • 424
  • 602
  • I posted answer on the same question here: http://stackoverflow.com/a/19475433/904679 – xtmq Oct 20 '13 at 08:41

2 Answers2

9

You need a polygon clipping library - and I'll plug my own Clipper library since it's written in C# (and C++ and Delphi), it's open source freeware, and it'll do exactly what you want.

My naive approach is to take two polygons, union them, and take another polygon, union it with the union of the two polygons, and repeat this process until every single piece is union

That would be a very inefficient approach. A much better way would be to 'union' them all in one operation ...

using ClipperLib;
using Polygon = List<IntPoint>;
using Polygons = List<List<IntPoint>>;
...

//precondition: all your polygons have the same orientation 
//(ie either clockwise or counter clockwise)
Polygons polys = new Polygons(PolyCnt);
for (int i = 0; i < PolyCnt; i++)
    polys.Add(loadPolyFromFile(String.Format("poly{0}.txt", i +1)));

Polygons solution = new Polygons();
Clipper c = new Clipper();
c.AddPolygons(polys, PolyType.ptSubject);
c.Execute(ClipType.ctUnion, solution, 
    PolyFillType.pftNonZero, PolyFillType.pftNonZero);

//code to display solution here.
Angus Johnson
  • 4,565
  • 2
  • 26
  • 28
  • Your `precondition` comment just solved a problem I have been struggling with all morning. I was having a union result in a form of difference and I could not figure out what the heck I was doing wrong. It turns out that I was writing in a counter clockwise polygon with a set of clockwise polygons. I'm sure this is in your documentation somewhere, but I missed it. Your docs are pretty solid in general, so good job. I have been very happy with the ported go.clipper library so far. – swill Dec 29 '16 at 19:27
  • It would be nice to have a NuGet package for the C# version of this library – Guillaume Aug 22 '20 at 11:54
1

That's brute force what's your doing. A better way of doing brute force is branch and bound. But that still scales horribly.

The next step is to try metaheuristic algorithms (tabu search, simulated annealing, ...) or just reuse a framework like Drools Planner (open source, java) which implements them for you.

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
  • any pointers on how the metaheuristic algorithm can help? I see the wiki, but it has little reference to the problem I described above. – Graviton Dec 25 '10 at 01:15
  • Metaheuristics are about "moving stuff", so in your case "move polygons; or add or remove a polygon". Take a look at tabu search, that's pretty easy to implement. – Geoffrey De Smet Oct 14 '11 at 09:58
  • If you're only looking into computing the union of the polygons and not some alternative solution to your underlying problem, then the correct approach would be to just union all the polygons at once instead of in pairs. For example a sweep line algorithm for computing the union can be adapted to union the whole set instead of a pair. The clipper answer mentioned below sounds good. – jjrv Feb 23 '12 at 13:15
  • The OP also asked the question on Math, and I think the answers are better (much more concrete). http://math.stackexchange.com/questions/15815/how-to-union-many-polygons-efficiently – Pimin Konstantin Kefaloukos Jan 22 '13 at 11:20