Triangulationsalgorithmus

[Skript]

Hallo,

Ich suche verzweifelt ein in Delphi programmierter Algorithmus zur Triangulation eines Polygons mit Löchern... kann mir dabei jemand weiterhelfen? :roll:

Gruss & Dank

Skript

[atreju2oo0]

Ich nehme an für 3-D ???
Und sind die Löcher rund oder beliebiger Form?

[Skript]

Die Fläche ist immer eben, also 2D und die Löcher sind ebenfalls Polygone, also beliebige Formen.

[Robert Marquardt]

Ich weiss nur das Innen und Aussen bei einem nicht-konvexen Polygon schwer zu entscheiden ist.
Hast du einen Algorithmus gefunden? C umzuschreiben sollte nicht so schwer sein.

[Skript]

Ich habe erst einen ohne Löcher gefunden, aber einer mit ist, soviel ich gelesen habe, ziemlich anderst :(

[atreju2oo0]

Ich kann Dir zwar keinen Code geben, aber vielleicht hilft Dir das:


Also ich würde die Anzahl der äußeren Punkte mit der Anzahl der inneren Punkte vergleichen.
Die Differenz ist dann die Anzahl von Punkten die zwei Schnittgeraden bekommen(siehe Anhang).
Die Schnittgeraden teilst Du dann auf indem Du ein geeignetes Paar findest und davon ausgehend immer ein Punkt wanderst.
Bei jedem Paar das nicht eine Doppelverbindung hat musst Du zusätzlich noch eine Schnittggerade zu dem davorgehenden Punkt machen, da sonst ja ein Viereck entstehen würde.

Falls das jetzt zu undeutlich war, oder Du dir das schon selbst gedacht hast dann wars wenigstens ein Versuch wert...
:-D

[edit] Anhang vergessen [/edit]

[Skript]

Ohgott, das musste ich jetzt zuerst 10 mal lesen bevor ich es einigermassen begriffen hatte :-D Hmmm ich werde mich dann jetzt mal mathematisch etwas kullern und hirnen :gruebel:

Wenn noch jemand Interesse hat mitzudenken, ist er herzlich eingeladen :cheers:

[w3seek]

ftp://ftp.cs.unc.edu/pub/users/manoc...Triangulation/

ist allerdings in C geschrieben

[Skript]

Oh toll! Das versuch ich mit meinen bescheidenen C-Kenntnissen umzuschreiben :coder:

Bier verdient! :cheers:

[Skript]

Hallo,

Habe jetzt angefangen das Programm zu übersetzen, ich blieb jetzt aber doch an meinen beschränkten C++ Kenntnissen hängen, weil: In der Funktion geht es um eine Zufalls-Permutation, aber ich begreiffe nicht, was mit dem Int *p passiert, bzw. wie man das in Delphi deklarieren könnte? Zuerst ist es ein Pointer auf ein Integer und dann wird ihm ein Array übergeben? :gruebel:

Kann mir jemand helfen diese Funktion in Delphi umzuschreiben?


Globale Variablen:

Code:

static int choose_idx;
static int permute[SEGSIZE];

Diese Funktion:

Code:

/* Generate a random permutation of the segments 1..n */
int generate_random_ordering(n)
     int n;
{
  struct timeval tval;
  struct timezone tzone;
  register int i;
  int m, st[SEGSIZE], *p;
  
  choose_idx = 1;
  gettimeofday(&tval, &tzone);
  srand48(tval.tv_sec);

  for (i = 0; i <= n; i++)
    st[i] = i;

  p = st;
  for (i = 1; i <= n; i++, p++)
    {
      m = lrand48() % (n + 1 - i) + 1;
      permute[i] = p[m];
      if (m != 1)
   p[m] = p[1];
    }
  return 0;
}

[ripper8472]

Auf den code gebe ich keine Garantie, ich hab ich nicht mal getestet.
Was dich sicher gewundert hat, war die Sache mit dem int* (^integer), der plötzlich ein array bekommt. In C/++ gibt es etwas, was man Pointer-Array-Dualität nennt. Dem Compiler ist es egal, ob es ein pointer oder ein array ist. Das glaube ich umgangen zu haben. Ne Garantie kann ich dir nicht geben. Probier einfach mal aus, ob das Richtige rauskommt.

Delphi-Quellcode:

var
  choose_idx:integer;
  permute:array[0..SEGSIZE-1];

{ Generate a random permutation of the segments 1..n }
function generate_random_ordering(n:integer):integer;
var
   tval:TTimeval;// struct timeval tval;
  tzone:TTimezone; // struct timezone tzone;
  i:integer; // register int i;
  m:integer; // int m, st[SEGSIZE], *p;
  st:array [0..SEGSIZE-1] of integer;
  p:^integer;

begin
  choose_idx := 1;
  gettimeofday(@tval, @tzone);
  srand48(tval.tv_sec);

  for i := 0 to n do
     st[i] := i;

  for i:=1 to n do begin
     m:=lrand48() mod (n + 1 - i) + 1;
    permute[i] := st[i-1+m];
    if m <> 1 then st[i-1+m] := st[i];

  end;

  result:=0;
end;

gruß, Christoph

[Skript]

Danke schön :cyclops: ! Also du hast es umgangen, indem du den "p" gar nicht verwendest? Ohjeh, ich weiss schon, wieso ich kein C++ programmiere; wieso einfach wenn's kompliziert geht :-D Bevor ich es testen kann muss ich noch den Rest der Unit übersetzen, dann bin ich mal gespannt :coder:

[Skript]

Uhohjeh, noch eine C++ Frage: Bei folgendem Ausdruck wird bei der logischen Prüfung der Variable "tnext" ein Wert übergeben (tnext = ...), welcher später im Code wieder verwendet wird. Da ich diese Zuweisung im Delphi ja vorher und nicht gleichzeitig machen muss, interessier mich jetzt, welchen Wert die Variable "tnext" am Ende dieser C++ Zuweisung trägt? Gilt da tnext = tr[t].d0 oder tnext = tr[t].d1 ?

Code:

cond = ((((tnext = tr[t].d0) > 0) && (tr[tnext].rseg == segnum)) ||
        (((tnext = tr[t].d1) > 0) && (tr[tnext].rseg == segnum)));

if tnext == ...

Bin schon fast durch und kann wohl nachher besser C++ als Delphi :-D

Gruss Skript

[ripper8472]

Hi!

Also die Anweisung ist echt grausam.
Zur Verständlichkeit etwas C:

Code:

  a = 3;
  b = 10;
  c = (a = b);

a ist jetzt 10, weil ich der Variable den Wert von b zugewiesen hab. Das Ergebnis dieser Zuweisung ist dann auch der Wert, den ich a zugewiesen hab. c ist jetzt also auch 10.


C hat außerdem das Sprachmerkmal, boolesche Ausdrücke nicht vollständig auswerten zu müssen. Wenn ich z.B. (1 || something()) auswerte, dann wird die funktion something() garnicht ausgeführt, weil das Ergebnis sowieso Eins sein muss.

Also mal wieder aus dem Handgelenk:

Delphi-Quellcode:

tnext := tr[t].d0;
cond := (tnext > 0) and (tr[tnext].rseg = segnum); //vorausgesetzt, segnum ist keine funktion

if not cond then begin
  tnext := tr[t].d1;
  cond := (tnext > 0) and (tr[tnext].rseg = segnum);
end;

Ich denke, das dürfte es sein.


Gruß, Christoph