/*****************************************************************************
*   "Irit" - the 3d (not only polygonal) solid modeller.		     *
*									     *
* Written by:  Gershon Elber				Ver 0.2, Mar. 1990   *
******************************************************************************
*  Module to handle adjacancies between polygons. Each edge has exactly two  *
* polygons which share it. An edge is implicitly defined by the VList - each *
* IPVertexStruct defines an edge with its succesor, and has a pointer to the *
* other polygons using that edge. Those pointers are our target in this      *
* module.								     *
*****************************************************************************/

#include <stdio.h>
#include <math.h>
#include "irit_sm.h"
#include "allocate.h"
#include "bool_loc.h"

/* #define DEBUG1	     If the adjacencies should be printed to stdout. */
/* #define DEBUG2     If the hash table content should be printed to stdout. */

#define HASH_TABLE_SIZE  100
#define HASH_TABLE_SIZE1 101			     /* One above the above. */
#define HASH_TABLE_SIZE2 50			       /* Half of the above. */

typedef struct HashTableEntry {
    int Key;
    IPPolygonStruct *Pl;
    IPVertexStruct *V;
    struct HashTableEntry *Pnext;
} HashTableEntry;

typedef struct HashTableStruct {
    HashTableEntry *Entry[HASH_TABLE_SIZE1];
} HashTableStruct;

/* Prototypes of local function of adjacecies module: */
static void InsertHashTable(HashTableStruct *HashTbl,
			    IPPolygonStruct *Pl,
			    IPVertexStruct *V);
static int EdgeKey(IPVertexStruct *V);
static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl,
				     int EntryNum,
				     HashTableEntry *PHash);
static int SameEdges(PointType V1E1,
		     PointType V2E1,
		     PointType V1E2,
		     PointType V2E2);
static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
				  HashTableEntry *PHash);
static void SecondEdgeKey(IPVertexStruct *V, int *Key1, int *Key2);
static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
					   int EntryNum,
					   HashTableEntry *PHash);
static int TestSameDir(PointType Pt11,
		       PointType Pt12,
		       PointType Pt21,
		       PointType Pt22);
static void DeleteHashTable(HashTableStruct *SecondHashTable,
			    IPVertexStruct *V,
			    int EntryNum);

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Routine to generate adjacencies to the given object.                     M
*   Note an edge might be only partially adjacent to another edge, and a     M
* second attempt is made to find (again only part of - see below) them. Any  M
* case, FALSE will be returned as there is no way we can say the object is   M
* perfectly closed!							     M
*   This is the only routine to generate the adjacencies of a geometric      M
* object. These adjacencies are needed for the boolean operations on them.   M
*   Algorithm: for each edge, for each polygon in the object, the edges are  M
* sorted according to the key defined by EdgeKey routine (sort in hash tbl). M
* A second path on the table is made to match common keys edges and set the  M
* pointers from one to another. Note that each edge is common to exactly 2   M
* faces if it is internal, or exactly 1 face if it is on the border (if the  M
* object is open).							     M
*                                                                            *
* PARAMETERS:                                                                M
*   PObj: The polygonal object to compute the adjacency information for.     M
*                                                                            *
* RETURN VALUE:                                                              M
*   int: TRUE if all adjacencies were resolved, or the object is completely  M
*        closed.                                                             M
*                                                                            *
* KEYWORDS:                                                                  M
*   BoolGenAdjacencies, adjacency, topology                                  M
*****************************************************************************/
int BoolGenAdjacencies(IPObjectStruct *PObj)
{
    int i, IsOpenObject;
    HashTableStruct *HashTbl, *SecondHashTbl;
    HashTableEntry *PHash, *PHashMatch;
    IPPolygonStruct *Pl;
    IPVertexStruct *V;

    if (!IP_IS_POLY_OBJ(PObj))
	IritFatalError("GenAdjacencies: Non polygonal object");
    if (IP_IS_POLYLINE_OBJ(PObj))
	return TRUE;				 /* No adj. in polyline obj. */

    IsOpenObject = FALSE;		    /* "Default" is closed object... */

    /* Prepare hash tables (for first and second attempts) and clear them.   */
    HashTbl = (HashTableStruct *) IritMalloc(sizeof(HashTableStruct));
    for (i = 0; i < HASH_TABLE_SIZE1; i++)
	HashTbl -> Entry[i] = NULL;
    SecondHashTbl = (HashTableStruct *) IritMalloc(sizeof(HashTableStruct));
    for (i = 0; i < HASH_TABLE_SIZE1; i++)
	SecondHashTbl -> Entry[i] = NULL;

    /* Step one - enter all the edges into the hash table: */
    Pl = PObj -> U.Pl;
    while (Pl) {
	V = Pl -> PVertex;
	do {
	    InsertHashTable(HashTbl, Pl, V); /* Insert the edge V..V->Pnext. */
	    V = V -> Pnext;
	} while (V != NULL && V != Pl -> PVertex);
	Pl = Pl -> Pnext;
    }

#ifdef DEBUG2
    printf("Hash Table content:\n");
    for (i = 0; i < HASH_TABLE_SIZE; i++) {
	PHash = HashTbl -> Entry[i];
	if (PHash)
	    printf("\nHashTable entry %d:\n", i);
	while (PHash) {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		PHash -> V -> Coord[0],
		PHash -> V -> Coord[1],
		PHash -> V -> Coord[2],
		PHash -> V -> Pnext -> Coord[0],
		PHash -> V -> Pnext -> Coord[1],
		PHash -> V -> Pnext -> Coord[2]);
	    PHash = PHash -> Pnext;
	}
    }
#endif /* DEBUG2 */

    /* Step two - scans all the entries and look for the matching edge.      */
    for (i = 0; i < HASH_TABLE_SIZE; i++)
	while (HashTbl -> Entry[i] != NULL) {
	    PHash = HashTbl -> Entry[i]; /* Remove one edge from hash table. */
	    HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;

	    /* Find matching edge (if perfect match - exactly the same edge) */
	    /* Otherwise put the edge in SecondHashTbl.			     */
	    if ((PHashMatch = FindMatchEdge(HashTbl, i, PHash)) == NULL) {
		PHash -> V -> PAdj = NULL;
		InsertSecondHashTable(SecondHashTbl, PHash);
		IsOpenObject = TRUE;
	    }
	    else {
#		ifdef DEBUG1
		    /* If DEBUG1 switch the pointers of the edges themselves.*/
		    PHash -> V -> PAdj = (IPPolygonStruct *) PHashMatch -> V;
		    PHashMatch -> V -> PAdj = (IPPolygonStruct *) PHash -> V;
#		else
		    /* Otherwise switch pointers of the edges polygons */
		    PHash -> V -> PAdj = PHashMatch -> Pl;
		    PHashMatch -> V -> PAdj = PHash -> Pl;
#		endif /* DEBUG1 */

		IritFree((VoidPtr) PHash);
		IritFree((VoidPtr) PHashMatch);
	    }
	}

#ifdef DEBUG1
    printf("Adjacencies for object %s (found to be open = %d)\n",
	PObj -> Name, IsOpenObject);
    Pl = PObj -> U.Pl.P;
    /* Note that adjacency in DEBUG1 is the other edge, not other polygon. */
    while (Pl) {
	V = Pl -> V;
	do {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		V -> Coord[0], V -> Coord[1], V -> Coord[2],
		V -> Pnext -> Coord[0], V -> Pnext -> Coord[1],
		V -> Pnext -> Coord[2]);
	    if (V -> PAdj != NULL)
		printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
		    ((IPVertexStruct *) V -> PAdj) -> Coord[0],
		    ((IPVertexStruct *) V -> PAdj) -> Coord[1],
		    ((IPVertexStruct *) V -> PAdj) -> Coord[2],
		    ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[0],
		    ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[1],
		    ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[2]);
	    else
		printf("No Match!\n\n");
	    V = V -> Pnext;
	} while (V != NULL && V != Pl -> V);
	Pl = Pl -> Pnext;
    }
#endif /* DEBUG1 */

#ifdef DEBUG2
    printf("Hash Table content left after all full matches were deleted:\n");
    for (i = 0; i < HASH_TABLE_SIZE; i++) {
	PHash = SecondHashTbl -> Entry[i];
	if (PHash)
	    printf("\nHashTable entry %d:\n", i);
	while (PHash) {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		PHash -> V -> Coord[0],
		PHash -> V -> Coord[1],
		PHash -> V -> Coord[2],
		PHash -> V -> Pnext -> Coord[0],
		PHash -> V -> Pnext -> Coord[1],
		PHash -> V -> Pnext -> Coord[2]);
	    PHash = PHash -> Pnext;
	}
    }
#endif /* DEBUG2 */

    /* Time to activate the second attempt - scan SecondHashTable for edges  */
    /* partially adjacent to each other, but with one common vertex!	     */
    for (i = 0; i < HASH_TABLE_SIZE; i++)
	while (SecondHashTbl -> Entry[i] != NULL) {
	    PHash = SecondHashTbl -> Entry[i];/* Remove one edge from table. */
	    SecondHashTbl -> Entry[i] = SecondHashTbl -> Entry[i] -> Pnext;

	    /* Remove the second instance of this edge with other key: */
	    DeleteHashTable(SecondHashTbl, PHash -> V, PHash -> Key);

	    /* Find matching edge (if perfect match - exactly the same edge) */
	    /* Otherwise put the edge in SecondHashTbl.			     */
	    if ((PHashMatch = FindSecondMatchEdge(SecondHashTbl, i, PHash)) ==
									NULL) {
		PHash -> V -> PAdj = NULL;		    /* Failed again! */
		IritFree((VoidPtr) PHash);
	    }
	    else {
#		ifdef DEBUG1
		    /* If DEBUG1 switch the pointers of the edges themselves. */
		    PHash -> V -> PAdj = (IPPolygonStruct *) PHashMatch -> V;
		    PHashMatch -> V -> PAdj = (IPPolygonStruct *) PHash -> V;
#		else
		    /* Otherwise switch pointers of the edges polygons. */
		    PHash -> V -> PAdj = PHashMatch -> Pl;
		    PHashMatch -> V -> PAdj = PHash -> Pl;
#		endif /* DEBUG1 */

		IritFree((VoidPtr) PHash);
		IritFree((VoidPtr) PHashMatch);
	    }
	}

#ifdef DEBUG1
    printf("Adjacencies for object %s - second attempt (found to be open = %d)\n",
	PObj -> Name, IsOpenObject);
    Pl = PObj -> U.Pl.P;
    /* Note that adjacency in DEBUG1 is the other edge, not other polygon. */
    while (Pl) {
	V = Pl -> V;
	do {
	    printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
		V -> Coord[0], V -> Coord[1], V -> Coord[2],
		V -> Pnext -> Coord[0], V -> Pnext -> Coord[1],
		V -> Pnext -> Coord[2]);
	    if (V -> PAdj != NULL)
		printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
		    ((IPVertexStruct *) V -> PAdj) -> Coord[0],
		    ((IPVertexStruct *) V -> PAdj) -> Coord[1],
		    ((IPVertexStruct *) V -> PAdj) -> Coord[2],
		    ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[0],
		    ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[1],
		    ((IPVertexStruct *) V -> PAdj) -> Pnext -> Coord[2]);
	    else
		printf("No Match!\n\n");
	    V = V -> Pnext;
	} while (V != NULL && V != Pl -> V);
	Pl = Pl -> Pnext;
    }
#endif /* DEBUG1 */

    IritFree((VoidPtr) HashTbl);
    IritFree((VoidPtr) SecondHashTbl);

    return !IsOpenObject;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Evaluates a key (integer!) from the given vertex V (in polygon Pl) and   *
* insert that in the hash table:					     *
*                                                                            *
* PARAMETERS:                                                                *
*   HashTbl:  To be used.                                                    *
*   Pl:       Polygon containing vertex.                                     *
*   V:        Vertex to insert into hash table.                              *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void InsertHashTable(HashTableStruct *HashTbl,
			    IPPolygonStruct *Pl,
			    IPVertexStruct *V)
{
    int Key;
    HashTableEntry *PHash;

    PHash = (HashTableEntry *) IritMalloc(sizeof(HashTableEntry));
    PHash -> Pl = Pl;
    PHash -> V = V;
    PHash -> Key = Key = EdgeKey(V);
    PHash -> Pnext = HashTbl -> Entry[Key];
    HashTbl -> Entry[Key] = PHash;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   This routine evaluates a key for a given edge. In order the try to make  *
* them unique as possible, the point is projected on a "random" vector. I    *
* picked vector X + 1.57 * Y + 1.29 * Z. If you have better one - change it. *
*   The key itself is the average of the two vertices keys.		     *
*   Note we get best results if the object is between ~-10..10.		     *
*                                                                            *
* PARAMETERS:                                                                *
*   V:   To computed key for.                                                *
*                                                                            *
* RETURN VALUE:                                                              *
*   int: The resulting key.                                                  *
*****************************************************************************/
static int EdgeKey(IPVertexStruct *V)
{
    int key;
    RealType RKey1, RKey2;

    RKey1 = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);
    V = V -> Pnext;
    RKey2 = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);

    key = (((int) ((RKey1 + RKey2) * 10.0)) + HASH_TABLE_SIZE) / 2;

    return BOUND(key, 0, HASH_TABLE_SIZE - 1);
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Searches the hash table for matching with a given edge pointed by PHash. *
* PHash was extracted from the hash table in entry EntryNum, so the match    *
* is probably in the same entry. If it is not, it must be (if there is one!) *
* in EntryNum+1 as we scans the entries in order and (EntryNum-1) is empty.  *
*   Note that idealy the match was in EntryNum, but because of real number   *
* errors there is a small chance it will be in its neibours: EntryNum +/- 1. *
*                                                                            *
* PARAMETERS:                                                                *
*   HashTbl:   To search.                                                    *
*   EntryNum:  The probably contains the matching to PHash.                  *
*   PHash:     To find a match for.                                          *
*                                                                            *
* RETURN VALUE:                                                              *
*   HashTableEntry *:  The matched entry.                                    *
*****************************************************************************/
static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl,
				     int EntryNum,
				     HashTableEntry *PHash)
{
    int i;
    HashTableEntry *PMatch,
	*PLast = NULL;

    for (i = EntryNum; i <= EntryNum+1; i++) {
	PMatch = HashTbl -> Entry[i];
	while (PMatch) {
	    if (SameEdges(PHash -> V -> Coord,  PHash -> V -> Pnext -> Coord,
			  PMatch -> V -> Coord, PMatch -> V -> Pnext -> Coord)) {
		/* Delete the matched edge from hash table, and return it: */
		if (PMatch == HashTbl -> Entry[i])
		    HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
		else
		    PLast -> Pnext = PLast -> Pnext -> Pnext;
		return PMatch;
	    }
	    PLast = PMatch;
	    PMatch = PMatch -> Pnext;
	}
    }

    return NULL;				  /* No match for this one ! */
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Compere two edges - if the same up to BOOL_EPSILON (see BOOL_PT_APX_EQ). *
* The two vetrices of each edge are given, but no order on them is assumed   *
*                                                                            *
* PARAMETERS:                                                                *
*   V1E1, V2E1: Two vertices of first edge.                                  *
*   V1E2, V2E2: Two vertices of second edge.                                 *
*                                                                            *
* RETURN VALUE:                                                              *
*   inr: TRUE is found the same, FALSE otherwise.                            *
*****************************************************************************/
static int SameEdges(PointType V1E1,
		     PointType V2E1,
		     PointType V1E2,
		     PointType V2E2)
{
    return (BOOL_PT_APX_EQ(V1E1, V1E2) && BOOL_PT_APX_EQ(V2E1, V2E2)) ||
	   (BOOL_PT_APX_EQ(V1E1, V2E2) && BOOL_PT_APX_EQ(V2E1, V1E2));
}

/*****************************************************************************
*   Everything from this point handles the second attempt - match edges      *
* which are not complete match - cases which one edge is only part of its    *
* adjacent one. We trap only cases which the two edges has common vertex. If *
* the two edges has no common vertex (i.e. one is totally in the other) we   *
* still misses that. You are invited to improve that. Any case this one will *
* have influence in extremely rare cases (The booleans will usually          *
* propagate the information using the common vertex edges).	             *
*   Note, the obvious, that if one edge is adjacent to few edges, only one   *
* (arbitrarily) will result in the match, and the other will result as NULL. *
*****************************************************************************/

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Evaluates two keys (integer!) from a given edge in HashTableEntry.       *
*   This time keys are of the vertices themselves (see SecondEdgeKet rtn).   *
*   Note each HashTableEntry hold the key of the other entry this time...    *
*                                                                            *
* PARAMETERS:                                                                *
*   SecondHashTbl:   See above.                                               *
*   PHash:           See above.                                              *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
				  HashTableEntry *PHash)
{
    int Key1, Key2;
    HashTableEntry *PHash2;

    SecondEdgeKey(PHash -> V, &Key1, &Key2);

    /* And insert the edge as at Key1 (using given HashTableEntry PHash): */
    PHash -> Key = Key2;
    PHash -> Pnext = SecondHashTbl -> Entry[Key1];
    SecondHashTbl -> Entry[Key1] = PHash;

    /* And insert the edge as at Key2 (allocating new HashTableEntry for it):*/
    PHash2 = (HashTableEntry *) IritMalloc(sizeof(HashTableEntry));
    PHash2 -> Pl = PHash -> Pl;
    PHash2 -> V = PHash -> V;
    PHash2 -> Key = Key1;
    PHash2 -> Pnext = SecondHashTbl -> Entry[Key2];
    SecondHashTbl -> Entry[Key2] = PHash2;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   This routine evaluates two keys for the given edge - one for each of its *
* vertices, and again tries to make them unique as passible:		     *
* picked the same vector: X + 1.57 * Y + 1.29 * Z.			     *
*   Note we get best results if the object is between ~-10..10.		     *
*                                                                            *
* PARAMETERS:                                                                *
*   V:        To compute keys for it and its next vertex, forming the edge.  *
*   Key1, Key2: The resulting two keys of the two vertices.                  *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void SecondEdgeKey(IPVertexStruct *V, int *Key1, int *Key2)
{
    RealType RKey;

    RKey = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);
    *Key1 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
    *Key1 = BOUND(*Key1, 0, HASH_TABLE_SIZE - 1);

    V = V -> Pnext;
    RKey = (V -> Coord[0] + 1.57 * V -> Coord[1] + 1.29 * V -> Coord[2]);
    *Key2 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
    *Key2 = BOUND(*Key2, 0, HASH_TABLE_SIZE - 1);
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Search The hash table for matching with the given edge pointed by PHash, *
* as in the second attempt: the keys used here are of the vertices	     *
* themselves, so we should search for match in given index EntryNum only.    *
* We search for same vertex AND same direction, which if both match, confirm *
* at list partial adjacency between the two edges (both with same vertex as  *
* one end - the vertex with this key).					     *
*                                                                            *
* PARAMETERS:                                                                *
*   SecondHashTbl:    Containing the edge database.                          *
*   EntryNum:         Where to look at the database.                         *
*   PHash:            To search for a match                                  *
*                                                                            *
* RETURN VALUE:                                                              *
*   HashTableEntry:   Found match, if any.                                   *
*****************************************************************************/
static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
					   int EntryNum,
					   HashTableEntry *PHash)
{
    int EqualFirst,
	SameDir = FALSE;
    HashTableEntry *PMatch,
	*PLast = NULL;

    PMatch = SecondHashTbl -> Entry[EntryNum]; /* It must be here if exists. */
    while (PMatch) {
	if ((EqualFirst = BOOL_PT_APX_EQ(PHash -> V -> Coord,
					 PMatch -> V -> Coord)) != 0 ||
	    BOOL_PT_APX_EQ(PHash -> V -> Coord,
			   PMatch -> V -> Pnext -> Coord)) {
	    /* Found same vertex in PMatch as first vertex in PHash - test   */
	    /* the direction vectors, to be same also:			     */
	    if (EqualFirst) {
		SameDir = TestSameDir(PHash -> V -> Pnext -> Coord,
				      PHash -> V -> Coord,
				      PMatch -> V -> Pnext -> Coord,
				      PMatch -> V -> Coord);
	    }
	    else {
		SameDir = TestSameDir(PHash -> V -> Pnext -> Coord,
				      PHash -> V -> Coord,
				      PMatch -> V -> Coord,
				      PMatch -> V -> Pnext -> Coord);
	    }
	}
	else if ((EqualFirst = BOOL_PT_APX_EQ(PHash -> V -> Pnext -> Coord,
					      PMatch -> V -> Coord)) != 0 ||
	    BOOL_PT_APX_EQ(PHash -> V -> Pnext -> Coord,
			   PMatch -> V -> Pnext -> Coord)) {
	    /* Found same vertex in PMatch as second vertex in PHash - test  */
	    /* the direction vectors, to be same also:			     */
	    if (EqualFirst) {
		SameDir = TestSameDir(PHash -> V -> Coord,
				      PHash -> V -> Pnext -> Coord,
				      PMatch -> V -> Pnext -> Coord,
				      PMatch -> V -> Coord);
	    }
	    else {
		SameDir = TestSameDir(PHash -> V -> Coord,
				      PHash -> V -> Pnext -> Coord,
				      PMatch -> V -> Coord,
				      PMatch -> V -> Pnext -> Coord);
	    }
	}

	if (SameDir) {	       /* TRUE iff same vertex AND same direction!!! */
	    /* Delete the matched edge from the hash table, its compliment   */
	    /* with the second key and return a pointer to it:		     */
	    if (PMatch == SecondHashTbl -> Entry[EntryNum])
		SecondHashTbl -> Entry[EntryNum] =
		    SecondHashTbl -> Entry[EntryNum] -> Pnext;
	    else
		PLast -> Pnext = PLast -> Pnext -> Pnext;
	    /* Uses the key in structure (hold key of other entry!): */
	    DeleteHashTable(SecondHashTbl, PMatch -> V, PMatch -> Key);
	    return PMatch;
	}
	PLast = PMatch;
	PMatch = PMatch -> Pnext;
    }

    return NULL; /* No match for this one ! */
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Test if the two points pairs (defining two edges) are actually on the    *
* same direction - find normalized direction vector for each and test if     *
* their dot product is equal to 1.					     *
*                                                                            *
* PARAMETERS:                                                                *
*   Pt11, Pt12:  The pair defining the first line.                           *
*   Pt21, Pt22:  The pair defining the second line.                          *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:   TRUE if same direction, FALSE otherwise.                          *
*****************************************************************************/
static int TestSameDir(PointType Pt11,
		       PointType Pt12,
		       PointType Pt21,
		       PointType Pt22)
{
    PointType Dir1, Dir2;

    PT_SUB(Dir1, Pt12, Pt11);
    PT_SUB(Dir2, Pt22, Pt21);

    PT_NORMALIZE(Dir1);
    PT_NORMALIZE(Dir2);

    return BOOL_APX_EQ(DOT_PROD(Dir1, Dir2), 1.0);
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Delete entry in SecondHashTable index EntryNum, which holds vertex V.    *
* This vertex MUST be there, otherwise its a fatal error.		     *
*                                                                            *
* PARAMETERS:                                                                *
*   SecondHashTable:    Data base.                                           *
*   V:                  Vertex to be removed from data base.                 *
*   EntryNum:           Where to search for V in data base.                  *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void DeleteHashTable(HashTableStruct *SecondHashTable,
			    IPVertexStruct *V,
			    int EntryNum)
{
    HashTableEntry
	*PLast = NULL,
	*PHash = SecondHashTable -> Entry[EntryNum];

    while (PHash != NULL) {
	if (PHash -> V == V)
	    break;
	PLast = PHash;
	PHash = PHash -> Pnext;
    }

    if (PHash == NULL)
	IritFatalError("DeleteHashTable: No hash table entry to delete");
    else {
	if (PHash == SecondHashTable -> Entry[EntryNum])
	    SecondHashTable -> Entry[EntryNum] =
		SecondHashTable -> Entry[EntryNum] -> Pnext;
	else
	    PLast -> Pnext = PHash -> Pnext;
	IritFree((VoidPtr) PHash);
    }
}

