home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / IRIT / IRITS.ZIP / ADJACNCY.C next >
Encoding:
C/C++ Source or Header  |  1990-05-05  |  19.4 KB  |  485 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *  Module to handle adjacancies between polygons. Each edge has exactly two  *
  7. * polygons which share it. An edge is implicitly defined by the VList - each *
  8. * VertexStruct defines an edge with its succesor, and has a pointer to the   *
  9. * other polygons using that edge. Those pointers are our target in this      *
  10. * module.                                     *
  11. *****************************************************************************/
  12.  
  13. #include <stdio.h>
  14. #include <math.h>
  15. #include "program.h"
  16. #include "allocatg.h"
  17. #include "adjcncyl.h"
  18. #include "adjcncyg.h"
  19.  
  20. /* #define DEBUG         If the adjacencies should be printed to stdout. */
  21. /* #define DEBUG2     If the hash table content should be printed to stdout. */
  22.  
  23. /*****************************************************************************
  24. *   Routine to generate adjacencies to the given object. Returns TRUE if all *
  25. * adjacencies were resolved, meaning the object is perfectly closed.         *
  26. *   Note an edge might be only partially adjacent to another edge, and a     *
  27. * second attempt is made to find (again only part of - see below) them. Any  *
  28. * case, FALSE will be returned as there is no way we can say the object is   *
  29. * perfectly closed!                                 *
  30. *   This is the only routine to generate the adjacencies of a geometric      *
  31. * object. These adjacencies are needed for the boolean operations on them.   *
  32. *   Algorithm: for each edge, for each polygon in the object, the edges are  *
  33. * sorted according to the key defined by EdgeKey routine (sort in hash tbl). *
  34. * A second path on the table is made to match common keys edges and set the  *
  35. * pointers from one to another. Note that each edge is common to exactly 2   *
  36. * faces if it is internal, or exactly 1 face if it is on the border (if the  *
  37. * object is open).                                 *
  38. *****************************************************************************/
  39. int GenAdjacencies(ObjectStruct *PObj)
  40. {
  41.     int i, IsOpenObject;
  42.     struct HashTableStruct *HashTbl, *SecondHashTbl;
  43.     struct HashTableEntry *PHash, *PHashMatch;
  44.     struct PolygonStruct *Pl;
  45.     struct VertexStruct *V;
  46.  
  47.     if (!IS_GEOM_OBJ(PObj))
  48.     FatalError("GenAdjacencies: None goemetric object\n");
  49.     if (IS_POLYLINE_GEOM_OBJ(PObj)) return TRUE; /* No adj. in polyline obj. */
  50.  
  51.     IsOpenObject = FALSE;            /* "Default" is closed object... */
  52.  
  53.     /* Prepare hash tables (for first and second attempts) and clear them.   */
  54.     HashTbl = (HashTableStruct *) MyMalloc(sizeof(HashTableStruct), OTHER_TYPE);
  55.     for (i=0; i<HASH_TABLE_SIZE1; i++) HashTbl -> Entry[i] = NULL;
  56.     SecondHashTbl = (HashTableStruct *) MyMalloc(sizeof(HashTableStruct),
  57.                                 OTHER_TYPE);
  58.     for (i=0; i<HASH_TABLE_SIZE1; i++) SecondHashTbl -> Entry[i] = NULL;
  59.  
  60.     /* Step one - enter all the edges into the hash table: */
  61.     Pl = PObj -> U.Pl;
  62.     while (Pl) {
  63.     V = Pl -> V;
  64.     do {
  65.         InsertHashTable(HashTbl, Pl, V); /* Insert the edge V..V->Pnext. */
  66.         V = V -> Pnext;
  67.     } while (V != NULL && V != Pl -> V);
  68.     Pl = Pl -> Pnext;
  69.     }
  70.  
  71. #ifdef DEBUG2
  72.     printf("Hash Table content:\n");
  73.     for (i=0; i<HASH_TABLE_SIZE; i++) {
  74.     PHash = HashTbl -> Entry[i];
  75.     if (PHash) printf("\nHashTable entry %d:\n", i);
  76.     while (PHash) {
  77.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  78.         PHash -> V -> Pt[0],
  79.         PHash -> V -> Pt[1],
  80.         PHash -> V -> Pt[2],
  81.         PHash -> V -> Pnext -> Pt[0],
  82.         PHash -> V -> Pnext -> Pt[1],
  83.         PHash -> V -> Pnext -> Pt[2]);
  84.         PHash = PHash -> Pnext;
  85.     }
  86.     }
  87. #endif /* DEBUG2 */
  88.  
  89.     /* Step two - scans all the entries and look for the matching edge.      */
  90.     for (i=0; i<HASH_TABLE_SIZE; i++)
  91.     while (HashTbl -> Entry[i] != NULL) {
  92.         PHash = HashTbl -> Entry[i]; /* Remove one edge from hash table. */
  93.         HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
  94.  
  95.         /* Find matching edge (if perfect match - exactly the same edge) */
  96.         /* Otherwise put the edge in SecondHashTbl.                 */
  97.         if ((PHashMatch = FindMatchEdge(HashTbl, i, PHash)) == NULL) {
  98.         PHash -> V -> PAdj = NULL;
  99.         InsertSecondHashTable(SecondHashTbl, PHash);
  100.         IsOpenObject = TRUE;
  101.         }
  102.         else {
  103. #        ifdef DEBUG
  104.             /* If debug switch the pointers of the edges themselves. */
  105.             PHash -> V -> PAdj = (PolygonStruct *) PHashMatch -> V;
  106.             PHashMatch -> V -> PAdj = (PolygonStruct *) PHash -> V;
  107. #        else
  108.             /* Otherwise switch pointers of the edges polygons */
  109.             PHash -> V -> PAdj = PHashMatch -> Pl;
  110.             PHashMatch -> V -> PAdj = PHash -> Pl;
  111. #        endif /* DEBUG */
  112.  
  113.         MyFree((char *) PHash, OTHER_TYPE);
  114.         MyFree((char *) PHashMatch, OTHER_TYPE);
  115.         }
  116.     }
  117.  
  118. #ifdef DEBUG
  119.     printf("Adjacencies for object %s (found to be open = %d)\n",
  120.     PObj -> Name, IsOpenObject);
  121.     Pl = PObj -> U.Pl;
  122.     /* Note that the adjacency in DEBUG is the other edge, not other polygon.*/
  123.     while (Pl) {
  124.     V = Pl -> V;
  125.     do {
  126.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  127.         V -> Pt[0], V -> Pt[1], V -> Pt[2],
  128.         V -> Pnext -> Pt[0], V -> Pnext -> Pt[1], V -> Pnext -> Pt[2]);
  129.         if (V -> PAdj != NULL)
  130.         printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
  131.             ((VertexStruct *) V -> PAdj) -> Pt[0],
  132.             ((VertexStruct *) V -> PAdj) -> Pt[1],
  133.             ((VertexStruct *) V -> PAdj) -> Pt[2],
  134.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[0],
  135.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[1],
  136.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[2]);
  137.         else printf("No Match!\n\n");
  138.         V = V -> Pnext;
  139.     } while (V != NULL && V != Pl -> V);
  140.     Pl = Pl -> Pnext;
  141.     }
  142. #endif /* DEBUG */
  143.  
  144. #ifdef DEBUG2
  145.     printf("Hash Table content left after all full matches were deleted:\n");
  146.     for (i=0; i<HASH_TABLE_SIZE; i++) {
  147.     PHash = SecondHashTbl -> Entry[i];
  148.     if (PHash) printf("\nHashTable entry %d:\n", i);
  149.     while (PHash) {
  150.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  151.         PHash -> V -> Pt[0],
  152.         PHash -> V -> Pt[1],
  153.         PHash -> V -> Pt[2],
  154.         PHash -> V -> Pnext -> Pt[0],
  155.         PHash -> V -> Pnext -> Pt[1],
  156.         PHash -> V -> Pnext -> Pt[2]);
  157.         PHash = PHash -> Pnext;
  158.     }
  159.     }
  160. #endif /* DEBUG2 */
  161.  
  162.     /* Time to activate the second attempt - scan SecondHashTable for edges  */
  163.     /* partially adjacent to each other, but with one common vertex!         */
  164.     for (i=0; i<HASH_TABLE_SIZE; i++)
  165.     while (SecondHashTbl -> Entry[i] != NULL) {
  166.         PHash = SecondHashTbl -> Entry[i];/* Remove one edge from table. */
  167.         SecondHashTbl -> Entry[i] = SecondHashTbl -> Entry[i] -> Pnext;
  168.  
  169.         /* Remove the second instance of this edge with other key: */
  170.         DeleteHashTable(SecondHashTbl, PHash -> V, PHash -> Key);
  171.  
  172.         /* Find matching edge (if perfect match - exactly the same edge) */
  173.         /* Otherwise put the edge in SecondHashTbl.                 */
  174.         if ((PHashMatch = FindSecondMatchEdge(SecondHashTbl, i, PHash)) ==
  175.                                     NULL) {
  176.         PHash -> V -> PAdj = NULL;            /* Failed again! */
  177.         MyFree((char *) PHash, OTHER_TYPE);
  178.         }
  179.         else {
  180. #        ifdef DEBUG
  181.             /* If debug switch the pointers of the edges themselves. */
  182.             PHash -> V -> PAdj = (PolygonStruct *) PHashMatch -> V;
  183.             PHashMatch -> V -> PAdj = (PolygonStruct *) PHash -> V;
  184. #        else
  185.             /* Otherwise switch pointers of the edges polygons. */
  186.             PHash -> V -> PAdj = PHashMatch -> Pl;
  187.             PHashMatch -> V -> PAdj = PHash -> Pl;
  188. #        endif /* DEBUG */
  189.  
  190.         MyFree((char *) PHash, OTHER_TYPE);
  191.         MyFree((char *) PHashMatch, OTHER_TYPE);
  192.         }
  193.     }
  194.  
  195. #ifdef DEBUG
  196.     printf("Adjacencies for object %s - second attempt (found to be open = %d)\n",
  197.     PObj -> Name, IsOpenObject);
  198.     Pl = PObj -> U.Pl;
  199.     /* Note that the adjacency in DEBUG is the other edge, not other polygon.*/
  200.     while (Pl) {
  201.     V = Pl -> V;
  202.     do {
  203.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  204.         V -> Pt[0], V -> Pt[1], V -> Pt[2],
  205.         V -> Pnext -> Pt[0], V -> Pnext -> Pt[1], V -> Pnext -> Pt[2]);
  206.         if (V -> PAdj != NULL)
  207.         printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
  208.             ((VertexStruct *) V -> PAdj) -> Pt[0],
  209.             ((VertexStruct *) V -> PAdj) -> Pt[1],
  210.             ((VertexStruct *) V -> PAdj) -> Pt[2],
  211.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[0],
  212.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[1],
  213.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[2]);
  214.         else printf("No Match!\n\n");
  215.         V = V -> Pnext;
  216.     } while (V != NULL && V != Pl -> V);
  217.     Pl = Pl -> Pnext;
  218.     }
  219. #endif /* DEBUG */
  220.  
  221.     MyFree((char *) HashTbl, OTHER_TYPE);
  222.     MyFree((char *) SecondHashTbl, OTHER_TYPE);
  223.  
  224.     return !IsOpenObject;
  225. }
  226.  
  227. /*****************************************************************************
  228. * Evaluate a key (integer!) from the given vertex V (in polygon Pl) and      *
  229. * insert that in the hash table:                         *
  230. *****************************************************************************/
  231. static void InsertHashTable(HashTableStruct *HashTbl, PolygonStruct *Pl,
  232.                             VertexStruct *V)
  233. {
  234.     int Key;
  235.     HashTableEntry *PHash;
  236.  
  237.     PHash = (HashTableEntry *) MyMalloc(sizeof(HashTableEntry), OTHER_TYPE);
  238.     PHash -> Pl = Pl;
  239.     PHash -> V = V;
  240.     PHash -> Key = Key = EdgeKey(V);
  241.     PHash -> Pnext = HashTbl -> Entry[Key];
  242.     HashTbl -> Entry[Key] = PHash;
  243. }
  244.  
  245. /*****************************************************************************
  246. *   This routine evaluate a key for the given edge. In order the try to make *
  247. * them unique as possible, the point is projected on a "random" vector. I    *
  248. * picked vector X + 1.57 * Y + 1.29 * Z. If you have better one - change it. *
  249. *   The key itself is the average of the two vertices keys.             *
  250. *   Note we get best results if the object is between ~-10..10.             *
  251. *****************************************************************************/
  252. static int EdgeKey(VertexStruct *V)
  253. {
  254.     int key;
  255.     RealType RKey1, RKey2;
  256.  
  257.     RKey1 = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  258.     V = V -> Pnext;
  259.     RKey2 = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  260.  
  261.     key = (((int) ((RKey1 + RKey2) * 10.0)) + HASH_TABLE_SIZE) / 2;
  262.  
  263.     return BOUND(key, 0, HASH_TABLE_SIZE - 1);
  264. }
  265.  
  266. /*****************************************************************************
  267. *   Search The hash table for matching with the given edge pointed by PHash. *
  268. * PHash was extracted from the hash table in entry EntryNum, so the match    *
  269. * is probably in the same entry. If it is not, it must be (if there is one!) *
  270. * in EntryNum+1 as we scans the entries in order and (EntryNum-1) is empty.  *
  271. *   Note that idealy the match was in EntryNum, but because of real number   *
  272. * errors there is a small chance it will be in its neibours: EntryNum +/- 1. *
  273. *****************************************************************************/
  274. static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl, int EntryNum,
  275.                             HashTableEntry *PHash)
  276. {
  277.     int i;
  278.     HashTableEntry *PLast = NULL, *PMatch;
  279.  
  280.     for (i=EntryNum; i<=EntryNum+1; i++) {
  281.     PMatch = HashTbl -> Entry[i];
  282.     while (PMatch) {
  283.         if (SameEdges(PHash -> V -> Pt,  PHash -> V -> Pnext -> Pt,
  284.               PMatch -> V -> Pt, PMatch -> V -> Pnext -> Pt)) {
  285.         /* Delete the matched edge from hash table, and return it: */
  286.         if (PMatch == HashTbl -> Entry[i])
  287.              HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
  288.         else PLast -> Pnext = PLast -> Pnext -> Pnext;
  289.         return PMatch;
  290.         }
  291.         PLast = PMatch;
  292.         PMatch = PMatch -> Pnext;
  293.     }
  294.     }
  295.  
  296.     return NULL;                  /* No match for this one ! */
  297. }
  298.  
  299. /*****************************************************************************
  300. *   Compere two edges - if the same up to an EPSILON (see APX_EQ, irit.h).   *
  301. * The two vetrices of each edge are given, but no order on them is assumed   *
  302. *****************************************************************************/
  303. static int SameEdges(PointType V1E1, PointType V2E1,
  304.              PointType V1E2, PointType V2E2)
  305. {
  306.     return (PT_EQ(V1E1, V1E2) && PT_EQ(V2E1, V2E2)) ||
  307.        (PT_EQ(V1E1, V2E2) && PT_EQ(V2E1, V1E2));
  308. }
  309.  
  310. /******************************************************************************
  311. *   Everything from this point handle the second attempt - try to match edges *
  312. * which are not complete match - cases which one edge is only part of its     *
  313. * adjacent one. We trap only cases which the two edges has common vertex. If  *
  314. * the two edges has no common vertex (i.e. one is totally in the other) we    *
  315. * still misses that. You are invited to improve that. Any case this one will  *
  316. * have influence in extremely rare cases (The booleans will usually propagate *
  317. * the information using the common vertex edges).                  *
  318. *   Note, the obvious, that if one edge is adjacent to few edges, only one    *
  319. * (arbitrarily) will result in the match, and the other will result as NULL.  *
  320. ******************************************************************************/
  321.  
  322. /*****************************************************************************
  323. * Evaluate two keys (integer!) from the given edge in HashTableEntry struct. *
  324. * This time the keys are of the vertices themselves (see SecondEdgeKet rtn). *
  325. * Note each HashTableEntry hold the key of the other entry this time...      *
  326. *****************************************************************************/
  327. static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
  328.                             HashTableEntry *PHash)
  329. {
  330.     int Key1, Key2;
  331.     HashTableEntry *PHash2;
  332.  
  333.     SecondEdgeKey(PHash -> V, &Key1, &Key2);
  334.  
  335.     /* And insert the edge as at Key1 (using given HashTableEntry PHash): */
  336.     PHash -> Key = Key2;
  337.     PHash -> Pnext = SecondHashTbl -> Entry[Key1];
  338.     SecondHashTbl -> Entry[Key1] = PHash;
  339.  
  340.     /* And insert the edge as at Key2 (allocating new HashTableEntry for it):*/
  341.     PHash2 = (HashTableEntry *) MyMalloc(sizeof(HashTableEntry), OTHER_TYPE);
  342.     PHash2 -> Pl = PHash -> Pl;
  343.     PHash2 -> V = PHash -> V;
  344.     PHash2 -> Key = Key1;
  345.     PHash2 -> Pnext = SecondHashTbl -> Entry[Key2];
  346.     SecondHashTbl -> Entry[Key2] = PHash2;
  347. }
  348.  
  349. /*****************************************************************************
  350. *   This routine evaluate two keys for the given edge - one for each of its  *
  351. * vertices, and again tries to make the unique as passible:             *
  352. * picked the same vector: X + 1.57 * Y + 1.29 * Z.                 *
  353. *   Note we get best results if the object is between ~-10..10.             *
  354. *****************************************************************************/
  355. static void SecondEdgeKey(VertexStruct *V, int *Key1, int *Key2)
  356. {
  357.     RealType RKey;
  358.  
  359.     RKey = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  360.     *Key1 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
  361.     *Key1 = BOUND(*Key1, 0, HASH_TABLE_SIZE - 1);
  362.  
  363.     V = V -> Pnext;
  364.     RKey = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  365.     *Key2 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
  366.     *Key2 = BOUND(*Key2, 0, HASH_TABLE_SIZE - 1);
  367. }
  368.  
  369. /*****************************************************************************
  370. *   Search The hash table for matching with the given edge pointed by PHash, *
  371. * as in the second attempt: the keys used here are of the vertices         *
  372. * themselves, so we should search for match in given index EntryNum only.    *
  373. * We search for same vertex AND same direction, which if both match, confirm *
  374. * at list partial adjacency between the two edges (both with same vertex as  *
  375. * one end - the vertex with this key).                         *
  376. *****************************************************************************/
  377. static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
  378.                     int EntryNum, HashTableEntry *PHash)
  379. {
  380.     int EqualFirst, SameDir = FALSE;
  381.     HashTableEntry *PLast = NULL, *PMatch;
  382.  
  383.     PMatch = SecondHashTbl -> Entry[EntryNum]; /* It must be here if exists. */
  384.     while (PMatch) {
  385.     if ((EqualFirst = PT_EQ(PHash -> V -> Pt, PMatch -> V -> Pt)) != 0
  386.               || PT_EQ(PHash -> V -> Pt, PMatch -> V -> Pnext -> Pt)) {
  387.         /* Found same vertex in PMatch as first vertex in PHash - test   */
  388.         /* the direction vectors, to be same also:                 */
  389.         if (EqualFirst) {
  390.         SameDir = TestSameDir(PHash -> V -> Pnext -> Pt,
  391.                       PHash -> V -> Pt,
  392.                       PMatch -> V -> Pnext -> Pt,
  393.                       PMatch -> V -> Pt);
  394.         }
  395.         else {
  396.         SameDir = TestSameDir(PHash -> V -> Pnext -> Pt,
  397.                       PHash -> V -> Pt,
  398.                       PMatch -> V -> Pt,
  399.                       PMatch -> V -> Pnext -> Pt);
  400.         }
  401.     }
  402.     else
  403.     if ((EqualFirst = PT_EQ(PHash -> V -> Pnext -> Pt, PMatch -> V -> Pt))
  404.                                     != 0 ||
  405.         PT_EQ(PHash -> V -> Pnext -> Pt, PMatch -> V -> Pnext -> Pt)) {
  406.         /* Found same vertex in PMatch as second vertex in PHash - test  */
  407.         /* the direction vectors, to be same also:                 */
  408.         if (EqualFirst) {
  409.         SameDir = TestSameDir(PHash -> V -> Pt,
  410.                       PHash -> V -> Pnext -> Pt,
  411.                       PMatch -> V -> Pnext -> Pt,
  412.                       PMatch -> V -> Pt);
  413.         }
  414.         else {
  415.         SameDir = TestSameDir(PHash -> V -> Pt,
  416.                       PHash -> V -> Pnext -> Pt,
  417.                       PMatch -> V -> Pt,
  418.                       PMatch -> V -> Pnext -> Pt);
  419.         }
  420.     }
  421.  
  422.     if (SameDir) {           /* TRUE iff same vertex AND same direction!!! */
  423.         /* Delete the matched edge from the hash table, its compliment   */
  424.         /* with the second key and return a pointer to it:             */
  425.         if (PMatch == SecondHashTbl -> Entry[EntryNum])
  426.         SecondHashTbl -> Entry[EntryNum] =
  427.             SecondHashTbl -> Entry[EntryNum] -> Pnext;
  428.         else PLast -> Pnext = PLast -> Pnext -> Pnext;
  429.         /* Uses the key in structure (hold key of other entry!): */
  430.         DeleteHashTable(SecondHashTbl, PMatch -> V, PMatch -> Key);
  431.         return PMatch;
  432.     }
  433.     PLast = PMatch;
  434.     PMatch = PMatch -> Pnext;
  435.     }
  436.  
  437.     return NULL; /* No match for this one ! */
  438. }
  439.  
  440. /*****************************************************************************
  441. *   Test the the two point pairs (defined two edges) are actually on the     *
  442. * same direction - find normalized direction vector for each and test if     *
  443. * their dot product is equal to 1.                         *
  444. *****************************************************************************/
  445. static int TestSameDir(PointType Pt11, PointType Pt12,
  446.             PointType Pt21, PointType Pt22)
  447. {
  448.     PointType Dir1, Dir2;
  449.  
  450.     PT_SUB(Dir1, Pt12, Pt11);
  451.     PT_SUB(Dir2, Pt22, Pt21);
  452.  
  453.     PT_NORMALIZE(Dir1);
  454.     PT_NORMALIZE(Dir2);
  455.  
  456.     return APX_EQ(DOT_PROD(Dir1, Dir2), 1.0);
  457. }
  458.  
  459. /*****************************************************************************
  460. *   Delete entry in SecondHashTable index EntryNum, which holds vertex V.    *
  461. * This vertex MUST be there, otherwise its a fatal error.             *
  462. *****************************************************************************/
  463. static void DeleteHashTable(HashTableStruct *SecondHashTable,
  464.                         VertexStruct *V, int EntryNum)
  465. {
  466.     HashTableEntry *PLast, *PHash = SecondHashTable -> Entry[EntryNum];
  467.  
  468.     while (PHash != NULL) {
  469.     if (PHash -> V == V) break;
  470.     PLast = PHash;
  471.     PHash = PHash -> Pnext;
  472.     }
  473.  
  474.     if (PHash == NULL)
  475.     FatalError("DeleteHashTable: No hash table entry to delete\n");
  476.     else {
  477.     if (PHash == SecondHashTable -> Entry[EntryNum])
  478.         SecondHashTable -> Entry[EntryNum] =
  479.         SecondHashTable -> Entry[EntryNum] -> Pnext;
  480.     else PLast -> Pnext = PHash -> Pnext;
  481.     MyFree((char *) PHash, OTHER_TYPE);
  482.     }
  483. }
  484.  
  485.