/****************************************************************************** * Handles searching routines. * ******************************************************************************* * (C) Gershon Elber, Technion, Israel Institute of Technology * ******************************************************************************* * Written by Gershon Elber, Sep. 2001 * ******************************************************************************/ #include #include #include "irit_sm.h" #include "misc_loc.h" /* #define DEBUG_MAIN_SEARCH_TEST - To test this file in stand alone mode. */ #ifdef DEBUG_MAIN_SEARCH_TEST #define IritMalloc malloc #define IritFree free #endif /* DEBUG_MAIN_SEARCH_TEST */ #define IRIT_SRCH2D_MAX_DIM 100 typedef struct IritSearch2DElementStruct { struct IritSearch2DElementStruct *Pnext; RealType X, Y; char Data[1]; /* We allocate more than one char, as need, to keep data. */ } IritSearch2DElementStruct; typedef struct IritSearch2DStruct { int GridXSize, GridYSize, DataSize; RealType XMin, XMax, YMin, YMax, DxInv, DyInv, Tol; IritSearch2DElementStruct ***Grid; } IritSearch2DStruct; /***************************************************************************** * DESCRIPTION: M * Initialize the search data structure. M * * * PARAMETERS: M * XMin, XMax, YMin, YMax: Dimensions of 2D domain. M * Tol: Tolerance of expected search. M * DataSize: Size, in bytes, of expected data elements to keep. M * * * RETURN VALUE: M * VoidPtr: An internal auxiliary structure to be provided to the M * insertion and searching routines, NULL if error. M * * * SEE ALSO: M * IritSearch2DInsertElem, IritSearch2DFindElem, IritSearch2DFree M * * * KEYWORDS: M * IritSearch2DInit M *****************************************************************************/ VoidPtr IritSearch2DInit(RealType XMin, RealType XMax, RealType YMin, RealType YMax, RealType Tol, int DataSize) { int XSize, YSize, i; IritSearch2DElementStruct ***Grid; IritSearch2DStruct *Search2D = (IritSearch2DStruct *) IritMalloc(sizeof(IritSearch2DStruct)); Search2D -> XMin = XMin; Search2D -> XMax = XMax; Search2D -> YMin = YMin; Search2D -> YMax = YMax; Search2D -> Tol = Tol; Search2D -> DataSize = DataSize; if (XMax == XMin) return NULL; Search2D -> DxInv = 1.0 / (XMax - XMin); if (YMax == YMin) return NULL; Search2D -> DyInv = 1.0 / (YMax - YMin); XSize = (int) ((XMax - XMin) / Tol); XSize = BOUND(XSize, 1, IRIT_SRCH2D_MAX_DIM); Search2D -> GridXSize = XSize; YSize = (int) ((YMax - YMin) / Tol); YSize = BOUND(YSize, 1, IRIT_SRCH2D_MAX_DIM); Search2D -> GridYSize = YSize; Search2D -> Grid = Grid = (IritSearch2DElementStruct ***) IritMalloc(YSize * sizeof(IritSearch2DElementStruct **)); for (i = 0; i < YSize; i++) { Grid[i] = (IritSearch2DElementStruct **) IritMalloc(XSize * sizeof(IritSearch2DElementStruct *)); ZAP_MEM(Grid[i], XSize * sizeof(IritSearch2DElementStruct *)); } return Search2D; } /***************************************************************************** * DESCRIPTION: M * Free auxiliary data structure aiding in 2D search. M * * * PARAMETERS: M * S2D: Internal data structure, aiding search, to be freed. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * IritSearch2DInsertElem, IritSearch2DFindElem, IritSearch2DInit M * * * KEYWORDS: M * IritSearch2DFree M *****************************************************************************/ void IritSearch2DFree(VoidPtr S2D) { int j, i; IritSearch2DStruct *Search2D = (IritSearch2DStruct *) S2D; for (j = 0; j < Search2D -> GridYSize; j++) { for (i = 0; i < Search2D -> GridXSize; i++) { IritSearch2DElementStruct *Elements = Search2D -> Grid[j][i]; while (Elements != NULL) { IritSearch2DElementStruct *NextElements = Elements -> Pnext; IritFree(Elements); Elements = NextElements; } } IritFree(Search2D -> Grid[j]); } IritFree(Search2D -> Grid); IritFree(Search2D); } /***************************************************************************** * DESCRIPTION: M * Insert a new element into the data structure. No test is made if a M * similar element already exists. M * * * PARAMETERS: M * S2D: Internal data structure, aiding search. M * XKey, YKey: The new 2D coordinates to insert. M * Data: A pointer to the data to save with this 2D coordinate key. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * IritSearch2DFree, IritSearch2DFindElem, IritSearch2DInit M * * * KEYWORDS: M * IritSearch2DInsertElem M *****************************************************************************/ void IritSearch2DInsertElem(VoidPtr S2D, RealType XKey, RealType YKey, VoidPtr Data) { int i, j; IritSearch2DStruct *Search2D = (IritSearch2DStruct *) S2D; IritSearch2DElementStruct *Element = (IritSearch2DElementStruct *) IritMalloc(sizeof(IritSearch2DElementStruct) + Search2D -> DataSize); RealType Fx = (XKey - Search2D -> XMin) * Search2D -> DxInv * Search2D -> GridXSize, Fy = (YKey - Search2D -> YMin) * Search2D -> DyInv * Search2D -> GridYSize; i = (int) BOUND(Fx, 0, Search2D -> GridXSize - 1); j = (int) BOUND(Fy, 0, Search2D -> GridXSize - 1); GEN_COPY(Element -> Data, Data, Search2D -> DataSize); Element -> X = XKey; Element -> Y = YKey; LIST_PUSH(Element, Search2D -> Grid[j][i]); } /***************************************************************************** * DESCRIPTION: M * Looks for an existing element in the data structure. If found an M * element within prescribed tolerance, Data is updated with the saved data M * * * PARAMETERS: M * S2D: Internal data structure, aiding search. M * XKey, YKey: The 2D coordinates to search for. M * Data: A pointer to the location to copy the found data into. M * * * RETURN VALUE: M * int: TRUE if element was found, FALSE otherwise. M * * * SEE ALSO: M * IritSearch2DFree, IritSearch2DInsertElem, IritSearch2DInit M * * * KEYWORDS: M * IritSearch2DFindElem M *****************************************************************************/ int IritSearch2DFindElem(VoidPtr S2D, RealType XKey, RealType YKey, VoidPtr Data) { int x, y, x1, y1, x2, y2; VoidPtr FoundData; IritSearch2DStruct *Search2D = (IritSearch2DStruct *) S2D; RealType MinSqrDist, Fx = (XKey - Search2D -> XMin) * Search2D -> DxInv * Search2D -> GridXSize, Fy = (YKey - Search2D -> YMin) * Search2D -> DyInv * Search2D -> GridYSize; /* Locate the local neighboorhood we must examine, taking into account */ /* tolerance deviation (in the order of one cell width). */ x1 = (int) (Fx - 1); y1 = (int) (Fy - 1); x2 = (int) (Fx + 1); y2 = (int) (Fy + 1); x1 = BOUND(x1, 0, Search2D -> GridXSize - 1); y1 = BOUND(y1, 0, Search2D -> GridXSize - 1); x2 = BOUND(x2, 0, Search2D -> GridXSize - 1); y2 = BOUND(y2, 0, Search2D -> GridXSize - 1); FoundData = NULL; MinSqrDist = SQR(Search2D -> Tol); for (y = y1; y <= y2; y++) { for (x = x1; x <= x2; x++) { IritSearch2DElementStruct *El, *Elements = Search2D -> Grid[y][x]; for (El = Elements; El != NULL; El = El -> Pnext) { RealType SqrDist = SQR(XKey - El -> X) + SQR(YKey - El -> Y); if (MinSqrDist > SqrDist) { MinSqrDist = SqrDist; FoundData = El -> Data; } } } } if (FoundData) { GEN_COPY(Data, FoundData, Search2D -> DataSize); return TRUE; } else return FALSE; } #ifdef DEBUG_MAIN_SEARCH_TEST /* Stand alone VC++ compilation line. cl -DDEBUG_SEARCH_TEST_MAIN -DHAVE_URT_RLE -DHAVE_GIF_LIB -Zi -Od -D__WINNT__ -D__OPENGL__ -D_X86_=1 -DWIN32 -D_MT -DRAND -W3 -nologo -Ie:\c\urt\include -Ie:\c\giflib\lib -DDEBUG_IRIT_MALLOC -I. -Ie:\irit\irit\include -Fosearch.obj search.c */ #define NUM_ITEMS 100000 RealType DbgRandom(RealType Min, RealType Max) { long R = rand(); return Min + (Max - Min) * ((double) (R & RAND_MAX)) / ((double) RAND_MAX); } n void main() { int i; static RealType TestArray[NUM_ITEMS * 2][2], Data[2]; VoidPtr S2D = IritSearch2DInit(0, 10, 0, 10, 0.001, sizeof(RealType) * 2); /* Insert (half) the data in. */ for (i = 0; i < NUM_ITEMS * 2; i++) { TestArray[i][0] = DbgRandom(0, 10); TestArray[i][1] = DbgRandom(0, 10); if (i < NUM_ITEMS) IritSearch2DInsertElem(S2D, TestArray[i][0], TestArray[i][1], TestArray[i]); } /* Now lets see if we can find it. */ fprintf(stderr, "Searching items that must be inside...\n"); for (i = 0; i < NUM_ITEMS; i++) { if (!IritSearch2DFindElem(S2D, TestArray[i][0], TestArray[i][1], Data)) fprintf(stderr, IRIT_EXP_STR("Failed to find item %d\n"), i); else { if (TestArray[i][0] != Data[0] || TestArray[i][1] != Data[1]) fprintf(stderr, "Found item %d not identical\n", i); } } fprintf(stderr, IRIT_EXP_STR("\nSearching items that are not inside...\n")); for (i = NUM_ITEMS; i < NUM_ITEMS * 2; i++) { if (IritSearch2DFindElem(S2D, TestArray[i][0], TestArray[i][1], Data)) fprintf(stderr, IRIT_EXP_STR("Found item %d: [%f %f], key = [%f %f]\n"), i, TestArray[i][0], TestArray[i][1], Data[0], Data[1]); } fprintf(stderr, "\nDone.\n"); } #endif /* DEBUG_MAIN_SEARCH_TEST */