1.
Benutzung der Funktion Pathfinder
2. Resultat der Funktion
3. Beispiel-Programm fuer Pathfinder
4. Fehler-Meldungen
long Pathfinder (int nP,
double *pdx, double *pdy,
double dMax ,double dyMax,
double dFar, double dFarRate,
int **ppiResults
)
Vorgaben :
nP : Anzahl der Punkte, Limit=MAXPOINTS (z.Z.=32000)
pdx,pdy : Pointer auf Arrays, die die x- bzw. y-Koordinaten der nP Punkte enthalten.
Die Punkte muessen nicht auf einem Gitter liegen, sondern koennen auch
einen "Sternenhimmel" bilden.
dMax : maximale Sprungweite
dyMax : Falls dyMax==0 , dann sind Spruenge innerhalb eines Umkreises
mit Radius dMax erlaubt.
Falls dyMax>0 , dann sind Spruenge innerhalb einer Ellipse mit
den Halbachsen dMax und dyMax erlaubt. dyMax=0 und dyMax=dMax liefern
dasselbe Resultat.
Falls dyMax<0, dann sind Spruenge innerhalb eines Rechteckecks
mit den Seitenlaengen 2*dMax und 2*(-dyMax) erlaubt.
dFar : siehe dFarRate
dFarRate: Falls dFarRate>0, werden nP*dFarRate "Ausnahme-Spruenge" zugelassen,
deren Sprungweite um dFar groesser sein darf als mit dMax und dyMax definiert
wurde. Vernuenftige Werte sind z.B dFar=1.5 , dFarRate=0.02
ppiResult : ist ein Pointer-Pointer auf ein Array, der das komplette Resultat
der Suche enthaelt (weitere Infos siehe unten).
Resultat der Funktion:
Der Funktionswert (int) selbst gibt die Laenge des *ppiResults - Array an.
Falls der Funktionswert negativ ist, lag ein Fehler vor und es konnte kein
Pfad gefunden werden (siehe Fehlermeldungen).
Format des Result-Arrays:
(*ppiResults)[ nn ] , nn = 0....Funktionswert-1
nn=0 : Anzahl der Pfade (im Idealfall=1, falls die Punkte so zerstreut sind,
dass sie nicht innerhalb der erlaubten Sprungweite verbunden werden
koennen, kann diese Zahl auch groesser sein).
Dieser Wert sei im Folgenden als nPath definiert.
nn=1..nPath : Laenge der nPath Pfade.
nn=nPath+1...2*nPath : Startadressen der Pfade im Result-Array
(siehe am Besten dazu das Beispiel)
nn=1+2*iPath+nP...2*iPath+nP: Indizes fuer die Zuordnung des gefundenen Weges.
Diese nP Indizes legen den(die) eigentlichen Weg(e) fest.
(siehe am Besten dazu das Beispiel)
Zusaezliche Ergebnisse, die nicht unbedingt benoetigt werden aber interessant sind:
nn=1+2*iPath+nP+0 : Anzahl der Cluster.
Die Cluster sind Punktmengen von Punkten,
die innerhalb der erlaubten Sprungweite zusammenliegen.
Die Cluster-Anzahl muss nicht unbedingt mit der Pfad-Anzahl
uebereinstimmen, im Normalfall ist es aber so. Groessere
Abweichungen deuten auf merkwuerdige Muster hin.
Dieser Wert hat keine entscheidende Bedeutung, ist aber
trotzdem interessant.
nn=1+2*iPath+nP+1 : diese Zahl gibt den mittleren Abstand aller Punkte zum
naechsten Nachbarn in Promille von dMax an (entspreache
z.B. der Gitterkonstanten bei einer Punktmenge mit einem
quadratischen Raster) . Diese Zahl spielt intern ein wichtige
Rolle.
nn=1+2*iPath+nP+2 : Anzahl der Punkte ohne Nachbarn (in der erlaubten Sprungweite)
nn=1+2*iPath+nP+3 : N1 (siehe unten)
nn=1+2*iPath+nP+4 : N2; N1*10000 + N2 ist die Anzahl der aller Verbindungen zwischen
den Punkten (mit erlaubter Sprungweite)
nn=1+2*iPath+nP+5 : Anzahl der Rekursions-Schritte fuer die Pfadsuche. Falls diese
Zahl gleich -1 ist, wurde MAXREKURSION erreicht und das Ergebnis
der Pfadsuche ist suboptimal.
nn=1+2*iPath+nP+6 : Anzahl der Durchgaenge in der 2. Wegsuchstufe
nn=1+2*iPath+nP+7 : Anzahl der Straffungen nach der. 2. Wegsuchstufe
nn=1+2*iPath+nP+8 : Anzahl der Ausnahme-Spruenge
Beispiel-Programm fuer Pathfinder :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* Function prototypes */
#define NPOINTS 10
#include <g:\tc\progs\Pathfind.c>
int main()
{
int ii,ij,ik;
int iRC,nPath;
int nP=NPOINTS;
int *pnPathLength,*pnPathStart,*pnAuxResult;
int *piResults;
double pdx[NPOINTS];
double pdy[NPOINTS];
double dMax;
/***************************/
/* Punkte-Haufen erstellen */
/***************************/
nP = NPOINTS;
for (ii=0;ii<nP;ii++)
{
pdx[ii] = 10.0*(rand()/(double)RAND_MAX);
pdy[ii] = 10.0*(rand()/(double)RAND_MAX);
printf("Punkt %1d: x=%lf y=%lf\n",ii,pdx[ii],pdy[ii]);
};
printf("Taste druecken\n");ii = getchar();
dMax = 3.0;
/********/
/*Aufruf*/
/********/
iRC = Pathfinder(nP, pdx, pdy, dMax, 0, 0, 0, &piResults);
/**************/
/* Auswertung */
/**************/
if (iRC!=0) printf("\n\nErgebnisse: iRC = %d \n",iRC);
if (iRC<0) return(-1); /*siehe Fehler-Codes*/
nPath = piResults[0]; /*Anzahl der Pfade*/
pnPathLength = &piResults[1]; /*Pfadlaengen*/
pnPathStart = &piResults[1+nPath]; /*Startadressen*/
pnAuxResult = &piResults[iRC-9]; /*Zusatzresultate*/
printf("Anzahl Pfade = %3d\n\n",nPath);
for (ii=0 ; ii<nPath ; ii++)
{
printf("%1d. Pfad: Laenge = %3d\n",ii+1,pnPathLength[ii]);
for (ij=0; ij<pnPathLength[ii]; ij++)
{
ik = piResults[ pnPathStart[ii] + ij];
printf(" Punkt%3d: %lf %lf \n",ij,pdx[ik],pdy[ik]);
};
printf("\n");
};
printf("Taste druecken\n");ii = getchar();
/*Zusatz-Resultate*/
printf("nCluster =%6d (Anzahl Cluster)\n", pnAuxResult[0]);
printf("dmean =%6.3lf (mittlerer Abstand) \n", pnAuxResult[1]*dMax/1000.0);
printf("nSingle =%6d (Anzahl einzelner Punkte)\n", pnAuxResult[2]);
printf("nNeighsOverall=%6ld (Anzahl Verbindungen mal 2)\n",
(long)pnAuxResult[3]*10000+pnAuxResult[4]);
printf("nRecursmax =%6d (Anzahl Rekursionen (max)\n", pnAuxResult[5]);
printf("nS2Runs =%6d (Anzahl Durchgaenge in 2. Stufe)\n",pnAuxResult[6]);
printf("nTighten =%6d (Anzahl Straffungen) \n", pnAuxResult[7]);
printf("nExcept. -nFar=%6d (Anzahl Ausn.-Spruenge) \n" , pnAuxResult[8]);
printf("Taste druecken\n");ii = getchar();
/*wenn piResult nicht mehr gebraucht wird, unbedingt freigeben, */
/*sonst akkumuliert sich bei mehrfachem Aufruf der allokierte Speicher*/
free(piResults);
ErrorResult:;
return(0);
}; /*end of main*/
Fehler-Meldungen :
******************************************************
* 0nn-Fehler (err_cond) treten bei sinnlosen Mustern *
* oder bei sehr kleiner Max-Sprungweite auf *
******************************************************
001: zu viele oder keine Punkte in der Flaeche
Fehlerbed.: (nP>MAXPOINTS) || (nP<=0)
002: zu viele Hilfsgitter-Felder. Passiert z.B dann, wenn die
Sprungweite dMax sehr klein im Vergleich zur Ausdehnung
des Feldes ist.
Fehlerbed.: (nHGx>MAXFIELDSHG)||(nHGy>MAXFIELDSHG)
003: Sehr stark verklumpte Punktemenge; in einem Hilfsgitterelement
sind mehr als MAXPOINTSHG Punkte.
Fehlerbed.: (pnHG[ psP[ii].ix ][ psP[ii].iy ]++) > MAXPOINTSHG
004: Cluster-Routine NCluster hat zu viele Cluster gefunden
Fehlerbed.: (nCl2==MAXCLUSTER)
005: Es werden zu viele Pfade gefunden; dass heisst, sehr schlecht
zusammenhaengendes Muster.
Fehlerbed.: iPath-1==MAXPATHS
**************************************************
* 1nn Fehler (err_alloc)sind alloc Probleme *
**************************************************
101: Fehler bei alloc vom Hilfgitter (1.Dimension)
Pointer: pnHG , psHG
102: Fehler bei alloc vom Hilfgitter (2.Dimension)
Pointer: pnHG[ii], psHG[ii]
103: Fehler bei alloc von den nP Punkt-structs (SPOINT)
Pointer: psP
104: Fehler bei alloc vom Hilfgitter (3.Dimension)
Pointer: psHG[ii][ij]
105: Fehler bei alloc von Sortierfelder (Reihenfolge Nachbarn)
Pointer: piSort, pdSort, psSort
106: Fehler bei alloc von Nachbar-Zeigern
Pointer: psPP->psNeigh, psPP->pdNeigh
107: Fehler bei alloc in NCluster function
Pointer: piLabel, piTrueLabel
108: Fehler bei alloc fuer stacks von Stufe 1
Pointer: ppStack, ppStack, pcStack, ppStart
109: Fehler bei alloc von Ergebnis-Array
Pointer: *ppiResults
********************************************************
* 2nn Fehler (err_code) weisen auf einen Fehler *
* im Programm hin. Bei Auftreten eines solchen Fehlers *
* bitte U.Weber@gsi.de benachrichtigen *
********************************************************
201: Fehler-Bed.: (nN>=(9*nHGMax+2))
202: Fehler-Bed.: (piSort[in]==-1)
203: Fehler-Bed.: (iStack==nP)
204: Fehler-Bed.: (nReturnLength>=32767)||(nReturnLength<=0)
205: Fehler-Bed.: ((iii<0)||(iii>=iPath))
206: Fehler-Bed.: ( (in<0)||(in>=nP) )
207: Fehler-Bed.: ( psP[in].iPath != ii+1 )
208: Fehler-Bed.: ( ij>=iij )
209: Fehler-Bed.: ( (im = 1+2*iPath+ik+ij) >= nReturnLength )
209: Fehler-Bed.: (ij!=iij)