triangulating a triangle into a grid

Question

Is there an algorithm for dividing a triangle that may span multiple grid elements into multiple triangles, where there are no triangles that span multiple grid elements?

I've included a crappy hand-drawing of a triangle in a 2x2 grid being diced into seven smaller triangles.

Answer 1

I see it like this:

Your triangle is 3 lines closed polygon
order of points gives you winding rule (CW or CCW)

1. cut all lines by grid lines

   but still leave triangle as single closed polygon and do not change winding

2. split polygon to few line lists

   just group together all lines belonging to the same grid cell so all point is inside or on edge of the cell. Again do not change winding !!!

3. convert line lists to closed polygons

   start with first line in the first line list in its direction. If it is joining any line in actual list continue with it. If not then continue with cell edge line in the same winding direction until hit another line point or cell corner.

   Repeat this until closed polygon is formed for this cell (hit already used line/point)). Process other cells in the same way

4. now you have closed convex polygon list

   so just split it to triangles (triangle fan)