Maximum Area of a Polygon with Vertices of a Polygon

3

1

Rules

Given a list of integer coordinates, l, with a length of at least 4, and an integer n such that n is smaller than the length of l (but at least 3), return the largest area of an n-sided polygon satisfies:

  • is simple (not self-intersecting).
  • has all the coordinates of its n vertices in the list l.
  • has no three consecutive collinear vertices.

Note that the polygon given in the input should comply to the three points above as well.

Test Cases

Here are a few test cases:

[(0,0), (0,-1), (-1,-1), (-1,0)], 3 -> 0.5
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 3 -> 3
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 5 -> 5.5
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 6 -> 6

You can try any test cases you like here.

Make your code as short as possible.

0WJYxW9FMN

Posted 2017-12-29T20:11:58.163

Reputation: 2 663

Question was closed 2018-01-12T00:31:08.707

This is a good challenge, but I would probably include some test cases in the body. Also, may we assume that no 3 points are collinear? – Giuseppe – 2017-12-29T20:31:27.553

@Giuseppe What test cases would be useful? – 0WJYxW9FMN – 2017-12-29T20:34:28.043

I'd just pick a few at random, including one where n is small but |l| is much larger. The link to generate more test cases is useful for getting more should we need them. I don't have any good insight on this problem, other than that the likely algorithms are going to be the brute force O(|l|^n) – Giuseppe – 2017-12-29T20:37:43.843

1When you say the input coordinates are in anticlockwise order, does this imply that they are vertices of a convex polygon, i.e. all of them lie on the border of their convex hull? – xnor – 2017-12-29T21:02:00.490

@xnor Not necessarily convex (although I don't know much about the rigorous definitions; I just thought follow the vertices in anticlockwise order). Currently, I don't see any reason to specify convex, but, if it has advantages or makes the challenge less confusing, I'll add it. – 0WJYxW9FMN – 2017-12-29T21:05:02.467

Are you sure you implemented the shoelace formula correctly? The first example is a square with area 1, how could an inscribed triangle have an area of 1.5? – Bolce Bussiere – 2018-01-03T22:39:47.687

Found the problem: line 5 should be a-=. – Bolce Bussiere – 2018-01-03T22:54:21.863

@BolceBussiere Thanks; I'm an idiot. Fixed. – 0WJYxW9FMN – 2018-01-05T22:54:06.447

1Your test program only considers polygons made from sequences of vertices in the given order, even if another order may yield a larger area. Also, it fails to exclude self-intersecting polygons, for which the shoelace formula may over- or under-count some regions depending on the winding number around them (how should self-intersecting polygons be handled?). – Anders Kaseorg – 2018-01-06T00:02:52.587

I think replacing combination with permutation will fix the issue. Also I think (but can't prove) that, using the formula in the example code, the area of any permutation of the points is no larger than the area of the polygon formed by the convex hull of those points. – user202729 – 2018-01-06T10:37:14.270

@AndersKaseorg I think the polygons the algorithm considers are the largest ones by area given the subset of points. There's no point considering extra cases that you know will have less area if you're trying to find the max area. – nog642 – 2018-01-11T10:28:09.843

@user202729 No; for example, the formula finds a larger area for the self-intersecting regular star polygon {7/2} (7 sin(4π/7)/2 ≈ 3.41225) than for its convex hull (7 sin(2π/7)/2 ≈ 2.73641).

– Anders Kaseorg – 2018-01-11T22:34:42.220

@nog642 That very much depends on the order in which the points were passed in, which was previously ill-defined (it’s not clear and certainly not unique what “anticlockwise order” means for sets other than the vertices of a convex polygon), and in the current revision is no longer defined at all. If the given test code works under some assumption about this order, it’s not clear what that assumption is. – Anders Kaseorg – 2018-01-11T22:38:22.420

@J843136028 I edited the question to address AndersKaseorg's concerns. You can roll back and edit the question if that is not what you want. – user202729 – 2018-01-12T08:36:05.483

@user202729 The test case generator is now fixed (though the test cases given in the problem were right). – 0WJYxW9FMN – 2018-01-12T17:08:23.177

@AndersKaseorg Is it clear enough now? – user202729 – 2018-01-13T02:08:37.697

The test case generator remains inconsistent with the specification because it doesn’t check for self-intersections or for three consecutive collinear vertices. (I think the requirement to exclude polygons with three consecutive collinear vertices is arbitrary; that part of the inconsistency is perhaps best resolved by removing that requirement, or by guaranteeing that no three input points are collinear. The self-intersections issue is fundamental though, as explained above.) – Anders Kaseorg – 2018-01-16T09:22:10.803

@AndersKaseorg Changed. – 0WJYxW9FMN – 2018-01-17T17:15:57.867

@J843136028 That doesn’t address the problem. You can still form a self-intersecting polygon from a subset of the vertices of a non-self-intersecting polygon (or similarly with three consecutive collinear vertices). – Anders Kaseorg – 2018-01-17T20:34:53.170

Example polygon to demonstrate that. This time I'm not sure what you want to do so I won't edit the challenge. – user202729 – 2018-01-18T13:41:43.863

@AndersKaseorg Surely, given certain vertices, the largest possible area with these vertices is a simple polygon, though. For example, if a square is ABCD, ABCD would have a bigger area than ACBD. – 0WJYxW9FMN – 2018-01-18T17:45:26.010

@user202729 "Note that the polygon given in the input should comply to the three points above as well." This means no three points are collinear. – 0WJYxW9FMN – 2018-01-18T17:46:34.227

@J843136028 “Surely…” No, I have already pointed out a counterexample. “This means no three points are collinear.” No, it means no consecutive three points are collinear. Non-consecutive vertices of the original polygon may become consecutive vertices of the small one, like I already said and like user202729 just demonstrated.

– Anders Kaseorg – 2018-01-18T19:06:03.837

Answers

0

Python 2, 172 bytes

-1 byte thanks to J843136028

bug fix thanks to Jonathan Frech

from itertools import*
def f(l,n,L=()):
 for p in combinations(l,n):
  r=0;j=-1
  for i in range(n):r+=(p[j][0]+p[i][0])*(p[j][1]-p[i][1]);j=i
  L+=abs(r/2.),
 print max(L)

Try it online!

nog642

Posted 2017-12-29T20:11:58.163

Reputation: 151

On the fourth line, you could do r,j=0,-1. On the sixth line, you could do L+=abs(r/2.),. – 0WJYxW9FMN – 2018-01-11T17:17:57.703

@J843136028 r,j=0,-1 doesn't save any bytes compared to r=0;j=-1, but thanks for your other suggestion. – nog642 – 2018-01-11T20:13:44.590

Your test cases only work because they are in increasing order (TIO).

– Jonathan Frech – 2018-01-12T17:13:42.850

A proposed fix would be not to use a mutable object for your L default. Using a tuple instead of a list makes the function truly reusable (TIO).

– Jonathan Frech – 2018-01-12T17:16:44.133

@JonathanFrech Right, I forgot python functions save mutable default arguments between calls. Thanks. – nog642 – 2018-01-12T17:47:40.913

134 bytes. – Jonathan Frech – 2018-01-12T18:01:14.723

Asked: 2017-12-29T20:11:58.163

Viewed: 282 times

Active: 2018-01-17T17:15:50.797