Find the largest area polygon built from a given list of vertices

This is code that gets a list of polygon vertices, non-ordered, and finds the order in which they should be arranged in order to create the polygon with the largest area.

There are two key elements in the approach:

-
Testing the area of the polygon is done by Monte Carlo calculation. Random points are dropped on the plane and we count the fraction that is inside the polygon. Note that the polygon is not necessarily concave.

-
Since going over all permutation of the vertices is too extensive, we employ a statistical trick. We have a greedy algorithm to unwind a polygon by identified pair of edges that cut each other and "untangle" them, then repeating until the polygon is completely untangled. Sometime untangling fails, but most of the time it's OK. Then we repeat shuffle-untangle cycle a low number of times, testing for the area, until we don't get a better candidate.

The code also plays a little with data structures, and have some plotting functions, etc.

I'm not sure I am too happy with the solution since the Monte Carlo findarea is slow and inaccurate. Also, the unwindpolygon untangling is not always successful and needs a bailout to break when no solution is found, which means that some tests are wasted. For large number of vertices it gets really slow.

```
import numpy as np
import matplotlib.pyplot as plt
import random
import copy

class point:
"""A point in 2d"""

def __init__(self, px, py):
self.x = float(px)
self.y = float(py)
self.type = "point"

def __repr__(self):
return "point(" + str(self.x) + ", " + str(self.y) + ")"

def rotate(self, theta):
"""Rotate the point around origin by angle theta"""
rotmat = np.array([[np.cos(theta), np.sin(theta)],
[-np.sin(theta), np.cos(theta)]])
self.x, self.y = np.matmul(rotmat, [self.x, self.y])

def plotpoints(points):
"""plots points"""
for k in range(len(points)):
plt.plot(points[k].x, point

Your algorithm seems to rely on randomness more than necessary.

One intuitively obvious conclusion is that the polygon with the largest area should be a simple polygon (i.e., no self-intersecting edges). You have implemented that, which is a good start.

It it easy to calculate the area of any simple polygon exactly using the shoelace formula. The algorithm is \$O(\left|V\right|)\$. No Monte-Carlo simulation is needed.

The convex hull of the points should provide a skeleton of the solution. The question is, what to do with the interior points? Intuitively, I think that the solution should involve computing the convex hull of the remaining interior points, then interspersing the traversal of the outer polygon with the traversal of the inner polygon in such a way that the area is maximized. Then, recurse as necessary if the inner polygon also has interior points.

StackExchange Code Review Q#133958, answer score: 4