Given a convex polygon, add a point and recalculate the area

1
votes

Assume you have a convex polygon P(defined by an array of points p), and a set of points S(all of them outside of P), how do you choose a point s in S such that it increases the most the area of P. Example
I have a O(|P|) formula to calculate the area of the polygon, but I can't do this for every point in S given that 

3 ≤ |P|, |S| ≤ 10^5

The big dots are the points in S

The big dots are the points in S
No 3 points in P u S are collinear

2
algorithmoptimizationcomputational-geometryconvex-hull
For every s, you introduce edges between two vertices of P and s. You could use the triangles formed by these vertices to approximate the added area, which should do to filter out quite a few incorrect ones. Since the area of these triangles is always >= the actually added area, this approach won't give any false negatives. Calculating the actual area can be reduced to calculating the added area, which saves some time as well. – Paul
Search for dynamic convex hull. There is a DS which gives O(log(n)*log(n)) time for point insert/delete operation. – Ivan Gritsenko
@Paul how do I choose the 2 vertices you are talking about? – Moro Silverio
@MoroSilverio Id suggest ordering the points of the polygon according to their rotation around the center of the polygon and doing a binary search for the first two points a, b for which P u {s} becomes convex if we insert the edges a - s and s - b. Search time would be O(log |P|), assuming constant time random access to the sorted points. – Paul
I added a test result and a simpler approximation method. – m69 says ''Пу́тин хуйло́''

2 Answers

1
votes

Given fixed points p = (px, py), q = (qx, qy) and a variable point s = (sx, sy), the signed area of the triangle ∆pqs is

  |px py 1|
½ |qx qy 1|
  |sx sy 1| ,

which is a linear polynomial in sx, sy.

One approach is to compute cumulative sums of these polynomials where p, q are the edges in clockwise order. Use binary search to find the sublist of edges that remain in the convex hull with a given point s, add the polynomials, and evaluate for s.

0
votes

You have a method to calculate the exact area that is added by a point n (and David Eisenstat posted another), but their complexity depends on the number of sides of the polygon. Ideally you'd have a method that can quickly approximate the additional area, and you'd only have to run the exact method for a limited number of points.

As Paul pointed out in a comment, such an approximation should give a result that is consistently larger than the real value; this way, if the approximation tells you that a point adds less area than the current maximum (and with randomly ordered input this will be true for a large majority of points), you can discard it without needing the exact method.

The simplest method would be one where you only measure the distance from each point to one point in the polygon; this could be done e.g. like this:

Start by calculating the area of the polygon, and then find the smallest circle that contains the whole polygon, with center point c and radius r.

enter image description here

Then for each point n, calculate the distance d from n to c, and approximate the additional area as:

  • the triangle with area r × (d - r)
  • plus the rectangle with area 2 × r 2 (pre-calculated)
  • plus the half circle with area r × π (pre-calculated)
  • minus the area of the polygon (pre-calculated)

This area is indicated in blue on the image below, with the real additional area slightly darker and the excess area added by the approximation slightly lighter:

enter image description here

So for each point, you need to calculate a distance using √ ((xn - xc)2 + (yn - yc)2) and then multiply this distance by a constant and add a constant.

Of course, the precision of this approximation depends on how irregular the shape of the polygon is; if it does not resemble a circle at all, you may be better off creating a larger simple polygon (like a triangle or rectangle) that contains the original polygon, and use the precise method on the larger polygon as an approximation.

UPDATE

In a simple test where the polygon is a 1x1 square in the middle of a 100x100 square space, with 100,000 points randomly placed around it, the method described above reduces the number of calls to the precise measuring function from 100,000 to between 150 and 200, and between 10 and 20 of these calls result in a new maximum.

While writing the precise measuring function for the square I used in the test, I realised that using an axis-aligned rectangle instead of a circle around the polygon leads to a much simpler approximation method:

enter image description here

Create a rectangle around the polygon, with sides A and B and center point c, and calculate the areas of the rectangle and the polygon. Then, for each point n, the approximation of the additional area is the sum of:

  • the triangle with base A and height abs(yn - yc) - B/2
  • the triangle with base B and height abs(xn - xc) - A/2
  • the area of the rectangle minus the area of the polygon

(If the point is above, below or next to the rectangle, then one of the triangles has a height < 0, and only the other triangle is added.)

So the steps needed for the approximation are:

abs(xn - xc) × X + abs(yn - yc) × Y + Z

where X, Y and Z are constants, i.e. 2 subtractions, 2 additions, 2 multiplications and 2 absolute values. This is even simpler than the circle method, and a rectangle is also better suited for oblong polygons. The reduction in the number of calls to the precise measuring function should be similar to the test results mentioned above.