2
\$\begingroup\$

Say you have a point on a grid, lets call it P and your have a direction vector called V, how do i find the closest point from P in V's direction ?

Example:

1|2|3
4|P|5
6|7|8

V = (0.5 , 0.5)

In this basic example the next point is 3. How do I make a general algoritm for more complex cases, say V = ( 0.44, -0.56) ?

EDIT: Just to clarify something in my question. The next point has to be a neighbor to point P.

\$\endgroup\$
  • 2
    \$\begingroup\$ How precisely does the point need to lie on the line? Would you prefer a nearby point that's less than some epsilon value away from the line, or an exact hit that's tens of thousands of units away from our origin point P? \$\endgroup\$ – DMGregory Jul 16 '18 at 22:22
  • \$\begingroup\$ I would add (sorry DM, just rephrasing if im right...), there are 2 tests for closest based upon your criteria. Are you looking at the closest in terms of angle from vector ala via Dot Product in the direction of the vector, OR, are you looking at the closest distance Perpendicular to the ray. \$\endgroup\$ – ErnieDingo Jul 17 '18 at 0:25
  • \$\begingroup\$ @DMGregory sorry I will clarify that in the question. The next point has to be a neighbor to point P. \$\endgroup\$ – Fredrik Boston Westman Jul 17 '18 at 8:39
  • \$\begingroup\$ @ErnieDingo closest in terms of angle from vector, I think, lot sure I understand your question \$\endgroup\$ – Fredrik Boston Westman Jul 17 '18 at 8:41
  • \$\begingroup\$ @FredrikBostonWestman in that case you could use the Dot Product of the vector from origin and the direction vector you mentioned. The other way gives you the closest distance to the vector if the vector was to go on forever. \$\endgroup\$ – ErnieDingo Jul 17 '18 at 9:34
2
\$\begingroup\$

The angle of the vector V can be calculated as atan(V.y/V.x), and since the angle from one point on the grid to the 8 neighbors is known you can compare the angle of V with the angle to each neighbor and take the smallest delta.

The starting point P is irrelevant in determining the closest neighbor as that only depends on the direction of V (and when found, offset by P).

For convenience I've re-numbered your cells so that instead of

1 2 3
4   5
6 7 8

mine are numbered

3 2 1
4   0
5 6 7

But that's just because it's more convenient to calculate a lookup-table for the angles to the neighbors.

A naive implementation might look something like this;

import static java.lang.Math.abs;
import static java.lang.Math.cos;
import static java.lang.Math.sin;
import static java.lang.Math.atan;
import static java.lang.Math.PI;

public class Program {

    // Class to represent a grid point
    public static class Point {
        public final int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return x + ", " + y;
        }
    }

    private final static double TAU = PI * 2;
    private final static double[] angles = new double[8 + 1];

    // build up a lookup-table to the angle of the neighbors
    // this is calculated as PI * 2 / index of the neigbor in a counter-clockwise rotation 
    // which is convenient because that is what cos, sin and atan expects
    // the last index is duplicated so that 0 degrees and 360 degrees are both accounted for.
    static {
        final double step = TAU / (double)(angles.length - 1);
        for(int i=0; i< angles.length; ++i)
            angles[i] = step * (double)i;
    }

    private static double getAngle(double dx, double dy) {
        if (dx == 0 && dy == 0)
            throw new RuntimeException("No direction!");

        if (dx == 0) {
            return dy < 0 ? PI * 0.5 : PI * 1.5;
        }

        if (dy == 0) {
            return dx < 0 ? PI : 0;
        }

        return atan(dy / dx);
    }

    private static int getGridIndex(double angle) {

        int bestIndex = -1;
        double bestDelta = Double.MAX_VALUE;
        for(int i = 0; i < angles.length; ++i) {
            double delta = abs(angle - angles[i]);
            if (delta < bestDelta) {
                bestDelta = delta;
                bestIndex = i;
            }
        }

        return bestIndex;
    }

    private static Point getGridPoint(Point input, double dx, double dy) {
        int index = getGridIndex(getAngle(dx, dy));
        switch(index) {
            case 0: 
            case 8: return new Point(input.x + 1, input.y + 0);
            case 1: return new Point(input.x + 1, input.y + 1);
            case 2: return new Point(input.x + 0, input.y + 1);
            case 3: return new Point(input.x - 1, input.y + 1);
            case 4: return new Point(input.x - 1, input.y + 0);
            case 5: return new Point(input.x - 1, input.y - 1);
            case 6: return new Point(input.x + 0, input.y - 1);
            case 7: return new Point(input.x + 1, input.y - 1);
            default:
                throw new RuntimeException("Impossible!");
        }
    }

    public static void main(String[] args) {
        Point p = new Point(0, 0);
        for(double a = 0; a <= TAU; a += TAU / 8.0)
        {
            double dx = cos(a);
            double dy = sin(a);
            System.out.println("Vector: " + dx + ", " + dy);
            System.out.println("Angle : " + getAngle(dx, dy));

            System.out.println("Next point : " + getGridPoint(p, dx, dy));
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you, to me this sound like the easiest and most pragmatic approach :) \$\endgroup\$ – Fredrik Boston Westman Jul 17 '18 at 12:57
1
\$\begingroup\$

Note 1: You're better off not normalizing your direction vector, since normalizing may result in rounding errors. However, assuming no precision issues, take your vector's slope (y / x), and simplify to the simplest fraction with integral numerator and denominator: (y'/x'). Now you can take a new V vector (x', y') . Here are your two examples:

  1. Example 1: Start = (1, 1), V = (0.5, 0.5). slope as a fraction = ((1/2) / (1/2)) = (1 / 1), end = (1, 1) + (1, 1) = (2, 2)

  2. Example 2: Start = (-10, 0), V = (0.44, -0.56). Slope as a fraction = (-0.56 / 0.44) = - ((56 / 100) / (44 / 100) = (56 / 44) = (14 / 11). An equivalent V with slope (-14/11) is (11, -14). Our ending point is at (-10, 0) + (11, -14) = (1, -14).


If you are worried about precision issues causing you to nearly-miss the grid point, you can consider using a rational approximation algorithm, such as by using a truncated continued fraction. For example, if we were looking for a point with V = (1, 3.14159), instead of using V = (314159 / 1000000), we could take one of the continued fraction expansions of 3.14159:

V = 3 / 1 = 3.0
V = 22 / 7 = 3.142857...
V = 333 / 106 = 3.1415094...
V = 355 / 113 = 3.1415929...
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I am sorry I think I should have clarified. The next point has to be a neighbor to point P. Thank you for your answer tho :) as for normalizing, I am not in control of that part, it is rules by other factors, so we just have to assume it is normalized :) \$\endgroup\$ – Fredrik Boston Westman Jul 17 '18 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.