以快速方式找到線和網格之間的交點

有沒有辦法讓我找到線和網格之間的所有交點？（交點圓未按彼此按比例繪製，我知道）以快速方式找到線和網格之間的交點

蠻力方法是計算非常交點爲x-y網格線，但該算法是非常低效的（O(m*n) ，其中m的網格數是x而n的網格數是y）。

我正在尋找一個更好的算法。

2010-07-17 Graviton

電網應該是正常的嗎？ – 2010-07-17 08:47:27

@Ignacio，是的，網格是經常的。 – Graviton 2010-07-17 09:13:00

聽起來像你需要一個Digital Differential Analyzer或Bresenham's line algorithm。 Bresenham與用於在位圖上繪製線條的算法相同;在這種情況下，着色像素等同於檢查該方塊中的碰撞。

2010-07-17 10:48:34 celion

我相信這應該是被接受的答案。使用像Bresenham's這樣的算法可以檢查網格點，然後可以更容易地計算出各個交點 - 水平和垂直分量都是已知的。 – 2014-06-27 15:30:02

我不確定我真的明白這個問題。這是你想要的任何機會嗎？

2010-07-17 11:15:30 dtb

我想要紅線和網格線之間的每個交點。所以，這些點是'（0，b）'，'（（hb）/ m，h）'，'（w，mw + b）'，'（2w，2wm + b）'，'（（2h- b）/ m，2h）'，'（3w，3wm + b）'等 – Graviton 2010-07-17 11:22:17

那麼缺什麼？ – dtb 2010-07-17 11:25:11

@dtb，沒有缺失。但我想要一個高效的算法 – Graviton 2010-07-17 11:42:32

如果網格軸線對齊：

如果網格是規則的，與每條水平線的交點之間的距離將是相同的。垂直線也是如此。在這種情況下，你可以用dx和dy做一個簡單的迭代算法。

2010-07-17 11:30:48 jackrabbit

回答