Crash when inserting bounding box with triangular or zero area

[vhf]

I've been using this lib with great success but recently I've been hitting a bug with small bounding boxes crashing DDRT.

Isolating the issue from the stacktrace and getting to a minimal repro was pretty hard but after some debugging time I got there:

This is fine:

DynamicRtree.new(type: MerkleMap)
{:ok, t} = DynamicRtree.insert({0, [{9, 10}, {9, 10}]})
{:ok, t} = DynamicRtree.insert({1, [{9, 9}, {9, 9.1}]})

fine as well:

DynamicRtree.new(type: MerkleMap)
{:ok, t} = DynamicRtree.insert({0, [{9, 9.1}, {9, 9.1}]})

but this crashes (notice the bounding box is a really small triangle):

DynamicRtree.new(type: MerkleMap)
{:ok, t} = DynamicRtree.insert({1, [{9, 9}, {9, 9.1}]})

and this crashes as well (the bounding box has an area of 0):

DynamicRtree.new(type: MerkleMap)
{:ok, t} = DynamicRtree.insert({1, [{9, 9}, {9, 9}]})

The crash looks like this:

17:46:17.597 [error] GenServer DDRT terminating
** (ArgumentError) argument error
    :erlang.tl([])
    (ddrt 0.2.1) lib/ddrt/dynamic_rtree_impl/utils.ex:44: DDRT.DynamicRtreeImpl.Utils.combine_multiple/1
    (ddrt 0.2.1) lib/ddrt/dynamic_rtree_impl.ex:263: anonymous fn/3 in DDRT.DynamicRtreeImpl.add_entry/3
    (elixir 1.11.2) lib/map.ex:818: Map.update!/3
    (merkle_map 0.2.0) lib/merkle_map.ex:221: MerkleMap.update!/3
    (ddrt 0.2.1) lib/ddrt/dynamic_rtree_impl.ex:262: DDRT.DynamicRtreeImpl.add_entry/3
    (ddrt 0.2.1) lib/ddrt/dynamic_rtree_impl.ex:246: DDRT.DynamicRtreeImpl.insertion/3
    (ddrt 0.2.1) lib/ddrt/dynamic_rtree_impl.ex:79: DDRT.DynamicRtreeImpl.tree_insert/2
    (ddrt 0.2.1) lib/ddrt/dynamic_rtree.ex:506: DDRT.DynamicRtree.handle_call/3
    (stdlib 3.13.2) gen_server.erl:706: :gen_server.try_handle_call/4
    (stdlib 3.13.2) gen_server.erl:735: :gen_server.handle_msg/6
    (stdlib 3.13.2) proc_lib.erl:226: :proc_lib.init_p_do_apply/3

It only seems to appear when (1) the tree is empty, and (2) the bounding box is either a triangle or has a 0 area.

I gave solving this a few attempts but without success.

Here are two failing tests reproducing the issue:

    test "MerkleMap inserts a triangular bounding box without crash" do
      DynamicRtree.new(type: MerkleMap)

      {:ok, t} = DynamicRtree.insert({1, [{9, 9}, {9, 9.1}]})

      assert t == DynamicRtree.tree()

      root = t |> MerkleMap.get(:root)
      {ch, _root_ptr, root_box} = t |> MerkleMap.get(root)
      assert t |> Enum.to_list() |> length == t |> Enum.uniq() |> length
      assert length(ch) == 1
      assert root_box == [{9, 9}, {9, 9.1}]
    end

    test "MerkleMap inserts a zero area bounding box without crash" do
      DynamicRtree.new(type: MerkleMap)

      {:ok, t} = DynamicRtree.insert({1, [{9, 9}, {9, 9}]})

      assert t == DynamicRtree.tree()

      root = t |> MerkleMap.get(:root)
      {ch, _root_ptr, root_box} = t |> MerkleMap.get(root)
      assert t |> Enum.to_list() |> length == t |> Enum.uniq() |> length
      assert length(ch) == 1
      assert root_box == [{9, 9}, {9, 9}]
    end

[lubiepiwo]

Hey victor, we are busy those days, but I'll figure out what's happening before the new year :).

When I was writing the code i didn't expect triangles or zero area, guess the problem is at some utils function.

Anyways I would accept the PR If you fix it.