连接点和计算区域 [英] Connect points and compute area

问题描述

那是我的第一篇文章，请保持友善.

thats my first post, so please be kind.

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

I have a matrix with 3~10 coordinates and I want to connect these points to become a polygone with maximum size.

我尝试了fill()[1]来生成图，但是如何计算该图的面积呢?有没有办法将图转换回矩阵?

I tried fill() [1] to generate a plot but how do I calculate the area of this plot? Is there a way of converting the plot back to an matrix?

你会推荐我什么?

提前谢谢！

[1]

x1 = [ 0.0, 0.5, 0.5 ];
y1 = [ 0.5, 0.5, 1.0 ];
fill ( x1, y1, 'r' );

[更新]

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

Thank you for your answer MatlabDoug, but I think I did not formulate my question clear enough. I want to connect all of these points to become a polygone with maximum size.

有什么新主意吗?

推荐答案

我第二次尝试尝试所有多边形.您只需要确保检查多边形的有效性即可(无自相交等).

I second groovingandi's suggestion of trying all polygons; you just have to be sure to check the validity of the polygon (no self-intersections, etc).

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

Now, if you want to work with lots of points... As MatlabDoug pointed out, the convex hull is a good place to start. Notice that the convex hull gives a polygon whose area is the maximum possible. The problem, of course, is that there could be points in the interior of the hull that are not part of the polygon. I propose the following greedy algorithm, but I am not sure if it guarantees THE maximum area polygon.

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

The basic idea is to start with the convex hull as a candidate final polygon, and carve out triangles corresponding to the unused points until all the points belong to the final polygon. At each stage, the smallest possible triangle is removed.

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函数，对三角剖分中的每个三角形的面积求和)，或者可以找到凸包的面积，并在将其切出时减去三角形的面积

Now, in practice you don't need a heap for T, just append the data to four lists: one for P, one for Pa, one for Pb, and one for the area. To test if a point lies within a triangle, you only need to test each point against the lines forming the sides of the triangle, and you only need to test points not already in Q. Finally, to compute the area of the final polygon, you can triangulate it (like with the delaunay function, and sum up the areas of each triangle in the triangulation), or you can find the area of the convex hull, and subtract out the areas of the triangles as you carve them out.

同样，我不知道这种贪婪算法是否可以保证找到最大面积的多边形，但是我认为它应该在大多数时候都可以正常工作，但是仍然很有趣.

Again, I don't know if this greedy algorithm is guaranteed to find the maximum area polygon, but I think it should work most of the time, and is interesting nonetheless.

这篇关于连接点和计算区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！