Den Schnittpunkt zwischen Linie und Gitter in einer schnellen Art und Weise finden

Question

Gibt es trotzdem, dass ich alle Schnittpunkte zwischen einer Linie und einem Gitter finden kann? (Die Schnittkreise sind nicht gezeichnet miteinander zu skalieren, ich weiß)

Ein Brute-Force-Weg ist sehr Kreuzung für die x-y Raster mit der Linie zu berechnen, aber dieser Algorithmus ist schrecklich ineffizient (O(m*n) , wobei m die Nummer x Raster und n die Nummer y Raster ist).

Ich bin auf der Suche nach einem besseren Algorithmus dafür.

Answer 1

Klingt, als ob Sie eine Digital Differential Analyzer oder Bresenham's line algorithm benötigen. Bresenham ist derselbe Algorithmus, der verwendet wird, um Linien auf einer Bitmap zu zeichnen; In diesem Fall entspricht das Einfärben eines Pixels der Überprüfung auf Kollisionen in diesem Quadrat.

Answer 2

Ich bin mir nicht sicher, ob ich die Frage wirklich verstehe. Ist das, wonach du suchst, zufällig?

Illustration 1 http://i31.tinypic.com/mwwg37.png

Illustration 2 http://i27.tinypic.com/657uc1.png

Answer 3

Wenn die Gitterachse ausgerichtet ist:

1. die Geradengleichung
2. berechnet die Schnittpunkte herauszufinden direkt entweder die Gitter Linie x oder y unter Verwendung von als feste Variable

Wenn das Raster regelmäßig ist, ist der Abstand zwischen den Schnittpunkten mit jeder horizontalen Linie gleich. Das Gleiche gilt auch für die vertikalen Linien. Sie könnten einfach einen einfachen iterativen Algorithmus mit dx und dy in diesem Fall machen.