多边形包围一组点 [英] Polygon enclosing a set of points

问题描述

我点（2D：由x和y的定义）的集合S，我想求P，最小的（意思是：用最小点数）多边形封闭组的所有点，P是的S有序的子集。

I have a set S of points (2D : defined by x and y) and I want to find P, the smallest (meaning : with the smallest number of points) polygon enclosing all the points of the set, P being an ordered subset of S.

是否有任何已知的算法来计算呢？ （我在这个领域缺少文化是惊人的...）

Are there any known algorithms to compute this? (my lack of culture in this domain is astonishing...)

感谢您的帮助

推荐答案

有很多算法针对此问题。它被称为最小边框。你会发现解决方案过于搜索凸包，特别的here 。

There are many algorithms for this problem. It is called "minimum bounding box". You will find solutions too searching for "convex hull", especially here.

的一种方式是找到最左边的点，然后重复以搜索一个点，其它所有点到线P（N-1）P（N）的权利。

One way is to find the leftmost point and then repeat to search for a point where all other points are to the right of the line p(n-1)p(n).

这篇关于多边形包围一组点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！