[no subject]

[vkulikov@mit.edu]

Yes, I know that it would be better to have triangles of the same type 
assembled into large pieces. I was thinking about an algorithm that would do 
that in such a way that:

1. all resultant pieces were convex (to optimize the pathfinder algorithm);
2. no piece was completely contained within another (“multiple-contours” 
problem);
3. all pieces had approximately equal dimensions (to ensure the granularity of 
the path throughout the basemap).

It turned out that implementation of an algorithm with all of the three 
properties above would be quite complex. This is why Patrick and I decided to 
test the pathfinder algorithm on a raw set of basemap triangles to see whether 
we actually needed all those optimizations. 

Now, I recommend that we forget about requirements (1) and (3) for now, and 
simply make sure that we have a relatively small number of pieces of the same 
type such that no piece is completely contained within another. This is a 
simpler problem, I have thoughts how to solve it, and I will try to have a 
working solution by Tuesday.

Vitaly

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Patrick Nichols wrote:

It does turn out from a memory perspective that my implementation would 
greatly benefit from collecting triangles into spaces. 

yes, absolutely.  this is something we've planned to do
from the beginning.  indeed, my estimate is that we can
represent all exterior spaces with something like a
thousand non-convex contours, each of which has the same
space type throughout (sidewalk, road, grass, etc.) and
each of which is the union of tens or hundreds of triangles.

vitaly, comments on feasibility of doing this in the near term?