Trova l’intersezione tra luce e griglia in un modo rapido

C’è comunque che mi permetta di trovare tutti i punti di intersezione tra una linea e una griglia? (I cerchi intersezione non sono disegnati in scala l’uno con l’altro, lo so)

Un metodo a forza bruta consiste nel calcolare molto l’intersezione per la griglia xy con la linea, ma questo algoritmo è terribilmente inefficiente ( O(m*n) , dove m è il numero di x griglia n è il numero di y griglia).

Sto cercando un algoritmo migliore su questo.

Sembra che tu abbia bisogno di un analizzatore digitale differenziale o dell’algoritmo di linea di Bresenham . Bresenham è lo stesso algoritmo utilizzato per tracciare linee su una bitmap; in questo caso, colorare un pixel equivale a controllare le collisioni in quel quadrato.

Non sono sicuro di capire davvero la domanda. È questo che stai cercando per caso?

Illustrazione 1 http://sofit.miximages.com/c%23/mwwg37.png

Illustrazione 2 http://sofit.miximages.com/c%23/657uc1.png

Se la griglia è allineata sull’asse:

  1. scopri l’equazione della linea
  2. calcola direttamente i punti di intersezione usando la x o y della linea della griglia come variabile fissa

Se la griglia è regolare, la distanza tra le intersezioni con ciascuna linea orizzontale sarà la stessa. Lo stesso vale anche per le linee verticali. In questo caso potresti semplicemente eseguire un semplice algoritmo iterativo con dx e dy.