Basically, I have a grid with certain contiguous cells marked (in grey) as below:

I want to draw a line intersecting all the squares. It has be a single line and it must necessarily be intersecting with all the marked squares, but it can intersect non-marked cells too. Is there any algorithm/sample program for determining such a line? I am not knowledgeable about geometric algorithms in general, so any guidance is appreciated.

CodePudding user response：

A conceivable way is Line fitting with an objective function that returns very bad values if some grid does not intersect the line(: Penalty Method) .

I think this is not the best, but may become one way.

CodePudding user response：

A line ax b doesn’t intersect a square if either it is above the square both at the left and the right side of the square or below the square at both sides of the square. This gives you a formula to calculate possible values of b depending on a. In your case with the square at 0, 0 to 1, 1 you need to avoid b where b<0 and a b <0, or b>1 and a b > 1. Then you add restrictions for the second square and so on. There may not be a solution.