请问有人熟悉对地理数据中区域边界路径的压缩算法吗？具体来说，就是一组
经纬度的点组成的一个闭合路径，适当的删减一些节点，同时保持该路径的形状
基本不变的算法。也可以理解为对多边形的顶点进行删减的算法。

如果与相邻两点连线的夹角大于某个临界值就删掉？

在 06-7-6，Xie Yanbo<xieyanbo at gmail.com> 写道：
> 请问有人熟悉对地理数据中区域边界路径的压缩算法吗？具体来说，就是一组
> 经纬度的点组成的一个闭合路径，适当的删减一些节点，同时保持该路径的形状
> 基本不变的算法。也可以理解为对多边形的顶点进行删减的算法。
>


-- 
Ocean
mail: chocean at gmail.com
homepage: www.oceanisland.com.cn

经网友 chbpku 提示，以"多边形简化"及"Polygon reduction"检索到很多信息，感兴趣
的朋友也可以一起来实践一下。

我没太看明白楼主的意思，不知道是否可简化为凹多边形转换为凸多边形？
如果是的话，有个算法，就是从每一点做一条直线，如果存在一条直线，让其他点都在直线的一侧，那就是凸多边形，否则是凹多边形，那么可以删除这个顶点，再把其他点连接起来，这样对每个点判断一下，就可以把多余的顶点去掉了。

在 06-7-6，Xie Yanbo<xieyanbo at gmail.com> 写道：
> 请问有人熟悉对地理数据中区域边界路径的压缩算法吗？具体来说，就是一组
> 经纬度的点组成的一个闭合路径，适当的删减一些节点，同时保持该路径的形状
> 基本不变的算法。也可以理解为对多边形的顶点进行删减的算法。
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>

On 7/8/06, WhiteFox <wyh817 at gmail.com> wrote:
>
> 我没太看明白楼主的意思，不知道是否可简化为凹多边形转换为凸多边形？


他要求的是允许损失信息的压缩，并不仅仅是删除多余顶点。

如果是的话，有个算法，就是从每一点做一条直线，如果存在一条直线，让其他点都在直线的一侧，那就是凸多边形，否则是凹多边形，那么可以删除这个顶点，再把其他点连接起来，这样对每个点判断一下，就可以把多余的顶点去掉了。


对于化简凹多边形的问题，你的算法时间复杂度太高了。
只要从任意顶点出发走一圈，一路上遇到凹角的时候就递归回溯，这样只要O(n)的时间复杂度。


在 06-7-6，Xie Yanbo<xieyanbo at gmail.com> 写道：
> > 请问有人熟悉对地理数据中区域边界路径的压缩算法吗？具体来说，就是一组
> > 经纬度的点组成的一个闭合路径，适当的删减一些节点，同时保持该路径的形状
> > 基本不变的算法。也可以理解为对多边形的顶点进行删减的算法。
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060708/5647a9ae/attachment.html

polygon reduction是处理3D模型的算法，最终还是自己设计了一个算法来实现2D 多边形
的缩减。算法说明及代码在这里：
http://xieyb.livejournal.com/12977.html