Может быть какой-то умный способ сделать это быстрее и проще, но вы всегда можете взломать его так:
Вы знаете формулу расстояния: s = sqrt ((x2-x1) ^2+ (у2-у1) ^ 2).Чтобы применить это, вы должны найти координаты x и y точек, где линия пересекает края каждой ячейки сетки.Вы можете сделать это, вставив координаты x и y границ ячейки в уравнение линии и решив для x или y соответственно.
То есть каждая ячейка простирается от некоторой точки (x0, y0) до (x0 + 1, y0 + 1).Поэтому нам нужно найти y (x0), y (x0 + 1), x (y0) и x (y0 + 1).Для каждого из них найденные значения x или y могут находиться или не входить в диапазоны для этой координаты для этой ячейки.В частности, два из них будут, а два - нет.Два, которые соответствуют ребрам, через которые проходит линия, и два, которые не являются ребрами, через которые она не проходит.
Хорошо, возможно, это звучит довольно запутанно, поэтому давайте разберемся спример.
Допустим, ваша строка имеет уравнение x = 2/3 * y.Вы хотите знать, где он пересекает края ячейки, простираясь от (1,0) до (2,1).
Подключите x = 1, и вы получите y = 2/3.2/3 находится в допустимом диапазоне для y - от 0 до 1, поэтому (1,2 / 3) - это точка на краю, где линия пересекает эту ячейку.А именно, левый край.
Подключите x = 2, и вы получите y = 4/3.4/3 вне диапазона для y.Таким образом, линия не проходит через правый край.
Подключите y = 0, и вы получите x = 0.0 не находится в диапазоне для x, поэтому линия не проходит через нижний край.
Подключите y = 1, и вы получите x = 3/2.3/2 находится в допустимом диапазоне для x, поэтому (3 / 2,1) является другой точкой пересечения на верхнем краю.
Таким образом, две точки, где линия пересекает края ячейки,(1,2 / 3) и (3 / 2,1).Включите их в формулу расстояния, и вы получите длину сегмента линии через эту ячейку, а именно sqrt ((1-3 / 2) ^ 2 + (2 / 3-1) ^ 2) = sqrt (1/4+1/9) = SQRT (13/36).Вы можете приблизить это к любому желаемому уровню точности.
Чтобы сделать это в программе, вам понадобится что-то вроде: (Я буду использовать псевдокод, потому что я не знаю, какой язык вы используете)
// Assuming y=mx+b
function y(x)
return mx+b
function x(y)
return (y-b)/m
// cellx, celly are co-ordinates of lower left corner of cell
// Upper right must therefore be cellx+1, celly+1
function segLength(cellx, celly)
// We'll create two arrays pointx and pointy to hold co-ordinates of intersect points
// n is index into these arrays
// In an object-oriented language, we'd create an array of point objects, but whatever
n=0
y1=y(cellx)
if y1>=celly and y1<=celly+1
pointx[n]=cellx
pointy[n]=y1
n=n+1
y2=y(cellx+1)
if y2>=celly and y2<=celly+1
pointx[n]=cellx+1
pointy[n]=y2
n=n+1
x1=x(celly)
if x1>=cellx and x1<=cellx+1
pointx[n]=x1
pointy[n]=celly
n=n+1
x2=x(celly+1)
if x2>=cellx and x2<=cellx+1
pointx[n]=x2
pointy[n]=celly+1
n=n+1
if n==0
return "Error: line does not intersect this cell"
else if n==2
return sqrt((pointx[0]-pointx[1])^2+(pointy[0]-pointy[1])^2)
else
return "Error: Impossible condition"
Ну, я уверен, что вы могли бы сделать код немного чище, но это идея.