Given a start and end point, how can I constrain the end point so the resulting line segment is horizontal, vertical, or 45 degrees?

Question

I have a grid of letters. The player clicks on a letter and drags out a selection. Using Bresenham's Algorithm I can create a line of highlighted letters representing the player's selection.

However, what I really want is to have the line segment be constrained to 45 degree angles (as is common for crossword-style games).

So, given a start point and an end point, how can I find the line that passes through the start point and is closest to the end point?

Bonus: To make things super sweet I'd like to get a list of points in the grid that the line passes through, and for super MEGA bonus points, I'd like to get them in order of selection (i.e. from start point to end point).

Answer 1

I didn't test this results, but i think it should work.

Lets call the things by the names: Start point coordinates: (X1,Y1) End point coordinates: (X2, Y2) Resultant closest End Point: (RX, RY)

A line that passes in Start point can be described as [y = x + (Y1 - X1)], for 45 degree slope. Slope equals the tangent of the desired angle, tan(pi/4) = 1. 45 degree is pi/4 radians.

Now you have a line with beginning on your Start Point, and with no end, defined by the given equation. We need to find it's End Point.

The End Point is closer to the line 1 wherever the line 1 intersects a line 2 with inverse slope, which passes in EndPoint. This line could be represented by [y = -x + (Y2+X2)], following the same principle, which has now -45 degrees slope.

The point of intersection is therefore described by: [RX = (-Y1+X1+Y2+X2)/2] And you can find its corresponding image calculating RX for the Line 1 (the one that we have interest in) [RY = RX + (Y1-X1)]

And done, you have your line ready, its a line generated by the function [y = x + (Y1-X1)] with a start in StartPoint and a end in (RX,RY).

Bonus: Since you have the line equation, you can calculate list of points the line passes through by changing x for any value between X1 and RX.

To get them for the order of selection, you just need to start changing x for X1 and go up to RX. Pretty straightforward.

Tell me if it works :) If you want the line in -45 degrees too, its the same, but the Line 2 is the important one instead of Line 1. You figure it out easily. Hope it helps.

Answer 2

Also not tested, but this is one way to approach it..

Some preliminary calculations:

// Vector from x1,y1 to x2,y2:

xd = x2 - x1
yd = y2 - y1
len = sqrt(xd*xd + yd*yd)

Now we can test the trivial cases:

if (xd == 0) // exactly vertical
if (yd == 0) // exactly horizontal
if (abs(xd) == abs(yd)) // exactly diagonal

Otherwise, we'll need to round a bit.. First, let's see which way the axes are going

xsign = (x > 0) ? 1 : -1
ysign = (y > 0) ? 1 : -1

Now, let's check the x major case.

// x major
if (abs(xd) > abs(yd))
{
  d = yd / xd
  if (floor(d+0.5) == 0)
  {
    // about horizontal
    yd = 0
    xd = len * xsign
  }
  else
  {
    // about diagonal
    xd = len / sqrt(2) * xsign
    yd = len / sqrt(2) * ysign
  }
}

And similarly the y major case.

// y major
if (abs(yd) > abs(xd))
{
  d = xd / yd
  if (floor(d+0.5) == 0)
  {
    // about vertical
    xd = 0
    yd = len * ysign
  }
  else
  {
    // about diagonal
    yd = len / sqrt(2) * ysign
    xd = len / sqrt(2) * xsign
  }
}

Finding all the steps between these is a matter of building a line-drawing algorithm from (x1),(y1) to (x1+xd),(y1+yd).

Answer 3

The method I ended up using is to:

1. Get the vector from the start point to the end point
2. Get the angle of that vector
3. Snap that angle to a multiple of 45 degrees
4. Create a new vector with the same magnitude as the starting velocity but rotated by the snapped angle amount
5. Add this vector to the start point to get the snapped end point

The code I'm using, in Lua is:

function snapEndpoint(startpos, endpos)
  -- startpos and endpos are vectors
  local velocity = endpos - startpos
  local step = math.rad(45)

  local angle = -math.atan2(-velocity.y, velocity.x)

  local snapped = (round(angle / step) % 8) * step

  local base = vector(1, 0) * round(velocity:len())
  local tmp = startpos + base:rotated(snapped)

  return vector(round(tmp.x), round(tmp.y))
end

This gives me the end point of line segment that snaps to 45 degree angles and is the correct length. If I then use the start and end point with Bresenham's Algorithm I can generate a list of points within the line.

This list of points is always returned in left-to-right, top-to-bottom order. I can look at the direction of the original line and, based on that, reverse the order of the returned points to get an ordered selection.