herausfinden, ob ein Quadrat auf einer Strecke ist

Der Knirps

hmmm...
Klingt gut...
Aber wie überprüft man, ob die Strecken sich schneiden?
Mir fällt jetzt auf Anhieb nichts ein.

Jester

volkard schrieb:

ich schätze, du solltest die strecke nacheinander mit den vier quadratseiten (sind auch strecken) schneiden. gibts einen schnittpunkt, liegt auch was von der strecke innerhalb.

Wenn beide Streckenndpunkte innerhalb des Quadrats liegen haben Quadrat und Strecke auch Punkte gemeinsam. Vielleicht könnte man vorher abfragen, ob einer der Punkte im Quadrat drinliegt.

MfG Jester

volkard

Der Knirps schrieb:

Ich habe:
ein Quadrat, dessen Seiten parallel zur x- bzw zur y-Achse sind. Ich kenne die Seitenlängen und die Koórdinaten einer Ecke
eine Strecke, von der ich die Koordinaten beider Endpunkte kenne.

vielleicht hilft das hier:
http://www.iam.unibe.ch/~fcglib/special_www/cg_lecture/lectContent/clipping/intro/line_clipping_intro/line_clipping_intro.php

MG80S

Das liesse sich doch relativ einfach über Vektoren lösen:

Die Strecke kann ja per P(x;y) = P₀ + t * a angegeben werden (a ist Richtungsvektor).
Damit ist x = x₀ + t * a_x
und y = y₀ + t * a_y

Also muss gelten: (y-y₀)/a_y = (x-x₀)/a_x

Damit hast Du schonmal raus, ob ein Punkt P(x;y) auf der Geraden liegt. Jetzt noch schauen, ob x zwischen den x-Werten der Punkte der Strecke liegt und das wars.
Zum Programm dazu habe ich gerade keine Lust, sind ja nur zwei if's mit bissel drumherum.

Jester

@MG80S: und das jetzt für alle Punkte im Quadrat? Das wird sicher enorm schnell!

MG80S

Nagut, dann anders. Wie wärs, wenn man alle Punkte der Strecke von x=xboxmin bis xboxmax durchgeht (wenn existent) und schaut, ob sie zwischen yboxmin und yboxmax liegen?

PS: Dachte es geht um einen beliebigen Punkt, nicht alle.

volkard

ich will zuerst mal schauen, wie ich es hinkriege, zu sehen, ob die strecke eine der senkrechten quadratseiten schneidet.

die strecke verlaufe von punkt a zu punkt b.
a bestehe aus ax und ay.
b bestehe aus bx und by.

die quadratseite sei bei x und verlaufe von oben nach unten von yo bis yu.
mit "oben" meine ich größere y-werte.

außerdem will ich, daß ax<=bx ist.

gesucht ist

bool schneidet(int ax,int ay,int bx,int by,int x,int yo,int yu);

hilffunktion

funktion bool range(int min,int x,int max){
   return min<=x && x<=max;
}

interessant ist es nur, wenn x zwischen ax und bx liegt

bool schneidet(int ax,int ay,int bx,int by,int x,int yo,int yu){
   if(!range(ax,x,bx)) return false;
   ...
}

jetzt könnte es noch sein, daß ax==bx, also daß die strecke zufällig senkrecht verläuft. und nach dem vortest ist auch sicher, daß wenn ax==bx, dann ax==x und x==bx. in diesem fall muss nur getestet werden, ob ay oder ab zwischen yo und yu liegen.

bool schneidet(int ax,int ay,int bx,int by,int x,int yo,int yu){
   if(!range(ax,x,bx)) return false;
   if(ax==bx){
      if(range(yu,ay,yo)) return true;
      if(range(yu,by,yo)) return true;
      return false;
   }
   ...
}

so, jetzt würde mich interessieren, an welcher stelle die gerade, auf der ste strecke liegt die gerade schneidet, auf der die quadratseite liegt.
oder anders: die strecke läuft von ax nach bx und steigt dabei von ay nach by. irgendwo dazwischen erreicht sie x und welches y hat sie da?
klingt nach dreisatzaufgabe.

by-ay    by-y
----- == ----
bx-ax    bx-x

das müßte ich mal nach y auflösen.

(by-ay)*(bx-x)    
-------------- == by-y
     bx-ax    

       (by-ay)*(bx-x)    
y=by - --------------
          bx-ax

oder in c++:

y=by-(by-ay)*(bx-x)/bx-ax;

vielleicht ließe sich das noch vereinfachen, aber ich riskiere nix und will nur erstmal, daß es läuft.

wenn dieses y dann zwischen yu und yo liegt, schneidet die strecke die quadratseite und anderenfalls tut sie es nicht.

bool schneidet(int ax,int ay,int bx,int by,int x,int yo,int yu){
   if(!range(ax,x,bx)) return false;
   if(ax==bx){
      if(range(yu,ay,yo)) return true;
      if(range(yu,by,yo)) return true;
      return false;
   }
   int y==by-(by-ay)*(bx-x)/bx-ax;
   return range(yu,y,yo);
}

und jetzt mal die ganze funktion wagen. das quadrat sei gegeben durch links, oben, rechts, unten.

bool schneidet(int ax,int ay,int bx,int by,int links,int oben,int rechts,int unten){
   //erstmal sicherstellen, daß ax<=bx
   if(ax>bx){
      swap(ax,bx);
      swap(ay,by);
   }
   //linke seite testen
   if(schneidet(ax,ay,bx,by,links,oben,unten)) return true;
   //rechte seite testen
   if(schneidet(ax,ay,bx,by,links,oben,unten)) return true;
   ...
}

mhmm. und jetzt müßte ich uben und unten testen. und zwar mit einer neuen funktion, die waagerechte quadratseiten kann. da helfe ich mir mit einem trick, ich spiegle an der winkelhalbierenden (und das geht technisch, indem ich alle x-werte und y-werte vertausche).

bool schneidet(int ax,int ay,int bx,int by,int links,int oben,int rechts,int unten){
   //erstmal sicherstellen, daß ax<=bx
   if(ax>bx){
      swap(ax,bx);
      swap(ay,by);
   }
   //linke seite testen
   if(schneidet(ax,ay,bx,by,links,oben,unten)) return true;
   //rechte seite testen
   if(schneidet(ax,ay,bx,by,links,oben,unten)) return true;

   //erstmal sicherstellen, daß ay<=by
   if(ay>by){
      swap(ax,bx);
      swap(ay,by);
   }
   //untere seite testen
   if(schneidet(ay,ax,by,bx,unten,links,rechts)) return false;
   //obere seite testen
   if(schneidet(ay,ax,by,bx,oben,links,rechts)) return false;
   //fein, die strecke hat gar keine quadratseite geschnitten. also liegt die strecke
   //komplett ausserhalb oder komplett innerhalb. ich teste das komplett-innerhalb-liegen 
   //vielleicht am besten mal am anfang.
}

bool innerhalb(int px,int px,int links,int oben,int rechts,int unten){
if(!range(links,px,rechts)) return false;
if(!range(unten,py,oben)) return false;
return true;
}
bool schneidet(int ax,int ay,int bx,int by,int links,int oben,int rechts,int unten){
if(innerhalb(ax,ay,links,oben,rechts,unten)) return true;
if(innerhalb(bx,by,links,oben,rechts,unten)) return true;
//erstmal sicherstellen, daß ax<=bx
if(ax>bx){
swap(ax,bx);
swap(ay,by);
}
//linke seite testen
if(schneidet(ax,ay,bx,by,links,oben,unten)) return true;
//rechte seite testen
if(schneidet(ax,ay,bx,by,links,oben,unten)) return true;

//erstmal sicherstellen, daß ay<=by
if(ay>by){
swap(ax,bx);
swap(ay,by);
}
//untere seite testen
if(schneidet(ay,ax,by,bx,unten,links,rechts)) return true;
//obere seite testen
if(schneidet(ay,ax,by,bx,oben,links,rechts)) return true;
//fein, die strecke hat gar keine quadratseite geschnitten. und die endpunkte
//der strecke liegen ausserhalb.
return false;
}
[/cpp]

alles ungestestet und nur mal so hingeschrieben. also geh nicht davon aus, daß der code funktioniert, ist nur als hinweis zu verstehen, wie es klappen könnte.

Jester

MG80S schrieb:

Nagut, dann anders. Wie wärs, wenn man alle Punkte der Strecke von x=xboxmin bis xboxmax durchgeht (wenn existent) und schaut, ob sie zwischen yboxmin und yboxmax liegen?

PS: Dachte es geht um einen beliebigen Punkt, nicht alle.

Du kannst diese Punkte nicht alle durchgehen, weil es unendlich viele sind. (mathematisch gesehen) Und selbst auf dem Rechner könnten das schon mal ein paar Millionen werden. Es steht nirgendwo was davon, daß es sich hier um Pixel handelt!

Es geht schon um einen beliebigen Punkte. Nämlich ja sagen, falls ein beliebiger Punkt der Strecke im Quadrat ist und nein sonst... nur sagt niemand welcher der Punkt ist, es kommen also alle in Frage.

MfG Jester

guyondrugs

volkard schrieb:

(by-ay)*(bx-x)    
y=by - --------------
          bx-ax

oder in c++:

y=by-(by-ay)*(bx-x)/bx-ax;

Fehlt da nich ne Klammer?

y=by-(by-ay)*(bx-x)/(bx-ax);

</klugscheiß>

volkard

guyondrugs schrieb:

Fehlt da nich ne Klammer?

jup, fehlt.
schlimmer wird evtl das prublem mit den rundungsfehler werden, und man darf nicht

int y==by-(by-ay)*(bx-x)/(bx-ax);
return range(yu,y,yo);

schreiben, sondern

return range(yu*(bx-ax),by-(by-ay)*(bx-x),yo*(bx-ax));

ka, muss man sehen. und dann natürlich wieder lange überlegen, ob man das nicht einfach machen kann.

MG80S

Jester schrieb:

Du kannst diese Punkte nicht alle durchgehen, weil es unendlich viele sind. (mathematisch gesehen) Und selbst auf dem Rechner könnten das schon mal ein paar Millionen werden. Es steht nirgendwo was davon, daß es sich hier um Pixel handelt!

Es geht schon um einen beliebigen Punkte. Nämlich ja sagen, falls ein beliebiger Punkt der Strecke im Quadrat ist und nein sonst... nur sagt niemand welcher der Punkt ist, es kommen also alle in Frage.

MfG Jester

Okay, I'm sorry. Hatte das Problem wohl zu speziell gesehen. Und ich hatte mich schon gewundert warum ihr hier mit Monster-Lösungsvorschlägen kommt, wo's doch auch so einfach geht (mal abgesehen von der Optimierung).....okay, dann viel Spaß noch.