4 ms·

Fun with convex polygons

49 points by MetallicCloud 15y ago

shasta 15y ago
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 http://en.m.wikipedia.org/wiki/Shoelace_formula.
- tantalor 15y ago
  Is this similar to the method of summing the area of trapezoids defined by the points and an axis?
- leeoniya 15y ago
  always knew this as "surveyor's formula"
  - deleted 15y ago
    [deleted]
jacobolus 15y ago
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 http://news.ycombinator.com/item?id=3284160
ahelwer 15y ago
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 http://en.wikipedia.org/wiki/Pick%27s_theorem [2] (PDF) https://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/2011WorldFinalProblemSet.pdf https://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/20...
adrianN 15y ago
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/classroomExamplesNonrobustness.pdf http://www.mpi-inf.mpg.de/~mehlhorn/ftp/classroomExamplesNon... [2] http://www.cgal.org/ http://www.cgal.org/
- helmut_hed 15y ago
  Not to mention the somewhat less license-encumbered Boost libraries Geometry (http://www.boost.org/doc/libs/1_49_0/libs/geometry/doc/html/index.html 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.htm http://www.boost.org/doc/libs/1_49_0/libs/polygon/doc/index....)

49 points by MetallicCloud 15y ago

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 http://en.m.wikipedia.org/wiki/Shoelace_formula.

tantalor 15y ago
Is this similar to the method of summing the area of trapezoids defined by the points and an axis?
leeoniya 15y ago
always knew this as "surveyor's formula"
- deleted 15y ago
  [deleted]

jacobolus 15y ago

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 http://news.ycombinator.com/item?id=3284160

ahelwer 15y ago

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 http://en.wikipedia.org/wiki/Pick%27s_theorem [2] (PDF) https://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/2011WorldFinalProblemSet.pdf https://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/20...

adrianN 15y ago

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/classroomExamplesNonrobustness.pdf http://www.mpi-inf.mpg.de/~mehlhorn/ftp/classroomExamplesNon... [2] http://www.cgal.org/ http://www.cgal.org/

helmut_hed 15y ago
Not to mention the somewhat less license-encumbered Boost libraries Geometry (http://www.boost.org/doc/libs/1_49_0/libs/geometry/doc/html/index.html 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.htm http://www.boost.org/doc/libs/1_49_0/libs/polygon/doc/index....)