Computational Geometry

Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars

Mentioned 3

This introduction to computational geometry focuses on algorithms. Motivation is provided from the application areas as all techniques are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement.

More on

Mentioned in questions and answers.

Im trying to triangulate a polygon for use in a 3d model. When i try using the ear method on a polygon with points as dotted below, i get triangles where the red lines are. Since there are no other points inside these triangles this is probably correct. But i want it to triangulate the area inside the black lines only. Anyone know of any algorithms that will do this?

enter image description here

The usual approach would be to split your simple polygon into monotone polygon using trapezoid decomposition and then triangulate the monotone polygons. The first part can be achieved with a sweep line algorithm. And speed-ups are possible with the right data-structure (e.g. doubly connected edge list). The best description of this, that I know, can be found in Computational Geometry. This and this also seem helpful.

I would like to know in which order I should learn different areas of maths so I can have a robust overview of all the theory in case I need something for a computer programming problem.

So I've created this mind map

enter image description here

I do not intend to know all those small details about how to do a certain thing (e.g. "gauss-jordan reduction"), I would rather look over an example, but then do it with math software like sage-maths or mathematica.

I would like to know, for instance, how to get to a taylor series, given the analytical function (I know it already, I am merely illustrating the kind of knowledge depth I expect).

So all I all, I want to be able to read academic articles about maths which have applicability in computer science / programming, and actually understand something from those articles, so I can use that knowledge in solving actual programming problems.

The open question is:

  1. (a) In what order do you suggest to learn about these areas, on what areas should I insiste more?

    (b) Do you see any missing areas in the mind map?

There is a good book, that I think would help you to get more out of computer science research papers and dissertations. It's called "Concrete Mathematics: A foundation for Computer Science", and it's available on Amazon:

I think this would help because it will all be relevant, and its consolidated which will help expedite the learning process.

Even if you don't have any money, just Google it and take a look at the index to get an idea of what areas you might want to learn.

And here's one more interesting book.

How to generate buffer around lines or any type of geometric shapes?
Not interested in available packages such as Shapely etc but wish to implement. enter image description here

Mathematically, this operation is a Minkowski sum. You should find a reference and some pseudo-code in a good book on compuational geometry. Try Computational Geometry in C by O'Rourke, or Computational Geometry: Algorithms and Applications by Berg et al.