Überprüfen einer Linie durch ein 2D-Array

Question

Ich habe ein 2D boolean Array (ein boolean[][]), und ich habe zwei Punkte ((x, y)). Ich möchte eine Linie zwischen diesen beiden Punkten zeichnen und sehen, ob die Linie jeden Raum schneidet, der einen true Wert hat.

Zur Verdeutlichung stellen Sie sich vor, dass jedes Element 1 unit x 1 unit ist. Die boolean[][] wird immer rechteckig sein. Ich streame von den Zentren der angegebenen Punkte.

Ich weiß nicht wirklich, wo ich anfangen soll, einige Ratschläge würden mir gefallen.

Answer 1

Wenn ich Ihre Frage richtig verstanden habe, klingt es so, als wollten Sie einfach berechnen, welche Binärpunkte in Ihrem Raster von der Linie betroffen sind. Für die längste Zeit haben Computer Bresenham's line algorithm verwendet. Es wurde in späteren Jahren angepasst, um Anti-Aliasing zu verwenden. Da es sich um einfache Ein/Aus-Bits handelt, können Sie den einfachen Algorithmus verwenden. Die Verbindung hat viel mehr von der Theorie und einige Anpassungen des Algorithmus für andere Linienprobleme.

Der Pseudo-Code wird wie etwa wie folgt aussehen:

deltaX = p1.X - p0.X 
deltaY = p1.Y - p0.Y 
error = -1.0 

# NOTE: assuming deltaX is not 0 (vertical) 
slope = Abs(deltaY/deltaX) 
y = p0.Y 

for(x = p0.X; x < p1.X; x++) 
{ 
    check(x,y) # plot/check, this is the point of interest 

    error += slope 
    if(error >= 0.0) 
    { 
     y += 1 
     error -= 1 
    } 
} 

Ein paar Anmerkungen:

• Alles, was nicht notwendig Punktzahlen koordinieren ist schwimmend (einschließlich deltaX und deltaY)
• p0 und p1 sind Punkte (x, y) und kann ganze Zahlen