A js graphic Segmentation algorithm

it is known that a polygon consists of n squares of the same size (this polygon is not necessarily a rectangle, but it must be a figure made up of squares). To cut this figure, you can only cut from the edge of each square. When you click submit, you can judge that all the cut areas have the same shape and area.
for example, this figure (Baidu randomly found a grid image), the red line divides the figure into four pieces. How to judge the shape of the four pieces? (ps: red lines are straight, red lines can only be straight from end to end)
clipboard.png


an idea:

  1. uses an array to store the vertex coordinates of a block in turn, and defines three transformations for this array.
  2. defines a translation transformation: place the translation of the graph in the first quadrant of the coordinate system and have at least one edge of the graph on the x-axis and y-axis. The calculation is simple, using (min (x1), min (x2), min (.) as the origin
  3. defines the first 90 degree rotation transformation, which rotates the graph as a whole 90 degrees, and uses the translation transformation in 2 to prevent it from being in a quadrant. Such a figure has four representations in a quadrant coordinate.
  4. defines a half-fold transformation up and down.
  5. such a graph has 8 representations within a quadrant, which proves that the above 8 representations are complete. (for example, left and right half fold can be obtained by adding 180 degree rotation up and down).
  6. to compare whether the two graphics are congruent, you can compare their corresponding eight coordinate representations, otherwise they are equal.

the following figure is a hint of four representations, and the other four are obtained by flipping up and down respectively:

suddenly found that it might be more convenient to use the centroid as the origin, for example, as long as the vertical coordinate is reversed when folding up and down. In addition, you can think for yourself if there is any way to optimize it.

Menu