CODEWITHSUNDEEP
algorithmgeolocation
Igor Tyulkanov
Igor Tyulkanov

Reputation: 5548

Algorithm to find min area covered X percents of geopoints

There is a convex geo polygon consisting of 200 vertexes (lat, lng). Lets call it M. There is a set of geo points inside it (about 15 000 points). P = {1 ... 15 000}. Also there is another convex geo polygon inside the first one (M) and consisting of 50 vertexes. Lets call it S. Polygon S contains 43 percent of points of P. I need some algorithm to increase the area of S (by moving the points of original polygon S) to get minimum area that will contain 55 percent of points of P. Is it possible?

Upvotes: 1

Views: 49

Answers (1)

MrSmith42
MrSmith42

Reputation: 10151

It is not always possible if the modified S (lets call it S') needs to be 100% within M.

Here the example:

Let M be kind of a circle where 43% of the points are near the center and all 57% other points on the rim of the circle. Let S be a triangle with the corners on the rim of the circle.

There is no way to get more of the points on the rim of the circle within the triangle with just moving the corners of the triangle within M because only maximal 3 of the points on the rim of the circle can be part of the triangle. So you cannot achieve the 55% in S' as long as it has to remain a triangle and the corners need to be inside M.

Upvotes: 1

Related Questions