Finden Sie den Schnittpunkt zwischen LIne und Grid in einer schnellen Art und Weise
Gibt es überhaupt eine Möglichkeit, alle Schnittpunkte zwischen einer Linie und einem Gitter zu finden? (Die Schnittpunkte sind nicht maßstabsgetreu gezeichnet, weiß ich)
Ein Brute-Force-Verfahren besteht darin, einen Schnittpunkt für das x-y -Gitter mit der Linie zu berechnen, aber dieser Algorithmus ist sehr ineffizient ( O(m*n) , wobei m die Anzahl von x grid und n ist) die Anzahl von y grid).
Ich suche nach einem besseren Algorithmus dafür.
3 Antworten
Klingt so, als ob Sie einen Digital Differential Analyzer oder Bresenhams Linienalgorithmus . 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.
Ich bin mir nicht sicher, ob ich die Frage wirklich verstehe. Ist das, wonach Sie suchen?
Wenn das Gitter auf die Achse ausgerichtet ist:
- finde die Liniengleichung
- Berechnen Sie die Schnittpunkte direkt mit dem Gitter Linie x oder y als feste Variable
Wenn das Gitter 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.