Re: [geomesa-users] Collision detection in large regions

[Chris Eichelberger <cne1x@xxxxxxxx>]

Eric,

This is an interesting problem!

My intuition for now is that this could be done in a single-pass
map-reduce/Spark type job that divides the entire n^2 problem into k
much smaller m_i^2 problems (where, with luck, sum_1^k { m_i^2 } <<
n^2).

Imagine something like this:

1.  MAP:  (_, geometry) -> 
      (CellA(geometry), geometry), 
      (CellB(geometry), geometry)

    Each geometry is mapped to *two* cells.  Each of these spatial
partitions is offset from the other by 50% in both dimensions.  This
ensures that, if A and B are geometries that are within radius R in
space, they will both map to either CellA together or CellB together
(assuming that the minimum width, height of CellA and CellB are at least
R).  There will be some pairs of geometries that necessarily end up
together in more than one bin.

2.  REDUCE:  (cell, {geometries}) ->
      [exhaustively consider pairwise combinations of 'geometries'
      for intersection/collision]

3.  REDUCE:  deduplicate

This scheme will work badly where the data clump significantly, as you
would expect.  In that case, I bet you could fairly easily adapt the
method to create equivalence-classes of points, and operate on that
reduced data set (provided there are mappings back from the equivalence
classes to the original data).

Anyway, it's just a thought.  As you find better solutions, please share
them back with the group!

Thanks.

Sincerely,
  -- Chris


On Tue, 2016-03-01 at 13:05 +0100, Eric Ahlberg wrote:
> Hi,
> 
> I have an application where I intend to perform collision detection between items in a very large region (potentially the whole world). To avoid calculating all possible combinations, I intend only to detect collisions between nearby items.
> 
> With GeoMesa and Spark, is it possible to construct a query for this kind of use case in an efficient manner or will it become a simple brute force search? What I'd like is something like "for all items, perform collision detection in a range of X meters". 
> 
> Greatful for any kind of input or pointers to other suitable alternatives!
> _______________________________________________
> geomesa-users mailing list
> geomesa-users@xxxxxxxxxxxxxxxx
> To change your delivery options, retrieve your password, or unsubscribe from this list, visit
> https://www.locationtech.org/mailman/listinfo/geomesa-users