The task is to find the area (length and width) of a rectangle describing a contour consisting of primitives (arcs and lines). I have the coordinates of the points forming these primitives (the red dots in the picture)

picture 1

There are also coordinates of cents of arcs, but perhaps they are not needed now. I solved the problem according to the following algorithm:

  1. compiled segments of all points, that is, connected each point with each;
  2. searched among the segments those that are perpendicular to each other;
  3. Among the pairs of perpendicular segments, I found those with the greatest product. This was the width and length of the desired rectangle (and, consequently, the area).

This algorithm worked well for most figures, including the one shown in the first figure. But I ran into the figure from the second drawing:

drawing2

It is clear that my algorithm did not work here. Width he chooses the right (bottom base), but the length is not, because there is no coordinate of the center of the lower base, so that it would be possible to construct a segment connecting the center of the lower base with the highest point.

There was an option to find the center of the lower base, but this option is only for the second pattern. And if the situation suddenly arises from Figure 3, the algorithm again becomes inoperative. Because the segment connecting the top point with the center of the bottom base will not be perpendicular to the bottom base.

drawing3

Please tell me a version of the general algorithm for finding the length and width of the rectangle describing the contour.

  • Give an exact definition of what you have a β€œrectangle describing the contour”. - VladD
  • If you mean that the rectangle cannot be rotated (the sides are parallel to the sides of the image), I would walk through all the points and find the minimum & maximum along the X and Y axis, but this option will not work for your first image (there the curve above will go beyond the rectangle ). To solve this problem, I would add a lot more points around the contours and walked, roughly speaking, β€œon each contour with a small step” (for example, 1 pixel). This is the case if I had only a "curve" and a "straight line". But if you use a circle with its radius and center instead of a curve, you can read therainycat
  • @VladD, unfortunately there is no direct definition. But as I imagine, this is a rectangle with the smallest area in which you can fit the selected shape. - rudolfninja
  • @therainycat, from the points there is only what is highlighted. You can, of course, programmatically calculate the points, but this will significantly increase the processing time (finding the desired rectangle) of one shape. - rudolfninja
  • @rudolfninja simply did not specify how the miscalculation is conducted - by program or manually. In fact, the program calculates everything very quickly - for example, straight lines do not need to be broken into small segments, there are enough start and end points. And the curves, as I understand it, are Bezier curves, they can also be calculated very quickly. I do not know how much data should be processed, but such figures can be processed in tens or even hundreds / thousands per second. Specify what data is in the input (file format / data array), maybe I'll write you a script. - therainycat

1 answer 1

Here are some partial solutions for your problem, for polygons, without segments of circles.

I will try to draw an analogy with the method of "rotating calipers" (I do not know a good Russian name).

Consider covering rectangles whose base is at a certain angle Ο† to the horizontal. Let S (Ο†) be the area of ​​this rectangle. Our goal is to find the extremum of this function on [0, Ο€ / 2).

Let Ο† = 0 to begin with. Consider the covering rectangle:

scan, yes

In our case, the sides of the enclosing rectangle pass through the vertices A ₁, A and A ₁, A, respectively. To begin with, we find the range of the angle Ο†, at which it will still be so. We first find out how far the lower base can be rotated so that the lower side still rests on the vertex A ₁. This angle will be the minimum of the angles of the rays A ₁ A β‚‚, A A ₃, A ₁ A β‚„, A ₁ A β‚…. Similarly, we find the ranges of rotation for the remaining four sides. The intersection of these ranges will give the range of values ​​of Ο†, inside which the enclosing rectangle rests on the same vertices.

For this range, we find the extreme value of the area. Let the angle of the segment A ₁ A β‚„ with the horizontal be φ₁, and the angle of the segment A ₁ A β‚… - Ο†β‚‚. Let d ₁ = | A ₁ A β‚„ |, d = | A ₁ A β‚… | The vertical side of the rectangle is d ₁ sin (Ο† - φ₁), the horizontal - d β‚‚ sin (Ο† + Ο€ / 2 - Ο†β‚‚) = d cos (Ο† - Ο†β‚‚).

The area is d d d β‚‚ sin (Ο† - Ο† ₁) cos (Ο† - Ο† β‚‚) = d ₁ d (sin (2 Ο† - Ο† ₁ - Ο† β‚‚) + sin (Ο† - Ο† ₁)) / 2. In order to find the extremum of this value, we can discard the constants d ₁ d β‚‚ / 2 and sin (Ο†β‚‚ - φ₁), and recall that the minimum of the sine is reached at the point where the argument is 3Ο€ / 2 + k Β· 2Ο€, or the ends of the segment.

Comparing the value of the area at the ends of the segment, as well as at points of the form 3Ο€ / 4 + (φ₁ + Ο†β‚‚) / 2 + k Β· Ο€ (if they fall on the segment), we obtain the minimum on this segment.

Okay. Easy further. Turning the base further, we proceed to the consideration of the case when the reference point of the lower base is A β‚…, we repeat the consideration on this interval of Ο† values. Continue until Ο† reaches Ο€ / 2.

Everything.

You will need to generalize this algorithm for the case of curved sides. Here the pivot point will roll along the arc with a change in Ο†, which, in principle, allows for the same consideration.

Dare!

  • Thank. Found the Russian version of the proposed algorithm (diameter of the set of points). I will try to implement it. It seems like, with his help, you can solve my problem. - rudolfninja