江湖救急，如何判断这个点在图像中的位置

mxlzhenzhu

问题是这样的，有一个平面图形【可以看成是某岛国的国土】，实际上对它的已知信息只知道它是由许多点构成【这些点构成了绿色部分】，而且这些点的分布规律几乎是均匀分布的，但是坐标并没有其他规律可循，另外这些点“离散这个图形”足够精细；现在要判断，任意给定一个点的坐标【可以看成是经度和纬度】，问是否这个点落在这个几何图形内部？

如下图所示，白色部分全部都是“不属于这个图形区域”，而绿色部分则“属于这个图形区域”，求算法。

ChaChing

help inpolygon ???

mxlzhenzhu

ChaChing 发表于 2013-7-30 10:23
help inpolygon ???

感谢ChaChing，我爱死你了；不过，现在的问题看来应该是，给定一系列的点，如何求取最外边的多边形区域呢？难道要搜索C(n，2)次，可是中间的那部分多边形又怎么也能识别出来呢？

看来这个问题算是要解决了。
http://wenku.baidu.com/view/288d3748852458fb770b565a.html
http://www.idlcoyote.com/math_tips/convexhull.html
http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
http://www.ams.sunysb.edu/~jsbm/courses/345/melkman.pdf

At last:
http://moais.imag.fr.sixxs.org/membres/denis.trystram/SupportsDeCours/convexHull.pdf