The following plan arose: there are a number of points forming something like a rectangle. However, it is not directed along axes (not AABB). The task is to find a vector that will be sent in the same way as the high height of the conditional rectangle.

The only solution that comes to mind is to draw some straight line through the conditional center of the rectangle, and then for points on one side we do the following: we find the distance from the center, squaring it. Sum these values. We do the same on the other side of the straight line. Then we draw another straight line, already at a different angle.

We perform the operation Nth number of times until we find a straight line, the sum of the weights of the points on either side of which will be maximal.

Why I do not like this method? It’s not a fact that it will work correctly, and I also have to perform these actions N times, and the more - the more accurate, and therefore it is too expensive. What can be done to find a vector with less cost?

    2 answers 2

    "Everything has been invented long ago." Gennady Khazanov

    The main axes and the main points of inertia.

    Find the center of gravity of the set of points. Then - moments of inertia about axes parallel to the axes of coordinates and passing through the center of gravity, as well as the central moment of inertia about the center of gravity. Orientation of the main axes:

    tan(2a) = 2 Iyx / (Iy - Ix)

    http://www.soprotmat.ru/geom2.htm

    http://mysopromat.ru/uchebnye_kursy/sopromat/geometricheskie_harakteristiki/glavnye_osi_glavnye_momenty_inertsii/

    Update

    If the distribution of points inside the "oblique rectangle" is uneven, to find the center of gravity and moments of inertia, it is necessary to use not a set of points, but an envelope convex polygon - convex hull ( https://en.wikipedia.org/wiki/Convex_hull ).

    • I do not quite understand what the "orientation of the main axes" means. I found the angle, and if the imaginary rectangle is deflected to <PI / 4, then everything seems normal, but if you deflect more, the angle does not increase, but begins to decrease. As if this is the minimum angle between the axis of coordinates and one of the main axes. This is the case? - selya
    • Yes. In the end, you will have two perpendicular directions, take one for which the moment of inertia is less - this will be the longitudinal axis of the "rectangle". - Igor

    About your algorithm. It can return both a vector along its greater and lesser heights. In addition, the number of points on different sides of the line can be different, which can lead to quite large errors.

    I would do something like the following. I will describe without formulas, choose them yourself to achieve the result.

    1. Draw a rectangle, the sides of which lie along the axes of coordinates and pass through at least one point. That is, it turns out that something like a rectangle described around the points with two sides parallel to the X axis and two to the Y axis. enter image description here
    2. The points that lie on the sides of the resulting rectangle will be the vertices of the new quadrilateral. If there are sides on which there is more than one point, then we build all quadrilaterals that succeed (with the condition that there is only one vertex of the new rectangle on one side of the rectangle). After that, from the resulting quadrangles, choose the only one, the modulus of the difference in the lengths of the diagonals of which will be the smallest, and the average value of any two opposite corners will be as close as possible to 90 degrees. enter image description here
    3. In the resulting quadrilateral, from each of its vertices, we build perpendiculars to two sides that do not belong to this vertex. We have 8 intersection points of the resulting perpendiculars with straight lines passing through the sides of the quadrilateral (2 at each vertex). enter image description here
    4. Between the two points near each vertex, obtained in the previous paragraph, we draw segments.
    5. We put dots on the centers of these segments. enter image description here
    6. These points will be the vertices of the final quadrilateral. Next you know. enter image description here

    Threat If it is too difficult, I can draw pictures, but really do not want. Read the algorithm and draw the pictures yourself; it will become clearer on paper.

    ZYY Kartinochki added. As you can see, the resulting rectangle is not exactly in the place where you would spend it and, possibly, different in size, but this is not important to you. The main thing is that the direction and proportions are preserved, which is enough to get the desired result.

    However, if you need not only the direction of the vector, but also its size, you can make inscribed and described rectangles from the final rectangle (without rotating the final one, but simply by changing the size and position). Next, connect their nearest vertices with segments and build a rectangle through the centers of these segments. But, as I understand it, this is not required.

    ZYYY Formulas that you need are quite simple from the initial geometry courses.

    ZYYYY This decision is based on intuition and I do not want to prove his loyalty now.

    • "quadrangles ... the average angle of which will be as close as possible to 90 degrees" - priceless - Igor
    • @Igor, yes, you are right that something is wrong here: D Scha will correct it) - iRumba
    • I wonder what the average angle in a quadrilateral depends on. - Igor
    • @Igor, yes, everything, everything, I realized my mistake. Already fixed) - iRumba
    • @igor, it was difficult to formulate without a clear definition of a rectangle something like "a figure resembling a rectangle". The general meaning of the test is: "choose from all quadrangles the one that most resembles a rectangle." And how else do you think the way is working? - iRumba