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;
}