Algorithm for determining a rectangle from coordinates

Question

I have user input consisting of a drawn rectangle (freestyle). Now this drawn figure is not perfect, so I would like to redraw the form for them based on the algorithm.

I have a bunch of coordinates from a custom drawing. I would like to find the largest (x, y) and lowest (x, y) coordinates and use the distance between them to determine the diagonal of the rectangle.

But it's hard for me to determine the largest coordinate (x, y) and the lowest (x, y) coordinate.

I cannot take the largest y with the largest x or the largest x with the largest y, for example, because maybe the user just made a random attempt on his line. (It makes sense?)

Pretend below is the user's drawn line. If I used the largest y with the largest x, I would not have the desired coordinate (because it will find the coordinate in a random ledge)

---- / \ ----/ \-------- ----- -- --------------/ \---------------/ \------/ \-- 

Hope you understand what I get ..

I suppose another way to put it is that I need the coordinate closest to (0,0), and if my canvas was 1000 x 1000, I would like the second coordinate to be closer to (1000,1000). (two extreme coordinates)

Can anyone help with this algorithm?

Thanks in advance!

Answer 1

if you want to find the nearest point to (0,0), then just find it!

 point FindClosestToOrigin(point[] P) { point closest = P[0]; foreach(point p in P) { if (DistanceOriginS(p) < DistanceOriginS(closest)) closest = p; } return closest; } float DistanceOriginS(point p) { return px*px + py*py; } 

You can easily change the algorithm to find the points closest to the rest of the edges of the screen.

Answer 2

Depending on how well you want the rectangle created by the algorithm to match user input, you can try the following:

• Match all x and y coordinates to give you the center of your rectangle (Xc, Yc).
• Find the highest and lowest x value, subtract the lowest value from the highest and divide by two. Repeat for y values. Call these Xs and Ys (s for the "side").
• Significant angles (upper left and lower right) will then become (Xc - Xs, Yc - Ys) and (Xc + Xs, Yc + Ys).
• If necessary, draw lines.

This will now give you a bounding box that contains all the points specified by the user. If you are looking for a more suitable type algorithm, replace the function (max-min) / 2 in the second step with the averaging function. A simple one can include averaging only points on one side of the center point (either above / below, or left / right) and use them as offsets from the center. Note that this will give you four offsets, only two of which will be used at any given time.

The rough idea suggested here can be customized to your taste, depending on what user input you expect (for example, how distorted you expect it to be). Further improvements can be made using linear regression lines, assuming that you can distinguish between sides either through the points themselves, or using user input methods (for example, on each side of a rectangle with a discrete action, and not right away).

We hope that this quick example will point you in the right direction.

Answer 3

Just average over all points and use it as the position of the sides of the rectangle. Of course, this assumes that you can distinguish the four sides of the rectangle, otherwise you could try to split the coordinates into 4 sides (by checking the horizontal and vertical changes with a certain threshold), and then calculate the average value for each side and set it to the sides.