Computational Geometry - Part 1

I've spent some time studying an area called Computational Geometry, which according to Wikipedia is "a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry." Examples include: Are two lines intersecting? How can you triangulate random points? If you are interested in the area, the best book I found was Computational Geometry: Algorithms and Applications. The algorithms I've studied are:

Find the convex hull of random points. If you have some points and you want to find the smallest possible area that includes these points, then you need to find the convex hull of those points.



Triangulate polygons. If you have a convex polygon or a concave polygon, how can you triangulate them? 



Triangulate points. If you have random points, how can you triangulate those?



Delaunay triangulation. If you look at the images above, the triangles look kinda odd. To improve the triangulation you can use an algorithm called Delaunay triangulation.


Voronoi diagram. If you run a stores in different cities, then you can create a Voronoi diagram to find out where those customers live that live the closest to a specific store.


That's it for part 1. Next part will include boolean operations on polygons!

Comments