Re: aggregating triangles into spaces

[Seth Teller <teller@csail.mit.edu>]

[bmg'ers:  please remember to use descriptive subject lines
("Re: " doesn't count) when sending anything to bmg@ for
archiving.]

vitaly,

why not use a simple greedy algorithm?  for example, put every
triangle on a queue, with its mark bit set to zero.  then

while there are triangles on the queue:
  dequeue a triangle T
  if it is marked, continue
  otherwise, initialize a new space S to contain only T
  while
    there is an unmarked neighbor N of some triangle T_s in S
      with the same type as T
    AND (area(S) + area(N) <= some predetermined threshold)
    AND taking the union of space S and neighbor N is convex
      S = S union N
      mark N

this will find many groups of 2, 3, or 4 triangles, won't it?
so it will reduce the number of spaces by a factor of at least
2, probably many more.

once you have this basic algorithm running, you can hand off
these much larger (& fewer!) spaces to patrick, and continue
your work on a more sophisticated algorithm.  even the greedy
algorithm, with a few adjustments, might be sufficient.  for
example, note that your constraint #1 implies constraint #2.
(constraint #3 is satisfied by the second predicate in the
inner while loop above.)

prof. t.

vkulikov@mit.edu wrote:
> 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?