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.

$\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....

$\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.

$\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.

$\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.