[ACCEPTED]-How to intersect two polygons?-intersection

Accepted answer
Score: 17

Arash Partow's FastGEO library contains implementations 9 of many interesting algorithms in computational 8 geometry. Polygon intersection is one of 7 them. It's written in Pascal, but it's 6 only implementing math so it's pretty readable. Note 5 that you will certainly need to preprocess 4 your edges a little, to get them into clockwise 3 or counterclockwise order.

ETA: But really, the best way to do this is to not do this. Find 2 another way to approach your problem that 1 doesn't involve arbitrary polygon intersections.

Score: 14

If you are programming in .NET Framework, you 3 may want to take a look at SqlGeometry class 2 available in .NET assemblies shipped as 1 Microsoft SQL Server System CLR Types

The SqlGeometry class provides STIntersection method

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry intersection = g1.STIntersection(g2);
Score: 12

What I think you should do

Do not attempt to do this yourself if you 43 can possibly help it. Instead, use one 42 of the many available polygon intersection 41 algorithms that already exist.

I was strongly 40 considering the following codebase on the 39 strength of their demonstration code and 38 the fact that they mentioned their handling 37 of most/all of the weird cases. You would 36 need to donate an amount (of you/your company's 35 choice) if you use it commercially, but 34 it's worth it to get a robust version of 33 this kind of code.


What I actually did was 32 to use a polygon-intersection algorithm 31 that is part of the Java2D libraries. You 30 can possibly find something similar in MS's 29 own C# libraries to use.

There are other 28 options out there as well; look for "polygon 27 clipper" or "polygon clipping", since 26 the same basic algorithms that handle polygon 25 intersection also tend to be usable for 24 the general clipping cases.

Once you actually 23 have a polygon clipping library, you just 22 need to subtract polygon B from polygon 21 A to get your first piece of output, and 20 intersect polygons A and B to get your second 19 piece of output.

How to roll your own, for the hopelessly masochistic

When I was considering rolling 18 my own, I found the Weiler-Atherton algorithm 17 to have the most potential for general polygon-cutting. I 16 used the following as a reference:



The details, as 15 they say, are too dense to include here, but 14 I have no doubt that you'll be able to find 13 references on Weiler-Atherton for years 12 to come. Essentially, you split all the 11 points into those that are entering the 10 final polygon or exiting the final polygon, then 9 you form a graph out of all the points, and 8 then walk the graph in the appropriate directions 7 in order to extract all the polygon pieces 6 you want. By changing the way you define 5 and treat the "entering" and "exiting" polygons, you 4 can achieve several possible polygon intersections 3 (AND, OR, XOR, etc.).

It's actually fairly 2 implementable, but like with any computational 1 geometry code, the devil is in the degeneracies.

Score: 3

You may also want to have a look at the 2 NetTopologySuite or even try importing it into Sql server 1 2008 & it's spatial tools.

Score: 3

Clipper is an open source freeware polygon clipping library 9 (written in Delphi and C++) that does exactly 8 what you're asking - http://sourceforge.net/projects/polyclipping/

In my testing, Clipper 7 is both significantly faster and far less 6 prone to error than GPC (see more detailed 5 comparisons here - http://www.angusj.com/delphi/clipper.php#features). Also, while there's 4 source code for both Delphi and C++, the 3 Clipper library also includes a compiled 2 DLL to make it very easy to use the clipping 1 functions in other (Windows) languages too.

Score: 2

If you dare to take a look to other people's 2 GPL C++ code, you can see how do they do 1 it in Inkscape:

http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (line 126)

Score: 2

A polygon is fully described by an ordered 25 list of points (P1, P2, ..., Pn). The edges 24 are (P1 - P2), (P2 - P3), ..., (Pn - P1). If 23 you have two polygons A and B which overlaps, there 22 will be a point An (from the list on points 21 describing polygon A) which lies within 20 the area surrounded by polygon B or vice 19 versa (a point of B lies in A). If no such 18 point is found, then the polygons does not 17 overlap. If such a point is found (i.e. Ai) check 16 the adjacent points of the polygon A(i-1) and 15 A(i+1). Repeat until you find a point outside 14 the area or all points are checked (then 13 the first polygon lies completly within 12 the second polygon). If you found a point 11 outside then you can calculate the crossing 10 point. Find the corresponding edge of polygon 9 B and follow it with resersed roles = now 8 check if the points of polygon B lie within 7 polygon A. This way you can build a list 6 of points which describe the overlapping 5 polygon. If needed you should check if the 4 polygons are identical, (P1, P2, P3) === (P2, P3, P1).

This 3 is just an idea and there maybe better ways. If 2 you find a working and tested solution I 1 would recommend that you use it...


Score: 2

Try to use GIS tools for that, such as ArcObjects, TopologySuite, GEOS, OGR, etc. I'm 3 not sure if all of these distributions are 2 availuable to .net, but they all do the 1 same.

Score: 2

This academic paper explains how to do this.


More Related questions