Zwei Vier-Ecke subtrahieren

[JayZ]

hallo freunde

ich habe eine struktur die so ähnlich ist wie TRect einfach nur mit weniger funktionen:

Delphi-Quellcode:

TViereck = record
  x, y, width, height : integer;
  function getX2() : integer; // rechnet x + width
  function getY2() : integer; // rechnet y + height
end;

function Viereck(x,y,width,height:integer);
begin
  Result.x := x;
  Result.y := y;
  Result.width := width;
  Result.height := height;
end;

ich habe auch eine funktion die die intersection von 2 vier-ecken zurückgibt:

Delphi-Quellcode:

function RectIntersection(a, b : TViereck) : TViereck;
begin
  Result := Viereck(max(a.x, b.x)),
                    max(a.y, b.y),
          min(a.x2(), b.x2()),
          min(a.y2(), b.y2()));
  result.width -= result.x;
  result.height -= result.y;
end;

Nun überelge ich schon seit stunden wie ich die 2 vierecke subtrahieren kann also das eine vom anderen abziehen könnte... ich weiss das je nach welche vierecke da benutzz werden auch mehrere als nur ein viereck zurückgegeben wird aber ich komme nicht drauf wie ich das machen soll.... ich habe schon einiges versucht aber habe nur sachen rausbekommen die gar keinen sinn ergeben und ich verzweifle schon fast... habe meinen vater schon gefragt aber er ist kein informatiker oder programmierer und weiss leider auch nicht wie man das lösen soll =(

könnte mir einer helfen? wäre sehr dankbar für alles, brauche nicht unbedingt eine fertige code lösung einfach jemanden der mein verwurstet gehirn auf die sprünge hilft =)

danke und einen guten abend noch! =D

edit:
habe ein erkerungsbild eingefügt

[stahli]

Schau mal unter dem Stichwort "CreateRectRgn" bzw. "CreatePolygonRgn", ob Dir das irgendwie weiter hilft...

[Zacherl]

Darf man fragen, für was du das Ergebnis am Ende benutzen willst? Geht es zufällig auch hier um Clipping bzw. Hit-Tests? Mich macht etwas stutzig, dass du dir - laut deinem Beispielbild - ggfls. mehrere Rechtecke wünschst und nicht ein einzelnes Polygon.

[jfheins]

Sagen wir, du machst A minus B. Und es existiert mindestens ein Punkt von B innerhalb A (Alles andere vorher abfangen)

Dieser Punkt wird in der Form eine konkave Ecke bilden. (Also eine Ecke "nach innen") und muss ein neues Rechteck erzeugen. Hierzu kannst du einfach eine der beiden Richtungen nach innen wählen, und entlang dieser Richtung das Rechteck teilen.

Nun bleibt zu prüfen, ob eines der verbleibenden Rechtecke einen (anderen) Punkt von A enthält. Da sich der vorige Punkt auf dem Ranf befindet, darf er nicht nochmals gefunden werden.

Sobald es komplexer wird, würde ich dir diese ausgezeichnete Stack-Overflow Antwort ans Herz legen: http://stackoverflow.com/a/6634668/1974021
Dort wir eine Form in möglichst viele Rechtecke zerteilt, wenn du deine Differenz als Polygon definierst, würde das direkt zutreffen.

[bernau]

Laut Grafik brauchst du als Ergebnis drei Vierecke. Dein Funktionsresult ist aber TViereck, welches ja nur ein Viereck abbildet.

Auch wenn das Ergebnis ein Viereck mit der Einbuchtung wäre, kannst du das ja garnicht in TViereck abbilden.

[Blup]

Zitat:

Zitat von JayZ (Beitrag 1362283)

ich habe eine struktur die so ähnlich ist wie TRect einfach nur mit weniger funktionen:

Warum das Rad neu erfinden, die Datenmenge bzw. Speicherplatz wird durch weniger Methoden gegenüber TRect nicht geringer?

Die Aufgabe lässt sich verallgemeinern, in dem man A in 8 Vierecke zerlegt (bzw. 9 mit B).
Je nach relativer Position von B, sind die einzelnen Vierecke vorhanden oder auch nicht.

Code:

*-----*-----*-----*
|     |     |     |
|  A1 |  A2 |  A3 |
|     |     |     |
*-----*-----*-----*
|     |     |     |
|  A4 |  B' |  A5 |
|     |     |     |
*-----*-----*-----*
|     |     |     |
|  A6 |  A7 |  A8 |
|     |     |     |
*-----*-----*-----*

Zum Schluss kann man die entstandenen Vierecke wieder zusammenfassen.
Als Ergebnis der Zusammenfassung können 0 bis 4 Vierecke enstehen.

[JayZ]

danke euch allen habs endlich hinbekommen auch wenns mehr ein if-gewurstel ist was ich eigentlich nicht ganz wollte aber mache dad noch basser also dann zeige ich das villeicht auch wenns mal beser aussieht hihi

das projekt ist für einen mikrocontroller zum effizenten zeichnen auf einem bildschirm, deswegen auch keine polygons.

Zitat:

Zitat von Zacherl (Beitrag 1362286)

Darf man fragen, für was du das Ergebnis am Ende benutzen willst? Geht es zufällig auch hier um Clipping bzw. Hit-Tests? Mich macht etwas stutzig, dass du dir - laut deinem Beispielbild - ggfls. mehrere Rechtecke wünschst und nicht ein einzelnes Polygon.

Zitat:

Zitat von Blup (Beitrag 1362335)

Zitat:

Zitat von JayZ (Beitrag 1362283)

ich habe eine struktur die so ähnlich ist wie TRect einfach nur mit weniger funktionen:

Warum das Rad neu erfinden, die Datenmenge bzw. Speicherplatz wird durch weniger Methoden gegenüber TRect nicht geringer?
[/code]
Zum Schluss kann man die entstandenen Vierecke wieder zusammenfassen.
Als Ergebnis der Zusammenfassung können 0 bis 4 Vierecke enstehen.

weil ich dieses Rad leider nicht zur verfügung habe, und auch die restliche rtl nicht dadas ganze auf einem microcontroller läuft und schwer in 32kb zu packen ist also muss ich mir mein rad dafür selbst machen ;)

Zitat:

Zitat von zacher

Die Aufgabe lässt sich verallgemeinern, in dem man A in 8 Vierecke zerlegt (bzw. 9 mit B).
Je nach relativer Position von B, sind die einzelnen Vierecke vorhanden oder auch nicht.
[code]
*-----*-----*-----*
| | | |
| A1 | A2 | A3 |
| | | |
*-----*-----*-----*
| | | |
| A4 | B' | A5 |
| | | |
*-----*-----*-----*
| | | |
| A6 | A7 | A8 |
| | | |
*-----*-----*-----*

habe das nun nicht so gelöst klingt aber eigetnlich ganz gut. was wäre aber wenn B ausserhalb von A steht? sollte doch eigetnlich auch gehen wenn ich dann a imaginär erweitere oder?

danke euch nochmal =)

edited: ach ja eigetnlich ist der code in c++ aber uch finde delphi coder netter also frage ich lieber hier =) wenn jemand den hässligen c++ code will kann ich ihn ja posten hihi

Zitat:

Zitat von bernau (Beitrag 1362310)

Laut Grafik brauchst du als Ergebnis drei Vierecke. Dein Funktionsresult ist aber TViereck, welches ja nur ein Viereck abbildet.

Auch wenn das Ergebnis ein Viereck mit der Einbuchtung wäre, kannst du das ja garnicht in TViereck abbilden.

was mir durchaus bewusst =) habe ich geschrieben und auzch gar keine funktion gepostet die das zurückgeben soll nur eine funktion für die intersektion aber nicht differenz die ich ja haben wollte ;)

liebe grüsse!

[Blup]

Hab ein bischen Zeit gehabt und meine Idee umgesetzt und erfolgreich getestet.
Auf vordefinierte Funktionen wurde verzichtet, der Austausch von TRect durch eine eigene Klasse sollte also kein Problem sein.

Delphi-Quellcode:

unit MathRect;

interface

uses
  Types;

type
  TRectArray = array of TRect;

function Subtract(const R1, R2: TRect): TRectArray;

implementation

function Min(A, B: Integer): Integer;
begin
  if A < B then
    Result := A
  else
    Result := B;
end;

function Max(A, B: Integer): Integer;
begin
  if A > B then
    Result := A
  else
    Result := B;
end;

function IntersectRect(out Rect: TRect; const R1: TRect; const R2: TRect): Boolean;
begin
  Result :=
    (R2.Top < R1.Bottom) and (R1.Top < R2.Bottom) and
    (R2.Left < R1.Right) and (R1.Left < R2.Right);
  if Result then
  begin
    Rect.Top    := Max(R1.Top,    R2.Top);
    Rect.Left   := Max(R1.Left,   R2.Left);
    Rect.Bottom := Min(R1.Bottom, R2.Bottom);
    Rect.Right  := Min(R1.Right,  R2.Right);
  end;
end;

function IsRectEmpty(const Rect: TRect): Boolean;
begin
  Result := (Rect.Left >= Rect.Right) or (Rect.Top >= Rect.Bottom);
end;

procedure AddRect(var RectArr: TRectArray; const Rect: TRect);
var
  n: Integer;
begin
  if IsRectEmpty(Rect) then
    Exit;
  {anfügen}
  for n := 0 to High(RectArr) do
  begin
    {selbe Zeile}
    if (RectArr[n].Top = Rect.Top) and
       (RectArr[n].Bottom = Rect.Bottom) then
    begin
      {rechts}
      if RectArr[n].Right = Rect.Left then
      begin
        RectArr[n].Right := Rect.Right;
        Exit;
      end;
      {links - derzeit auf Grund der Reihenfolge nicht verwendet}
      if RectArr[n].Left = Rect.Right then
      begin
        RectArr[n].Left := Rect.Left;
        Exit;
      end;
    end;
    {selbe Spalte}
    if (RectArr[n].Left = Rect.Left) and
       (RectArr[n].Right = Rect.Right) then
    begin
      {unten}
      if RectArr[n].Bottom = Rect.Top then
      begin
        RectArr[n].Bottom := Rect.Bottom;
        Exit;
      end;
      {oben - derzeit auf Grund der Reihenfolge nicht verwendet}
      if RectArr[n].Top = Rect.Bottom then
      begin
        RectArr[n].Top := Rect.Top;
        Exit;
      end;
    end;
  end;
  {eigenständiges Recheck hinzufügen}
  n := Length(RectArr);
  SetLength(RectArr, n + 1);
  RectArr[n] := Rect;
end;

function Subtract(const R1, R2: TRect): TRectArray;
var
  A: array[0..2, 0..2] of TRect;
  B: TRect;
  x, y: Integer;
begin
  Result := nil;
  {Das tatsächliche Überschneidungsrechteck B ermitteln}
  if not IntersectRect(B, R1, R2) then
  begin
    {keine Überschneidung}
    AddRect(Result, R1);
    Exit;
  end;
  {Zeilen}
  for y := 0 to 2 do
  begin
    A[0, y].Left  := R1.Left;
    A[0, y].Right := B.Left;
    A[1, y].Left  := B.Left;
    A[1, y].Right := B.Right;
    A[2, y].Left  := B.Right;
    A[2, y].Right := R1.Right;
  end;
  {Spalten}
  for x := 0 to 2 do
  begin
    A[x, 0].Top    := R1.Top;
    A[x, 0].Bottom := B.Top;
    A[x, 1].Top    := B.Top;
    A[x, 1].Bottom := B.Bottom;
    A[x, 2].Top    := B.Bottom;
    A[x, 2].Bottom := R1.Bottom;
  end;
  {benachbarte Rechtecke zusammenfassen}
  for y := 0 to 2 do
    for x := 0 to 2 do
      if not ((y = 1) and (x = 1)) then
        AddRect(Result, A[x, y]);
end;

end.

[JayZ]

Ach sorry Blup ich hab das leider erst jetzt gesehen, ist ja nett das du dir die zeit dafür genommen hast :D Deine methode ist auch viel simpler und kürzer als das was ich gemacht habe (ist wie gesagt ein echtes if-gewrustel geworden weil mir keine mathematische methode eingefallen ist) werde sie wenn ich zeit habe einbauen und meine rauswerfen und kann somit wichtige bits und bytes einsparen hehe, vielen dank! =)

[Michael II]

Wenn man solche Dinge nicht neu erfinden will, dann helfen in Windows bereits eingebaute Funktionen wie CombineRgn.

CombineRgn function