#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    2
    Rep Power
    0

    Geometric search/intersection problem


    Hello guys.

    I decided to post this in the C forum since its what I use, but its really a general problem.

    I need to find if a any given point in space (2d/3d) is inside an irregular region formed by rectangles (or cubes in 3d).

    I have several different boxes with its coordinates. All of the boxes overlap with at least another box, meaning its a closed region with no holes. I want to form one big region from all these boxes and then try to find if points lie inside or outside.

    I have already developed an implementation that uses search trees (quadtrees) and is efficient in looking through each of the boxes to see if the points are there. Now, some of the problems I want to solve have millions of boxes and millions of points, so I'm looking for ways of say having one big region. In 2d this could be a polygon for example which is not hard to do, but not for 3d.

    Basically what I would like in the end is to form a big region where I can quickly get candidate points, which I can then process in detail with my search trees algorithms.

    I've been developing the search tree algorithms for the last few days so my head is pretty biased towards that at the moment and I need some external thinking.

    Any ideas?
    Thanks a lot in advance!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,364
    Rep Power
    1870
    Cross-posted here and here
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    2
    Rep Power
    0
    Originally Posted by salem
    Cross-posted here and here
    Sorry. Yes, I forgot to mention I also posted the question in the dreamincode.net and cprogramming.com forums. Didn't mean to flood the forums, I just thought I would get different answers this way. Thanks for pointing it out.
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,708
    Rep Power
    480
    Don has written about three fifths of The Art of Computer Programming by Knuth. If he's addressed geometrical algorithms this would be quite a good reference. The programs would be written in MIX or in MMIX which could be a bit challenging at first to follow---just because these are low level languages.

    Robert Sedgwick's books are more accessible.

    Are your boxes convex? It's easier if they are.

    Maybe you could sort the nodes in each dimension (storing all n, after all, memories are large and cheap these days) and use successive binary searches. 3D FFT time goes to heck on the third dimension because the cache hit rate sinks to nil.

    With an ordered convex polygon,
    I expect you know that
    for plane vectors
    Code:
           A
    C                       P
              B
    Where signum returns the sign of, and cross represents an inorder cross product
    P is in triangle ABC if
    signum((B-C)cross(P-C))==signum((A-B)cross(P-B))==signum((C-A)cross(P-A))
    otherwise you wouldn't attempt this algorithm.
    Which I'm sure can be written as the determinant of some matrix.

    In 3D, I'd check signs of dot products of face normals against the vector from center of face to P. Since the face could be warped, this would only work for volumes composed of planar surfaces. Triangles. So it would work for all tetrahedra (the case that interests me most often) and a constrained set of other volumes.

    Check with Sedgwick.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    Originally Posted by b49P23TIvg
    Don has written about three fifths of The Art of Computer Programming by Knuth. If he's addressed geometrical algorithms this would be quite a good reference. The programs would be written in MIX or in MMIX which could be a bit challenging at first to follow---just because these are low level languages.

    Robert Sedgwick's books are more accessible.

    Are your boxes convex? It's easier if they are.
    I believe the standard reference for this type of problem is "the Dutch book," i.e., Computational Geometry: Algorithms and Applications by de Berg, Cheong, van Kreveld, and Overmars. (I just searched Google to get the exact title and authors, forgetting that the actual book was on the table in front of me!)

    Anyway, it doesn't seem that the OP's problem is reducible to a single convex polyhedron. However, the Dutch book does state that while the problem of efficient point location in a general subdivision in high-dimensional space is open, efficient solutions exist for rectangular subdivisions, which they don't define but I'm guessing are similar or identical to what the OP is trying to do. The references they give are:
    • "Two- and three-dimensional point location in rectangular subdivisions," by de Berg, van Kreveld and Snoeyink (J. Algorithms, 1995)
    • "Rectangular point location in d dimensions with applications," by Edelsbrunner, Haring, and Hilbert (Comput. J., 1986)

IMN logo majestic logo threadwatch logo seochat tools logo