How to calculate a two-dimensional polygon?

Question

I have polygons that define the outline of counties in the UK. These forms are very detailed (from 10 to 20 thousand points each), which makes the associated calculations (point X in the polygon P?) Quite computationally expensive.

Thus, I would like to “select” my polygons to get a similar shape, but with fewer points. What are the different methods for doing this?

It would be trivial to take every point N (thus, sub-sampling by a factor of N ), but this seems too "rude". I would rather do some averaging of points or something like that. Any pointer?

Answer 1

Two spring solutions:

1), since the map of the UK is quite square, you can display a bitmap in the counties. Assign each specific color, and then visualize the borders with a black line 1 or 2 pixels thick. This means that you will need to perform an expensive internal / external calculation if the sample is at the border. The larger the bitmap, the less likely it will be.

2) simplify the contours of the county. You can use the Ramer-Douglas-Peucker recursive algorithm to recursively simplify boundaries. Just make sure you cache the results. You can also solve this problem not for all county borders, but only for common borders so that there are no gaps. It can be quite complicated.

Answer 2

Here you can find a project that specifically addresses your problems. Although it works mainly with the area "filled" with points, you can configure it to work with the definition of the type "perimeter" as yours.

It uses the k-nearest-neighbor approach to compute the region.

Samples:

Here you can request a copy of the document.

Apparently, they planned to offer an online service to request calculations, but I have not tested it, and it probably does not work.

NTN!

Answer 3

Polygon triangulation should help here. You will still have to check many polygons, but now they are triangles, so they are easier to check, and you can use some optimizations to determine only a small subset of the polygons to check for a given area or point.

It seems to you that you have all the algorithms necessary for polygons, and not just for triangles, you can also combine several triangles that are too small after triangulation or if the number of triangles becomes too high.