It is required to minimize the number of points with at least one integer coordinate on the line. How to do it?

Question

Python

I have the coordinates of two points. I need to draw a polyline between them so that the number of intersections of this polyline with coordinates where at least one of them is an integer is minimized. How can I do this and how do I find the number of these intersection points?

Here is a piece of code that, in theory, was supposed to do this:

rx = x1 - x0
ry = y1 - y0

if abs(rx) < abs(ry):
    res.append(abs(ry) + 1)
else:
     res.append(abs(rx) + 1)
k += 1

x0 and x1 are the coordinates of the first point, and y0 and y1 are the coordinates of the second point.
In res, as planned, I should have an answer (I put the answers in the list, because there can be several points).
Thanks in advance for any help.

Answer 1

Represent the grid along integer coordinates. Your two points are in some cells. To move from one cell to the next, you will have to cross the border - this will be the considered point.
Those. you need to find a way from one cell to another, passing through as few cells as possible. You can walk in 8 directions - if you cross the corner, you can go diagonally for one point on the broken line.
After a bit of drawing, you will realize that the answer is the minimum of the horizontal and vertical distances between the start and end cells.
It is only necessary to carefully analyze the cases when the starting or ending point lies on the border of the cell.