连接点和计算区域

[poster]

多数民众赞成在我的第一篇文章，所以请客气。

我有一个3〜10座标的矩阵，我想将这些点连接成最大尺寸的多边形。

我尝试了fill（）[1]来生成图，但是如何计算该图的面积呢？有没有一种方法可以将绘图转换回矩阵？

你会推荐我什么？

先感谢您！

[1] x1 = [0.0，0.5，0.5];y1 = [0.5，0.5，1.0];填充（x1，y1，'r'）;

[更新]

感谢您的回答MatlabDoug，但我想我提出的问题不够清楚。我想将所有这些点连接起来以成为具有最大尺寸的多边形。

有什么新主意吗？


回答：
我赞同groovingandi关于尝试所有多边形的建议。您只需要确保检查多边形的有效性即可（无自相交等）。

现在，如果您想处理很多点，正如MatlabDoug指出的那样，凸包是一个不错的起点。请注意，凸包给出的多边形面积最大。当然，问题在于船体内部可能存在一些不属于多边形的点。我提出以下贪婪算法，但不确定是否可以保证最大面积多边形。

基本思想是从凸包作为候选最终多边形开始，并雕刻出与未使用的点对应的三角形，直到所有点都属于最终多边形。在每个阶段，都将删除最小的三角形。

Given: Points P = {p1, ... pN}, convex hull H = {h1, ..., hM} where each h is a point that lies on the convex hull. H is a subset of P, and it is also ordered such that adjacent points in the list of H are edges of the convex hull, and the first and last points form an edge. Let Q = H while(Q.size < P.size) % For each point, compute minimum area triangle T = empty heap of triangles with value of their area For each P not in Q For each edge E of Q If triangle formed by P and E does not contain any other point Add triangle(P,E) with value area(triangle(P,E)) % Modify the current polygon Q to carve out the triangle Let t=(P,E) be the element of T with minimum area Find the ordered pair of points that form the edge E within Q (denote them Pa and Pb) Replace the pair (Pa,Pb) with (Pa,E,Pb) 现在，在实践中，您不需要为T堆，只需将数据追加到四个列表即可：一个用于P，一个用于Pa，一个用于Pb，以及一个用于区域。要测试某个点是否在三角形内，您只需要相对于形成三角形边的线测试每个点，并且只需要测试不在Q中的点即可。最后，要计算最终多边形的面积，您可以对其进行三角剖分（例如使用delaunay函数，并对三角剖分中每个三角形的面积求和），或者可以找到凸包的面积，并在将其切出时减去三角形的面积。

再说一次，我不知道这种贪婪算法是否可以保证找到最大面积的多边形，但是我认为它应该在大多数时间都可以工作，但是仍然很有趣。



更多&回答...