一种求最小覆盖率X%地面点的算法

Question

有一个由200个顶点组成的凸几何多边形( lng)。我们称它为M。它里面有一组地理点(大约15000个点)。P={1...15000}。此外，在第一个凸几何多边形(M)中还有另一个凸几何多边形，它由50个顶点组成。让我们称之为S。多边形S包含P的43 %的点。我需要一些算法来增加S的面积(通过移动原始多边形S的点)来获得包含P的55 %的点的最小面积。

Answer 1

如果修改后的S(让我们称之为S')在M内需要100%，这并不总是可能的。

下面是示例：

假设M是一种圆，其中43%的点在圆心附近，所有57%的其他点都在圆的边缘。设S是一个三角形，其边角在圆的边上。

只需在M内移动三角形的角，就无法获得更多的三角形内圆边缘上的点，因为圆边缘上的最多3个点可以是三角形的一部分。所以你不能在S‘中达到55%，只要它必须保持一个三角形，并且角需要在M内。