Koordinaten des umschließenden Rechtecks aller vorhandenen Punkte in einem 2D Punktdiagramm

Neue Frage »

nd1012 Auf diesen Beitrag antworten »
Koordinaten des umschließenden Rechtecks aller vorhandenen Punkte in einem 2D Punktdiagramm
Meine Frage:
Hi,

ich hoffe mal, dass ich in die richtige Kategorie poste: Im Prinzip suche ich eine möglichst effiziente Formel/Funktion, um die Koordinaten eines Rechtecks (grün) in einem Punktdiagramm zu finden, dass genau alle Punkte (rot) umschließt (Beispiel-Diagramm anbei). Im Beispiel könnten die Wochentage auch durch die Zahlen 1-7 ersetzt werden, wobei die Formel/Funktion aber generell auf Diagramme mit unterschiedlichsten numerischen X/Y Achsen verwendet werden können soll.

Bekannt ist der Bereich von X und Y. Es kann durchaus sein, dass am minimalen oder maximalen Wert von X oder Y kein Punkt liegt, das Rechteck sich also irgendwo mitten im Diagramm befindet.

Die Funktion Diagramm(x, y) ergibt 0 (=kein Punkt) oder 1 (=Punkt). Das Diagramm selbst stellt mir also bereits eine Funktion (bzw. eine mehrdimensionale Liste) zur Verfügung, die mir mitteilt, ob sich an den angegebenen X/Y Koordinaten ein Punkt befindet.

Meine Mathe-Kenntnisse sind leider etwas begrenzt, und ich habe keine Ahnung, nach welchen Themen ich namentlich suchen sollte, um das Problem zu lösen. Aber vielleicht kann mir jemand hier zum Beispiel mit Pseudocode oder einem Tipp für ein Mathe-Thema, mit dem ich mich mal befassen sollte, weiterhelfen!?

LG
nd

Meine Ideen:
Natürlich könnte ich das Raster Punkt für Punkt komplett durchgehen, und dabei die Koordinaten des Rechtecks in Variablen immer erweitern, sobald ein Punkt gefunden wurde, der außerhalb des bisherigen Rechtecks liegt. Wenn ich aber beispielsweise ein sehr großes Raster habe, in dem das Rechteck insgesamt nur sagen wir mal 2% ausfüllt, wäre dieses Vorgehen äußerst uneffizient:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
xMin = 1;// Minimaler Wert der X-Achse
xMax = 7;// Maximaler Wert der X-Achse
yMin = 0;// Mininaler Wert der Y-Achse
yMax = 45;// Maximaler Wert der Y-Achse
x1 = xMax + 1;// X-Wert des Rechtecks oben links
x2 = xMin - 1;// X-Wert des Rechtecks unten rechts
y1 = yMax + 1;// Y-Wert des Rechtecks oben links
y2 = yMin - 1;// Y-Wert des Rechtecks unten rechts
for y = yMin, y <= yMax, y = y + 1 do
  for x = xMin, x <= xMax, x = x + 1 do
    if Diagramm(x,y) == 1 then
      if x < x1 then x1 = x endif;
      if x > x2 then x2 = x endif;
      if y < y1 then y1 = y endif;
      if y > y2 then y2 = y endif;
    endif;
  next x;
next y;


Das funktioniert sicher, aber ich könnte mir vorstellen, dass es wesentlich bessere Methoden gibt, um die Koordinaten des Rechtecks zu finden, oder etwa nicht?
frank09 Auf diesen Beitrag antworten »
RE: Koordinaten des umschließenden Rechtecks aller vorhandenen Punkte in einem 2D Punktdiagramm
Besteht die Möglichkeit, direkt auf die Koordinaten der Punkte zuzugreifen, bzw. wie sind sie gespeichert? Was ich nicht verstehe, warum gehst du nicht von außen nach innen? Du fährst mit der oberen waagerechten Begrenzung von der max. Y-Koordinate solange über die ganze Breite nach unten bis ein Punkt auftaucht. Dann führst du die linke und die rechte senkrechte Rechteckseite solange zusammen bis rechts oder links ein Punkt angezeigt wird, um dann nur noch die andere Seite nach innen zu führen bis der dritte Punkt feststeht.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »