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

问题描述

我有一组点 S(2D:由 x 和 y 定义)，我想找到 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...)

感谢您的帮助

推荐答案

这个问题有很多算法.它被称为最小边界框".您也会在搜索convex hull"时找到解决方案，尤其是 这里.

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屋！