Java, Generate a direct path of points between two points

Question

I currently have a bad method for doing this, it just translates the start point by 1/-1 depending on if the x/y coordinate is over or under the current coordinates and adds it to an ArrayList until the start point .equals(end), this is a bad solution because it creates a really bad path that looks like the black path below.

I'm trying to generate a direct path of points between two points (The same kind of line as Graphics.drawLine makes).

I'm guessing I need to use the Math class to get the angle, but I'm not very familiar with the Math API.

Can you show how do you generate it now so we can understand API you're using (point class, path class). — Mikita Belahlazau, Jul 31 '12 at 15:25
Seems to me this isn't so much a Java question as a trigonometry question. Once you know the maths, looking up the relevant functions in the Math API is trivial. — slim, Jul 31 '12 at 15:34
I don't get it. Why not to return an array of points, where first point is start and second point is end? You can only make step of length 1? — Mikita Belahlazau, Jul 31 '12 at 15:35
If it's solved accept an answer. If none of the answers is comprehensive, write your own answer and accept that! — slim, Aug 02 '12 at 13:24

slim · Accepted Answer · 2012-07-31T15:58:35.320

6

One somewhat naive way, is to work out the ratio of the slope, rather than the angle.

Something like:

float ratio = (y2 - y1) / (x2 - x1);

Then:

width = x2 - x1;
for(int i = 0; i < width; i++) {
    float x = x1 + i;
    float y = y1 + (ratio * i);
    points.add(new Point(x,y));
}

If float isn't what you need, you'll need to do some conversion.

You'll also need to handle the special case of x1 == x2, or you'll get divide-by-zero errors.

Using this method, the steeper the line, the fewer points you will generate. If you want the points evenly spaced no matter what the angle, you'll need to break out sin/cos/tan.

Write unit tests for lines in at least the main 8 compass directions, to iron out any glitches.

edited Jul 31 '12 at 15:58

answered Jul 31 '12 at 15:44

slim

40,215
13
94
127

I thought slope was the change in Y over the change in X? So `(y2 - y1)/(x2 - x1)` ? – Roddy of the Frozen Peas Jul 31 '12 at 15:48
You have to be careful when the slope is infinity. – RedGreasel Jul 31 '12 at 15:51
1

Could you explain the special case of divide by zero? How could be solved – bellotas Sep 16 '20 at 14:10
1

@mario well, when x1 == x2, `x2 - x1` == 0, so you'll get a divide by zero from the code I've supplied. But you know you want to draw a simple vertical line, so just use an `if` (or whatever) to draw the vertical line instead of running the code that will break. – slim Sep 28 '20 at 14:32

score 1 · Answer 2 · answered Jul 31 '12 at 15:44

This is actually more of a math problems than a programming problem. You need to find the vector that goes from start to end and then scale it and add it to start for the number of points that you want.

In pseudo code:

f(start,end,nPoints) -> (path)
   delta = (end-start) / nPoints //Find the best difference vector.
   current = start //Set the current point to the start.
   i = 0
   while(|current-end| < epsilon)
      current += delta
      path[i] = current
      i = i + 1

I'm assuming that the points are floating point (due to the division). epslion should be chosen to be a small value (depends on your problem) to check equality (never use != for floating points!).

score 1 · Answer 3 · answered Jul 31 '12 at 15:45

This is a very simple concept, but you've not been too clear on what exactly you want. By definition, there are an infinite number of points between any two points (and between two of those points, exist an infinite number of points. And so on.)

The simplest solution would be to calculate the formula for the line between point A and point B, and then decide how far apart you want your points to be, and calculate those points using your line formula.

Elementary geometry tells us that the slope between two points in the change in y over the change in x. So m = (y1 - y2)/(x1 - x2), where all of these values are doubles, and x1 and y1 belong to the same point.

Then the formula for the line between two points is y - y1 = m(x - x1). Then all you'd have to do is start plugging in values for, say, x, taking the resultant y, and drawing it.

This is, of course, the idea behind the whole thing. You'd be much better off using vectors.

score 0 · Answer 4 · edited May 23 '17 at 11:53

0

Check out this previously answered question to calculate the angle. And then use the distance formula to find the distance.

double dist = Math.sqr((x2 - x1)^2 + (y2 - y1)^2);  //obviously wont compile but you get the idea.

edited May 23 '17 at 11:53

Community

1
1

answered Jul 31 '12 at 15:29

Zoop

646
5
7

Java, Generate a direct path of points between two points

4 Answers4