# How can I pack $45-45-90$ triangles inside an arbitrary shape ?

If I have an arbitrary shape, I would like to fill it only with $45-45-90$ triangles.

The aim is to get a Tangram look, so it's related to this question.

Starting with $45-45-90$ triangles would be an amazing start. After the shape if filled I imagine I could pick adjacent triangles, either $2$ or $4$ and draw squares and parallelograms instead, but just getting the outline estimated with packed $45-45-90$ triangles would be great.

How do I get started ?

EDIT @J.M.'s comment makes perfect sense, which means I should first make sure my shape is suited for this. Here's a sketch I did to illustrate this:

The black shape is the 'arbitrary shape', the blue path is the path I should be filling.

So far, I see the first step is to 'estimate' arbitrary paths with lines at right or 45 degree angles. The second step would be the initial question, packing 45-45-90 triangles into the shape.

Hints for estimating random angles lines with 45/90 degrees angled lines or 45-45-90 triangle packing ?

UPDATE2

I've gone ahead with a naive approach to estimate an arbitrary path(outline) using only straight or diagonal(45 degrees) lines.

function estimate45(points:Vector.<Point>):Vector.<Point> {
var result:Vector.<Point> = new Vector.<Point>();
var pNum:int = points.length,angle:Number,pi:Number = 3.141592653589793,qpi:Number = pi*.25,d:Number = 0;
for(var i:int = 0 ; i < pNum ; i++){
if(i == 0) angle = Math.atan2(points[i].y,points[i].x);
else {
angle = Math.atan2(points[i].y-points[i-1].y,points[i].x-points[i-1].x);
d = Math.sqrt((points[i].x-points[i-1].x)*(points[i].x-points[i-1].x)+(points[i].y-points[i-1].y)*(points[i].y-points[i-1].y))
}
//constraint to 45 (1. scale to values between 0,1 (/qpi) 2. round, 3. do whatever(convert to degrees/radians as needed)
angle = (Math.round(angle/qpi)) * 45 / 57.2957795;
if(i == 0) result.push(new Point(Math.cos(angle)*d,Math.s(angle)*d));
else       result.push(new Point(result[i-1].x+Math.cos(angle)*d,result[i-1].y+Math.s(angle)*d));
}
return result;
}


I loop trough the the path (an ordered list of points) and I calculate the angle and radius of each line(cartesian to polar I think). Then I 'round' the angle to 45 degrees, and draw a line to a 45 degrees constrained version of the original angle, and keep the same length for the line.

This isn't very good way to do it, especially for consecutive lines with similar angles.

Here are some tests:

The faded red is the original, the green is the estimation.

@Américo Tavares's suggestion is great though. I could use this approach for bitmap graphics too, not just vector graphics.

If I would go with this approach, I imagine I would do something like:

get a mosaic(create a grid of boxes to cover the size of the shape)

boxes_xnum = floor(w/box_size)
boxes_ynum = floor(h/box_size)
for(y to boxes_ynum):
for(x to boxes_xnum):

for box in grid:
if(box.nonAlphaPixels/box.totalPixels > .75): fullBox
else:
checkDiagonalType()//is it like this / or like this \
checkFillSide()//which of the two sides should be filled
//which means I should check for something constrained to 45 degrees angles \| or _\ or |/ or /_
//in the case of halfs go for random diagonal ?


when I loop though the pixels of a box, keep a pixel count per box 'quadrant'(top-left). If the non transparent pixels in one quadrant in larger than .5 or .75 it's marked as used. Based on how many and which of the 4 quadrants are used in a box, a diagonal with direction is used.

Does this make sense, or am I over complicating this ?

-
The shape can't be that arbitrary, the only angles you can manage would be multiples of 45 degrees. –  Ｊ. Ｍ. Sep 15 '10 at 12:13
It seems to me that one has to define the required resolution of the mesh, i.e. the base length of the minimum triangle. –  Américo Tavares Sep 15 '10 at 13:13
It's not mentioned in the question, but I guess you would like to use as few triangles as possible to accomplish this? –  Larry Wang Sep 15 '10 at 15:20
Do you require your 45-45-90 triangle to be bigger than a certain size? Or the number of such triangles be limited? Otherwise you could just perhaps "pixellate" your figure, i.e. approximate it with a set of sufficiently small squares. I see I just repeated what Kaestur said. –  Aryabhata Sep 15 '10 at 17:55
What Moron stopped short of saying outright is that you can lay your image on top of a square grid, then shade in all squares that are part of the shape (filled or >half filled, for small enough squares it doesn't matter), and bisect them to get the triangles you want. I don't write this as an answer because although it answers your question as written, I think it also suggests some clarifying edits you may wish to make to bring it closer to your 'real' question. –  Larry Wang Sep 15 '10 at 18:32