home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / gstobjects_1 / quadtree / 140 / 100 / quadtree < prev   
Encoding:
Text File  |  1994-09-23  |  3.9 KB  |  149 lines
  1. /***************************************************************************
  2.  
  3.                 (C) 1994 George Taylor
  4.                 ----------------------
  5.  
  6.  
  7.         Title:        quadtree
  8.  
  9.         Purpose:    2D Space subdivision for quick collision detection
  10.  
  11.         Author:        George Taylor
  12.  
  13.         Notes:          These procedures must be called from
  14.                 a Shared C Library environment (eg call from C/Pascal).
  15.  
  16.                 malloc(),free() are used for space allocation.
  17.  
  18. ***************************************************************************/
  19.  
  20.  
  21. /* need GeomI2 type */
  22. #include "<Adhesive$ObjectPath>139.100.geometry"
  23.  
  24.  
  25. /* abstract quadtree */
  26. typedef void *Quadtree;
  27.  
  28.  
  29. /* a point in a quadtree */
  30. typedef struct Quadtree_Point {
  31.   GeomI2 point;        /* the position of the point */
  32.   void   *private;    /* private pointer associated with a point */
  33.   /* After you have added a point, you can use the elements below to
  34.      get to a point in one of the four quadrants around the point.
  35.      These pointers are NULL if there are no such points.
  36.   */
  37.   struct Quadtree_Point *tr,*tl,*bl,*br;
  38. } Quadtree_Point;
  39.  
  40.  
  41.  
  42. /* Procedure:    quadtree_New
  43.  *
  44.  * Description:    Makes a new emptry Quadtree.
  45.  *
  46.  * Parameters:    none
  47.  *
  48.  * Returns:    Quadtree - abstract tree of NULL if not enough space
  49.  *
  50.  * Other Info:
  51.  */
  52. Quadtree quadtree_New(void);
  53.  
  54.  
  55.  
  56. /* Procedure:    quadtree_Build
  57.  *
  58.  * Description:    Given an array of GeomI2 points, insert them into a Quadtree.
  59.  *
  60.  * Parameters:    Quadtree q
  61.  *        Quadtree_Point *points - an array of points
  62.  *    A copy of this array is NOT made, it must remain in existence until
  63.  *    after quadtree_Empty() or quadtree_Dispose() is called.
  64.  *        unsigned int num - number of points in array
  65.  *
  66.  * Returns:    int - non-zero if not enough space
  67.  *
  68.  * Other Info:    For best performance you should add your points in as few
  69.  *        arrays of points as possible. The points in the array should
  70.  *        ideally be in a random order.
  71.  *        This call takes O(nlogn) time to add n points asssuming
  72.  *        good random order.
  73.  *        Never add the same array more than once to a Quadtree without
  74.  *        calling quadtree_Empty() first.
  75.  */
  76. int quadtree_Build(Quadtree q, Quadtree_Point *points, unsigned int num);
  77.  
  78.  
  79.  
  80. /* Procedure:    quadtree_Empty
  81.  *
  82.  * Description:    Removes all points from a Quadtree.
  83.  *
  84.  * Parameters:    Quadtree q
  85.  *
  86.  * Returns:    void
  87.  *
  88.  * Other Info:    This call takes time proportional to the number of
  89.  *        arrays of points.
  90.  */
  91. void quadtree_Empty(Quadtree q);
  92.  
  93.  
  94.  
  95. /* Procedure:    quadtree_Dispose
  96.  *
  97.  * Description:    Disposes of a quadtree (opposite of quadtree_New())
  98.  *
  99.  * Parameters:    Quadtree q
  100.  *
  101.  * Returns:    void
  102.  *
  103.  * Other Info:    This call takes time proportional to the number of
  104.  *        arrays of points.
  105.  */
  106. void quadtree_Dispose(Quadtree q);
  107.  
  108.  
  109.  
  110. /* type of procedure called when point inside bounding box */
  111. /* Procedure type:  Quadtree_Proc
  112.  *
  113.  * Parameters:    Quadtree_Point *point - point which is inside bounding box
  114.  *        void *private - private ptr passed to quadtree_Search()
  115.  *
  116.  * Returns:    void
  117.  *
  118.  * Other Info:  The private ptr with each point is useful for dealing with
  119.  *        a collision.
  120.  */
  121. typedef void (*Quadtree_Proc)(Quadtree_Point *point, void *private);
  122.  
  123.  
  124.  
  125. /* Procedure:    quadtree_Search
  126.  *
  127.  * Description:    Given a bounding box and a function to call, test to see
  128.  *        if any of the points in the Quadtree intersect with your
  129.  *        object.
  130.  *
  131.  * Parameters:    Quadtree q - tree to search
  132.  *        GeomI2   *min - minimum corner of bounding box
  133.  *        GeomI2     *max - maximum corner of bounding box
  134.  *             (undefined results if not ordered)
  135.  *        Quadtree_Proc furthertest -
  136.  *            This procedure is called for every point inside
  137.  *            the bounding box.
  138.  *        void *private - private ptr passed to furthertest procedure.
  139.  *
  140.  * Returns:    void
  141.  *
  142.  * Other Info:    The bounding box should not be changed by the function
  143.  *        furthertest.
  144.  *        This call takes O(lgn) time where n is the number of points.
  145.  */
  146. void quadtree_Search(Quadtree q, GeomI2 *min, GeomI2 *max,
  147.              Quadtree_Proc furthertest, void *private);
  148.  
  149.