14 replies to this topic

[ref_cracker]

I want to clip polygon A against polygon B.
Both polygons are allowed to be concave, but don't have holes or self intersections.

I'm looking for code to do this. Has anyone here ever implemented such a function?

I've found a few online sources but they are too general purpose and seem to be overly complex, accounting for holes and self intersection etc etc.

I've looked for a "WEILER ATHERTON" source out there and didn't come up with anything too promising ... again overly complex.

This would seem to me to be a fairly common routine, but finding good source code out there has alluded me!

If anyone has a good tested routine they would like to share please pass it on!

Thanks!

EDIT: BTW I'm wanting to do this just in 2D!

[rouncer]

true intersection of two 3d objects is not an easy thing to do, its like boolean objects, you need plane intersections or triangle intersections to do it. theres no real quick way to do it thats easy, if you want to do it fast it probably takes binary space partitioning.
i could write it, it probably would go okish, if it doesnt have concave parts then it probably could be written faster...
if you want to hire me for 100 bucks ill write it for ya ;)
if you want the objects to bounce and rotate off each other or cut polygon a's shape out of polygon b's thatll cost ya extra... like an
arm and a leg and poor usage rights. hehehe just kidding.

[.oisyn]

Please reread his last line

[spacerat]

There should be a couple of free libraries available like this one
http://www.cs.man.ac.../alan/software/

[Spudman]

If your polygons are on the same plane and asssuming they have passed a trivial rejection test on some simple bounding shape, then split each polygon
into a series of convex triangles, and compare the elements of one set against those of the other. Triangle against triangle intersection is well-documented, if somewhat laborious.

[Nils Pipenbrinck]

Hm.

There simply don't exist a cheap solution, and having a algorithm that can only handle convex polygons without holes won't help you either since the clipped output can contain holes and isles. The algorithms require some kind of divide and conquer method, and will at one stage or another deal with holes.



This is the simplest implementation I have seen. It even comes with source, but I must admit, I've never tried it on my own.

http://davis.wpi.edu...urses/clipping/


Other than that you can use gpc for the task (already pointed out by a forumite). Gpc wasn't for me though. It was not fast enough and I had problems with it's license.

I ended up taking the gl-tesselator from the sgi opengl reference implementation. That's less restricted from a licence point of view (even less restricted than lgpl). The downside is that the code need a day or two of work to run without opengl.

For those who know the gl-tesselator and wonder how it can be used to do polygon-clipping: the sgi implementation has undocumented hooks to do that. Once you dive into the code you'll find them.

[.oisyn]

Nils Pipenbrinck said:

Hm.

There simply don't exist a cheap solution, and having a algorithm that can only handle convex polygons without holes won't help you either since the clipped output can contain holes and isles.

Not true, the intersection (boolean AND) of two convex objects is always convex. And the intersection of two concave objects without holes will also not contain holes (but can contain isles)

[Nils Pipenbrinck]

.oisyn said:

Not true, the intersection (boolean AND) of two convex objects is always convex. And the intersection of two concave objects without holes will also not contain holes (but can contain isles)

Hm. I agree for the AND case, but the intersection can contain isles and holes. Just intersect a triangle with another triangle. One of them should be contained in the other. This will "stencil" out the inner triangle of the outer leaving a hole.

I've done quite a lot of work on such algorithms (tesselation and 2d csg), and they are not simple. Let alone write one that is numerical stable with real world data.

These kind of algorithms are incredibly hard to write. You have to deal with lots of pesky details such as double vertices, back and forth edges, double and tripple intersections (three lines cross at exactly one point) and other corner cases. There are some cases that don't have a logical solution at all, and all you can do is to write an algorithm that at least outputs usefull data.

Once that's done the real numerical pain starts: If you ever start to create new vertices by intersection the slope of the lines you've just splitted slightly changes due to roundoff errors and the finite precision of floats. This can (and in practice will) create new intersections that wheren't there before. You need either to do brute force intersection or re-test all affected geometry). If your code is not prepared for that, you can be sure it will halt at a later stage (during extracting of resulting outlines for example).

Simple hacks won't work but will just open a can of worms. The more you hack, the more worms/bugs you will get.

And that still does not solve the problem of intersections that have no definate solution.

To write a polygon clipping algorithm that does not suck is not as simple as to follow the textbook algorithm: e.g. outline traversal, intersection-detection, adding new vertices and then a final inside/outside extraction. That might work for test data and is fine for a university course, but in practice it will break.

As an example how hard it can be: how is the intersection of these two little quads (in CW-order)

A: <0,0>, <10,0>, <10,10>, <0,10>
B: <0,3>, <6,3>, <6,7>, <0,7>

[Reedbeta]

Nils Pipenbrinck said:

Hm. I agree for the AND case, but the intersection can contain isles and holes. Just intersect a triangle with another triangle. One of them should be contained in the other. This will "stencil" out the inner triangle of the outer leaving a hole.

That's difference, not intersection...the intersection of those two triangles would just be the smaller.

[Nils Pipenbrinck]

Reedbeta said:

That's difference, not intersection...the intersection of those two triangles would just be the smaller.

*think, think*

You're right.. I always classify by winding count. That works a bit different. (e.g. intersection would be ODD, union becomes NONZERO ect..)

[jhagmar]

I stumbled across this thread since I'm looking for a way to compute unions of polygons. I started looking into gpc, but as Nils pointed out, the license makes it difficult to use the code for commercial projects.

It was interesting to hear that you, Nils, considered gpc to be slow, and that you preferred using tesselation. Could you give me some more pointers in that direction?

[ljubang]

here some example code for u?
this code using Canvas class here
http://www.ecs.umass...Ece660Chap3.pdf

source code :
http://www.mediafire.com/?fwc9bn1nxpp

[UnrealSolo]

I can share with you my beginners efforts with 3d polygon - polygon intersection, wich may give you an idea, I take each wire of each polygon and find the point of intersection in the other polygon, thus giving me 2 points wich form a line. I may get upto 4 points due to rounding errors.

as yours are in a single plane, then you could test each wire in one poly with each wire in the other poly, and determine if it intersects or if its completly inside. then you just join up the dots or lines ... my 3d code itself isnt realy of much help ... however I found it a lot speedier to store results of calculations wich would otherwise be repeated,

ie. vector of each line, length, and normal or cross product.

[angusj]

Nils Pipenbrinck said:

These kind of algorithms are incredibly hard to write. You have to deal with lots of pesky details such as double vertices, back and forth edges, double and triple intersections (three lines cross at exactly one point) and other corner cases.

Yes, that pretty much sums it up. Dealing with complex intersections (more than 2 edges intersecting at the same point) is probably the hardest thing to get right.

Anyhow, in case some are still looking for a solution to this problem, I've recently written a freeware polygon clipping library -Clipper- that can be downloaded from SourceForge - http://sourceforge.n...s/polyclipping/

Features include:
* 2D polygon clipping - intersection, union, difference & xor
* Processes all kinds of polygons including complex polygons
* Processes multiple subject and clipping polygons
* Input polygons can use either (or both) the EvenOdd or NonZero filling rule
* Significantly faster & more robust than popular commercial alternatives
* Library written in both Delphi and C++

[adimarten23]

I could possibly be persuaded to make another where users could load their own polygon data from text files, but so far I'm not convinced that there would be enough interest in this additional demo to justify the effort in making it.