Il peut y avoir une façon intelligente de le faire qui est plus rapide et plus facile, mais vous pouvez toujours pirater à travers elle comme ceci:
Vous connaissez la formule de distance: s = sqrt ((x2-x1)^2 + (y2-y1)^2).Pour appliquer cela, vous devez trouver les coordonnées x et y des points où la ligne intersecte les bords de chaque cellule de la grille. Vous pouvez le faire en branchant les coordonnées x et y des limites de la cellule dans l'équation de la ligne et résoudre pour x ou y le cas échéant. En d'autres termes, chaque cellule s'étend d'un point (x0, y0) à (x0 + 1, y0 + 1). Nous devons donc trouver y (x0), y (x0 + 1), x (y0) et x (y0 + 1). Pour chacun d'entre eux, la valeur x ou y trouvée peut être comprise ou non dans les plages de cette coordonnée pour cette cellule. Plus précisément, deux d'entre eux seront et deux ne le seront pas. Les deux qui correspondent aux bords que la ligne traverse, et les deux qui ne le sont pas sont des bords qu'elle ne traverse pas. D'accord, peut-être que cela semble assez confus, alors travaillons sur un exemple.
Disons que votre ligne a l'équation x = 2/3 * y. Vous voulez savoir où il croise les bords de la cellule s'étendant de (1,0) à (2,1).
Branchez x = 1 et obtenez y = 2/3. 2/3 est dans la gamme légale pour y - 0 à 1 - donc (1,2/3) est un point sur le bord où la ligne coupe cette cellule. A savoir, le bord gauche.
Branchez x = 2 et vous obtenez y = 4/3. 4/3 est en dehors de la plage pour y. Donc, la ligne ne passe pas par le bord droit.
Branchez y = 0 et vous obtiendrez x = 0. 0 n'est pas dans la plage pour x, donc la ligne ne passe pas par le bord inférieur.
Branchez y = 1 et obtenez x = 3/2. 3/2 est dans la gamme légale pour x, donc (3/2,1) est un autre point d'intersection, sur le bord supérieur.
Ainsi, les deux points où la ligne coupe les bords de la cellule sont (1,2/3) et (3/2,1). Branchez-les dans la formule de distance et vous obtiendrez la longueur du segment de ligne à travers cette cellule, à savoir sqrt ((1-3/2)^2 + (2/3-1)^2) = sqrt (1/4 +1/9) = sqrt (13/36). Vous pouvez l'approximer à n'importe quel niveau de précision souhaité.
Pour ce faire, dans un programme que vous auriez besoin de quelque chose comme: (je vais utiliser le code pseudo parce que je ne sais pas quelle langue que vous utilisez)
// 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"
Eh bien, je suis sûr vous pourriez rendre le code un peu plus propre, mais c'est l'idée.
Merci beaucoup, j'ai passé environ 3 heures pour que cela fonctionne correctement, mais c'était surtout des problèmes calculant ma pente (utilisait les points de début et de fin et non les points de ligne réels) et je ne savais pas comment calculer à Y-Intercept.Une fois que j'y suis parvenu, je devais aussi copier votre bloc de code pour inclure cellX-1 et Y-1 parce que j'avais des lignes dans plusieurs directions. Merci beaucoup! – James