CODEWITHSUNDEEP
algorithmgeometrydrawingcoordinates
developer
developer

Reputation: 7400

algorithm to determine a rectangle from coordinates

I have user input that consists of a drawn rectangle (freestyle). Now this drawn figure isn't perfect, so I would like to redraw the shape for them based on an algorithm.

I have a bunch of coordinates from the user's drawing. I would like to find the greatest (x,y) and the lowest (x,y) coordinates and use the distance between those to determine the diagonal of the rectangle.

But I'm having difficulty determining the greatest (x,y) coordinate and the lowest (x,y) coordinate.

I can't take the greatest y with the greatest x, or the greatest x with the greatest y for example because maybe the user just made an accidental jut out in their line. (Does that make sense?)

Pretend below is a user drawn line.. if i used the greatest y with the greatest x, I would not have the desired coordinate (because it would find the coordinate in the accidental jut out)

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

Hope you understand what I'm getting at..

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

Can anyone help with this algorithm?

Thanks in advance!

Upvotes: 4

Views: 2678

Answers (3)

MysteryMoose
MysteryMoose

Reputation: 2363

Depending on how well you want the algorithm-generated rectangle to fit the user input, you might try the following:

  1. Average all x and y coordinates to give you the center of your rectangle, (Xc, Yc).
  2. Find your highest and lowest x value, subtract the lowest from the highest and divide by two. Repeat for the y values. Let us call these Xs and Ys (s is for 'side').
  3. The important corners (upper left and lower right) would then become (Xc - Xs, Yc - Ys) and (Xc + Xs, Yc + Ys).
  4. Draw lines as appropriate.

Now, this will give you a bounding-box wherein all user given points are contained. If you are looking for more of a best-fit type algorithm, replace the (max - min) / 2 function in step two with an averaging function. A simple one might involve averaging only points to one side of the center point (either above / below or left / right) and using those as offsets from center. Note that this will give you four offsets, only two of which you will use at any given time.

The rough idea presented here can be tuned to taste, depending on what kind of user input you are expecting (e.g. how distorted you expect it might be). Further improvements can be made using linear regression lines, assuming you are able to distinguish sides either via the points themselves or by user input methods (ex. drawing each side of the rectangle with a discrete action rather than all at once).

Hope this quick example will point you in the right direction.

Upvotes: 2

DennyRolling
DennyRolling

Reputation: 486

if you want to find the closest 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 p.x*p.x + p.y*p.y;
}

you can easily modify the algo to find points closest to the rest of screen edges.

Upvotes: 1

Jack
Jack

Reputation: 133577

Just do an average over all points and use it as the position of rectangle sides.. of course this assumes you are able to distinguish the four sides of the rectangle otherwise you could try a way to split the coordinates into 4 sides (by checking the horizontal and vertical variation with some threshold) and then compute the average for each side and adjust it to link sides.

Upvotes: 0

Related Questions