Some good reading on polygon algorithms

Question

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

Have you looked at http://stackoverflow.com/questions/1526352/how-to-intersect-two-polygons ? — Paul, Mar 07 '12 at 19:16

Paul · Answer 1 · 2012-03-09T03:59:29.663

4

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.

edited Mar 09 '12 at 03:59

answered Mar 07 '12 at 19:22

Paul

12,045
7
56
129

score 3 · Answer 2 · answered Mar 07 '12 at 21:09

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

score 2 · Answer 3 · answered Mar 07 '12 at 23:48

2

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.

answered Mar 07 '12 at 23:48

lhf

966
1
7
12

score 2 · Answer 4 · answered Mar 17 '12 at 13:56

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.

score 2 · Answer 5 · answered Jun 05 '18 at 03:58

This one is quite old and not well known, but it is a good one:

M. V. Leonov and A. G. Nikitin. An Efficient Algorithm for a Closed Set of Boolean Operations on Polygonal Regions in the Plane (draft English translation). A. P. Ershov Institute of Informatics Systems, Preprint 46, 1997

Some good reading on polygon algorithms

5 Answers5