Wie erhält man die Länge eines Segments, das ein Quadrat kreuzt?

Question

Ich habe eine Linie, definiert durch die Parameter m, h, wo

y = m*x + h 

Diese Linie über einem Gitter geht (d.h. Pixel). Für jedes Quadrat (a, b) des Gitters (dh das Quadrat [a, a+1] x [b, b+1]) möchte ich bestimmen, ob die gegebene Linie dieses Quadrat kreuzt oder nicht, und wenn ja, wie groß ist die Länge des Segments im Quadrat.

Schließlich würde ich gerne in der Lage sein, dies mit mehreren Zeilen auf einmal zu tun (dh m und h sind Vektoren, Matlab-Stil), aber wir können uns auf den "einfachen" Fall für jetzt konzentrieren.

Ich stellte dar, wie, um zu bestimmen, ob die Zeile den Platz überquert:

1. Compute den Schnittpunkt der Linie mit den vertikalen Linien x = a und x = a + 1 und die horizontalen Linien y = b und y = b + 1
2. Prüfen, ob 2 Diese 4 Punkte auf dem Platz Grenzen sind (dh a <= x < a + 1 und b <= y < b + 1)

Wenn zwei auf diese Punkte auf dem Platz sind, wird die Linie C wirft es um. Dann, um die Länge zu berechnen, subtrahieren Sie einfach die zwei Punkte und verwenden Pythagoras Theorem.

Mein Problem ist mehr auf der Implementationsseite: wie kann ich das schön implementieren (besonders wenn man auswählt, welche 2 Punkte subtrahiert werden)?

Answer 1

Das Quadrat wird durch Eckpunkte definiert (a, b), (a + 1, b), (a, b + 1), (a + 1, b + 1).

Schritt 1: Überprüfen, ob die Zeile den Platz schneidet ...

(a) jede der Koordinaten der 4 Eckpunkte ersatz, wiederum in y - mx - h. Wenn das Vorzeichen dieser Auswertung sowohl positive als auch negative Terme enthält, fahren Sie mit Schritt b fort. Andernfalls schneidet die Linie das Quadrat nicht.

(b) nun zwei Unterfälle gibt es:

(b1) Fall 1: In Schritt (a) Sie drei Punkte hatten, für die y - mx - h ein Zeichen ausgewertet und vierten Punkt zum anderen Zeichen ausgewertet. Dieser vierte Punkt sei etwa (x *, y *). Dann sind die Schnittpunkte (x *, mx * + h) und ((y * -h)/m, y *).

(b2) Fall 2: In Schritt (a) hatten Sie zwei Punkte, für die y - mx - h zu einem Zeichen auswerten und die anderen beiden Punkte zum anderen Zeichen ausgewertet werden. Wählen Sie zwei beliebige Punkte aus, die auf dasselbe Vorzeichen ausgewertet wurden, z. B. (x *, y *) und (x * + 1, y *). Dann sind die Schnittpunkte (x *, mx * + h) und (x * + 1, m (x * + 1) + h).

Sie müssten einige entartete Fälle betrachten, in denen die Linie genau einen der vier Eckpunkte berührt, und der Fall, in dem die Linie genau auf einer Seite des Quadrats liegt.

Answer 2

Ihre vorgeschlagene Methode kann in Schritt (1) Probleme verursachen, wenn m 0 ist (wenn Sie versuchen, die Kreuzung mit y = k zu berechnen). Wenn m 0 ist, dann ist es einfach (die Liniensegmentlänge ist entweder 1 oder 0, abhängig davon, ob b <= h <= b+1).

Ansonsten können Sie die Kreuzungen mit x = a und a+1 finden, sagen wir, y_a, y_{a+1} über eine Substitution. Dann Clip y_a und y_{a+1} zwischen b und b+1 (sagen wir, y1 und y2, d.h. y1 = min(b+1, max(b, y_a)) und ähnlich für y2), und verwenden den Anteil abs((y1-y2)/m) * sqrt(m^2+1).

Dies macht sich die Tatsache zunutze, dass das Liniensegment zwischen x=k und x=k+1sqrt(m^2+1) ist, und der Unterschied in ym ist, und Ähnlichkeit.

Answer 3

Sie können so tun: zuerst finden Zentrum des Quadrats und dann finden Länge der Diagonale. Wenn die Entfernung von der Mitte des Quadrats zur Linie kleiner ist als die Länge der Diagonalen, schneidet die Linie das Quadrat. Sobald Sie wissen, dass sich die Linie überschneidet, können Sie das geschnittene Liniensegment leicht finden. Ich denke, Sie versuchen, eine Gewichtsmatrix für die algebraische Rekonstruktionstechnik zu erstellen. Ich hoffe, das ist die richtige Antwort. Dies war meine erste Antwort im Stapelfluss. :)