Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Fun with convex polygons (wildbunny.co.uk)
49 points by MetallicCloud on March 29, 2012 | hide | past | favorite | 7 comments


All of these sorts of things start making a lot more obvious intuitive sense when you learn some basic “geometric algebra”. See e.g. http://news.ycombinator.com/item?id=3284160


If the polygon is self-intersecting, the area around which the algorithm traverses the edges clockwise will be subtracted from the rest of the area traversed counter-clockwise. While interesting, I have yet to find this fact actually useful.

Edit: for more fun with polygons, check out Pick's theorem [1].

Since I'm guessing that pretty much everyone on this site has a copy of CLRS, the Selected Topics chapter on Computational Geometry has a good overview of cross product tricks. The convex hull algorithms are also interesting, useful, and very simple to learn.

If you're finished with that and are actually still interested, look at the Rotating Calipers method. It's a way of addressing all antipodal pairs of a given polygon, which serves as the basis for a whole whack of algorithms. Example - finding the narrowest rotation of a polygon. Some of you may recognize this as the solution to the last (and easiest) problem at the 2011 ICPC world finals [2].

[1] http://en.wikipedia.org/wiki/Pick%27s_theorem

[2] (PDF) https://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/20...


The area method works with non-convex polyons, too. Not sure why he thinks it won't. See http://en.m.wikipedia.org/wiki/Shoelace_formula.


Is this similar to the method of summing the area of trapezoids defined by the points and an axis?


always knew this as "surveyor's formula"


Computational geometry algorithms are often fairly easy to explain, but implementing them robustly in quite tricky. Not only are there many edge cases, you also need to do your calculations with arbitrary precision (at least sometimes) [1]. You're generally much better off to use some library like CGAL [2] instead of rolling your own.

[1] http://www.mpi-inf.mpg.de/~mehlhorn/ftp/classroomExamplesNon...

[2] http://www.cgal.org/


Not to mention the somewhat less license-encumbered Boost libraries Geometry (http://www.boost.org/doc/libs/1_49_0/libs/geometry/doc/html/...) and Polygon (http://www.boost.org/doc/libs/1_49_0/libs/polygon/doc/index....)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: