This was an interesting puzzle.
I approached it from pure geometry math.
Each cell is defined by 4 line segments. So to determine if a transecting line segment intersects any cell you need only to determine if it intersects with any of those 4 line segments.
The below script not only finds all the cells intersected but also the point XY information of where all the intersections occur.
Code: Select all
for N, Points in Cells_Intersected(120, 40, 280, 460)
Display .= N ", "
Display := Trim(Display, " ,")
MsgBox % "Cells Intersected `n" Display
Display := ""
for N, Points in Cells_Intersected(280, 20, 455, 445)
Display .= N ", "
Display := Trim(Display, " ,")
MsgBox % "Cells Intersected `n" Display
Display := ""
for N, Points in Cells_Intersected(280, 20, 455, 20)
Display .= N ", "
Display := Trim(Display, " ,")
MsgBox % "Cells Intersected `n" Display
Display := ""
for N, Points in Cells_Intersected(100, 100, 400, 100)
Display .= N ", "
Display := Trim(Display, " ,")
MsgBox % "Cells Intersected `n" Display
for N, Points in Cells_Intersected(120, 40, 280, 460)
for index, Point in Points
MsgBox % "Cell: " N "`nPoint " index ":`t" Point.x ", " Point.y
Cells_Intersected(x1, y1, x2, y2, Col:=11, Row:=10, Size:=50)
{
Segs := {}, Result := {}
Loop
{
N++
cCol := Floor((N-1)/Row)+1
cRow := N-(cCol-1)*Row
px := (cCol-1)*Size
py := (cRow-1)*Size
Segs.1 := [px, py, px+Size, py]
Segs.2 := [px+Size, py, px+Size, py+Size]
Segs.3 := [px+Size, py+Size, px, py+Size]
Segs.4 := [px, py+Size, px, py]
ps := 0
for index, Seg in Segs
if (p := LineSeg_Intersection(x1, y1, x2, y2, Seg*))
ps++, Result[N,ps] := p
} until (N = (Row * Col))
return Result
}
; [Function] LineSeg_Intersection
; Author: FanaticGuru
; 11/22/2017
;
; Parameters:
; s1a_x x of segment 1 point a
; s1a_y y of segment 1 point a
; s1b_x x of segment 1 point b
; s1b_y y of segment 1 point b
; s2a_x x of segment 2 point a
; s2a_y y of segment 2 point a
; s2b_x x of segment 2 point b
; s2b_y y of segment 2 point b
;
; Return:
; false no intersection of segments
; true collinear of segments
; object {X , Y} of intersection point of segments
;
; Example:
; p := LineSeg_Intersection(1,1,4,4,4,1,1,4)
; MsgBox % p.x ", " p.y ; intersection point is at 2.5, 2.5
;
LineSeg_Intersection(s1a_x, s1a_y, s1b_x, s1b_y, s2a_x, s2a_y, s2b_x, s2b_y)
{
s1_x := s1b_x - s1a_x
s1_y := s1b_y - s1a_y
s2_x := s2b_x - s2a_x
s2_y := s2b_y - s2a_y
d := s1_x * s2_y - s2_x * s1_y
if !d ; parallel
{
if (LineSeg_Point(s1a_x, s1a_y, s1b_x, s1b_y, s2a_x, s2a_y) ||
. LineSeg_Point(s1a_x, s1a_y, s1b_x, s1b_y, s2b_x, s2b_y)||
. LineSeg_Point(s2a_x, s2a_y, s2b_x, s2b_y, s1a_x, s1a_y) ||
. LineSeg_Point(s2a_x, s2a_y, s2b_x, s2b_y, s1b_x, s1b_y))
return true ; collinear
}
s := (-s1_y * (s1a_x - s2a_x) + s1_x * (s1a_y - s2a_y)) / d
t := ( s2_x * (s1a_y - s2a_y) - s2_y * (s1a_x - s2a_x)) / d
if (s >= 0 and s <= 1 and t >= 0 and t <= 1)
{
iX := s1a_x + (t * s1_x)
iY := s1a_y + (t * s1_y)
return {X: iX, Y: iY} ; intersection
}
return false ; no intersection
}
; determine if point is on line segment
LineSeg_Point(segA_x, segA_y, segB_x, segB_y, p_x, p_y)
{
if !Point_Orientation(segA_x, segA_y, segB_x, segB_y, p_x, p_y)
if (min(segA_x, segB_x) <= p_x && p_x <= max(segA_x, segB_x))
if (min(segA_y, segB_y) <= p_y && p_y <= max(segA_y, segB_y))
return true
return false
}
; 3 point orientation: 1 = clockwise, -1 = counter-clockwise, 0 = collinear points
Point_Orientation(p1_x, p1_y, p2_x, p2_y, p3_x, p3_y)
{
v := (p2_y - p1_y) * (p3_x - p2_x) - (p2_x - p1_x) * (p3_y - p2_y)
return (v > 0) ? 1 : (v < 0) ? -1 : 0
}
Min(List*)
{
X := List[1]
for key, element in List
if (element < X)
X := element
return X
}
Max(List*)
{
X := List[1]
for key, element in List
if (element > X)
X := element
return X
}
The function LineSeg_Intersection might be useful for other uses so I commented it some.
The toughest part for me was the handling of collinear line segments where the segments overlap. The functions
LineSeg_Point and
Point_Orientation were needed for that. There is probably a better way than looking for each line segment's end points on the other line segment but at the time I thought about returning the overlapping line segment but it made the return object a little cumbersome.
The main function
Cells_Intersected allows for any number of columns and rows as well as the ability to set the size of each cell.
I put some example lines that were horizontal and vertical that also fell exactly on the grid line. Those could be problem cases for some solutions.
I had to go out on the internet and study geometry math. I was surprised not to find definitive perfect code out there for how to find the intersection of line segments. Lots of code but many that don't always work. Some fail on parallel lines, some fail on collinear line segments that overlap, some fail on collinear line segments that don't overlap, line segments that intersect at end points, etc.
There might be ways I could simply the algorithms and variables. Handling the points and line segments as objects would probably help to keep all the variables more clear but I was just happy to get it to work. Makes me want to brush up more on my geometry math.
Edit: Added my version of Min/Max functions. Forgot they were not standard AHK functions.
FG