2010-07-17 3 views
8

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ß)Den Schnittpunkt zwischen Linie und Gitter in einer schnellen Art und Weise finden

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.

+2

Soll das Raster regelmäßig sein? –

+0

@Ignacio, ja das Raster ist regulär. – Graviton

Antwort

6

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.

+0

Ich glaube, das sollte die akzeptierte Antwort sein. Mit einem Algorithmus wie dem von Bresenham werden die Gitterpunkte überprüft, und von dort aus können einzelne Schnittpunkte viel einfacher berechnet werden. Die horizontalen und vertikalen Komponenten sind alle bekannt. –

6

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

+0

Ich möchte jeden einzelnen Schnittpunkt zwischen der roten Linie und der Gitterlinie. Also sind die Punkte '(0, b)', '((hb)/m, h)', '(w, mw + b)', '(2w, 2wm + b)', '((2h- b)/m, 2h) ',' (3w, 3wm + b) 'und so weiter – Graviton

+0

Was fehlt also? – dtb

+0

@ dtb, nichts fehlt. Aber ich will einen effizienten Algorithmus dafür – Graviton

0

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.

Verwandte Themen