`spaceSplit(tgeompoint, integer)` returns different results with bitmatrix on vs off. about mobilitydb

[estebanzimanyi]

After I posted my answer, Maxime found a great solution that he will explore
https://stackoverflow.com/questions/41195973/how-to-use-bresenhams-line-drawing-algorithm-with-sub-pixel-bias
We will keep you posted !

[LauJosefsen]

Can confirm it is working with latest development branch. Closing the issue :)

[estebanzimanyi]

Many thanks for reporting this bug and for your targeted example that helped us to understand the problem. After analysis I didn't find an easy fix for it :-(
The Bresenham line algorithm that is used for constructing the bitmap implicitly assumes that the points for determining the selected cells are in the center of the cell which is obviously not the case, this is a mistake in our design. In your example the cells are (1,0) and (0,1) which is a diagonal and then it misses the cell with the red segment in your figure.
How much gain is obtained in your use case when using the bitmap ? Is it foreseeable not to use it ? Any other suggestion for constructing the bitmap in a fast way ? A possibility that I see is to do not use the Bresenham algorithm and set all the cells in the bounding box defined by the selected cells of each segment. In your example, from the cells of the segment (1,0) and (0,1) it will select all 4 cells (0,0), (0,1), (1,0) and (1,1). However, the result of this method is that it will add many false positives and then we lose the advantage of using the bitmap.
Alas, in my answer there are many questions and not any answer :-( If you want, we can continue this conversation offline, you can easily find my email address and we can brainstorm for finding a solution to this problem.

[LauJosefsen]

Hi again.

Our use case is splitting trajectories of vessels in a day to day basis. We split them into a 5 km grid as part of an ETL process, where future queries then process the split trajectories further. On the limited data we have, it seems that running without bitmatrix is fine for our use case. It added ~20 seconds to a ~30 second query, but as it is ETL queries it doesn't really matter in the big picture. I just thought I'd raise the issue in here, as it was a bit unexpected, and we spent a fair amount of time trying to find the cause to a data artifact in our output data.

As for proposals, I must admit I am fairly new to the Moving Object world. The only thing I can think if is maybe using some form of thick line approach, with a line thickness of the space split size? It would probably still produce some false positives though? I found this if interested: http://homepages.enterprise.net/murphy/thickline/index.html

But yes, I'm afraid that using a bounding box for trajectories will involve too many false positives, as bounding boxes of trajectories, at least in our experience, grow in spatial area very quickly as trajectories become longer. This is the main reason we split the trajectories into the 5km spatial split to begin with, as the large bounding boxes is a nightmare in r-trees as well.

I don't know how much help I can provide in discussing a solution for the problem, but I will gladly try my best if you would like to discuss something over email or on this issue. :)