An optimal partitioning algorithm (i.e. tessellation / partitioning) of 2d polygons into smaller polygons?

Question

I have 2D polygons, each of which is a list of coordinates in a clockwise direction. Polygons are simple (i.e., they can be concave, but they do not intersect), and they do not intersect with each other.

I need to split these polygons into smaller polygons so that they fit the size constraints. Like the original polygons, the smaller ones must be simple (non-self-intersecting), and the restriction is that each of them must fit into one “unit square” (which for simplicity I can take as 1x1).

The fact is that I need to do this as efficiently as possible, where "effective" means the minimum number of received (small) polygons. The calculation time is not important.

Is there any smart algorithm for this? At first I thought about recursively dividing each polygon (dividing it in half, either horizontally or vertically, depending on which direction is larger), but I do not seem to get very optimal results from this. Any ideas?

Answer 1

Draw a circle with the center of one of the starting points of the original polygon and the radius of the desired length limit.

The circle will intersect at least two lines at two points. Now you have your first triangle as much as possible. Then select these intersections as the next target. Do until there are no starting points on the outside. You have your triangles as much as possible (as much as possible)

• Do not consider triangular edges already created as the intersection point.
• The resulting polygons are not always triangles; they can also be squares. Perhaps larger numbers too!
• All of them are almost equal to the desired size.

Fine tuning of the internal parts will require some calculation.

<T411>

Answer 2

I suggest you use the following:

• Triangulate a polygon, for example. using a sweep line algorithm.

• Make sure that all triangles do not violate the constraint. If someone violates the restriction, first try folding the edges to fix it, otherwise divide it by the longest edge.

• Use dynamic programming to join triangles, keeping the constraint and joining only adjacent polygons.