What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ convex or non-convex polygons? $\endgroup$– Aron AhmadiaCommented Mar 7, 2012 at 17:32
-
1$\begingroup$ Have you looked at stackoverflow.com/questions/1526352/… ? $\endgroup$– PaulCommented Mar 7, 2012 at 19:16
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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....
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
This one is quite old and not well known, but it is a good one:
