Re: Re: aggregating triangles into spaces

[vkulikov@mit.edu]

yes, it is a good idea to implement a simpler algorithm to make sure that 
Patrick's program works. i'll do my best to implement the algorithm below
today. i'am also ready to support Patrick and BMG throughout this month.

vitaly

p.s. sorry for "no subject", i think i just forgot to fill in the subject 
field.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

[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.