8
$\begingroup$

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?

$\endgroup$
4
$\begingroup$

I am a big fan of Joseph O'Rourke's works. I highly recommend his book Computational Geometry in C (2nd edition) because it has a particularly good balance of theory and implementation. Chapter 7 contains direct information pertaining to polygon intersection.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Paul's suggestion is great, I would just like to add two more:

"Geometric Tools for Computer Graphics", Schneider

"Computational Geometry" Mark deBerg et al.

On this note, my 2cents (coming from experience): if you are considering coding such algorithms, I advise you kindly to take a look at Boost::Geometry and/or CGAL libray first, there is no need (hopefully) to re-invent the wheel. If you are coding in C++, that is....

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

GPC, General Polygon Clipper is a good implementation for boolean operations on polygons based on Vatti's clipping algorithm. The page also contains links to other solutions.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

One strategy is to look for modern algorithms for related problems, like collision detection, etc. Often there are good strategies in slightly different application if you have a particular problem you're trying to solve.

As for implementation, you could check out the Boost Polygon Library.

A couple general books for Computational Geometry that are on my shelf are:

Computational Geometry: An Introduction by Franco Preparata and Michael Shamos is yet another good introductory book on computational geometry algorithms.

Computational Geometry: An Introduction Through Randomized Algorithms by Ketan Mulmuley is an excellently constructed book good algorithmic coverage of a wide variety of algorithms for geometric problems; all done through randomized methods.

| cite | improve this answer | |
$\endgroup$

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.