Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

hand

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: crescent

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

hand 45

@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):
        grid.addBitmap(copyPixels(source,x*box_size,y*box_size,box_size,box_size));//copypixels(source,x,y,width,height)

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 ? 

If I think about this better,
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.

solve

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

share|improve this question
2  
The shape can't be that arbitrary, the only angles you can manage would be multiples of 45 degrees. –  J. M. Sep 15 '10 at 12:13
5  
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
1  
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
2  
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
3  
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
show 2 more comments

1 Answer 1

up vote 4 down vote accepted

I show here my interpretation of your question and comments until now:

alt text

One has to define the triangle sides lengths (one is of course enough) depending on the resolution one needs. In the figure I approximated the red shape by the green right triangles with two equal angles. The shape boundary determines the triangles over or closed to it, the criteria being that at least 50% of the triangle area lies inside the shape. The inner triangles can be chosen more freely.

Remark: there are a few mistakes in the sketch.

share|improve this answer
    
Once the borders are 'drawn' with 45-45-90 triangles, any hints on how to fill the remaining boxes(pseudo-random sizes) ? –  George Profenza Sep 22 '10 at 15:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.