How to fit a line in a rectangle

Question

I'm trying to convert the python algorithm (here: Extending a line segment to fit into a bounding box) to my iPhone application.. but it only works when my startPoint.x > then endPointx

What is to change here? I don't get it..

If I draw a line from top-left to bottom right it works! But If I draw a line from top-right to bottom-left it fails. So it only works in one direction.. I think I have to change some variables if its from right to left

MIN is (0,0) and MAX depends on the device but for iPhone Retina (300,568)

    - (NSMutableArray *) extendAlgorithm:(CGPoint)start withEnd:(CGPoint)end withBorderMin:(CGPoint)min andBorderMax:(CGPoint)max {

    int x1 = (int) start.x;     int y1 = (int) start.y;
    int x2 = (int) end.x;       int y2 = (int) end.y;
    int xmin = (int) min.x;     int ymin = (int) min.y;
    int xmax = (int) max.x;     int ymax = (int) max.y;

    if(y1 == y2) {
        return [[NSMutableArray alloc] initWithObjects:
                [NSNumber numberWithDouble:xmin],
                [NSNumber numberWithDouble:y1],
                [NSNumber numberWithDouble:xmax],
                [NSNumber numberWithDouble:y1],
                nil];
    }

    if(x1 == x2) {
        return [[NSMutableArray alloc] initWithObjects:
                [NSNumber numberWithDouble:x1],
                [NSNumber numberWithDouble:ymin],
                [NSNumber numberWithDouble:x1],
                [NSNumber numberWithDouble:ymax],
                nil];
    }

    double y_for_xmin = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
    double y_for_xmax = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);

    double x_for_ymin = x1  + (x2 - x1) * (ymin - y1) / (y2 - y1);
    double x_for_ymax = x1  + (x2 - x1) * (ymax - y1) / (y2 - y1);

    if(ymin <= y_for_xmin <= ymax) {

        if(xmin <= x_for_ymax <= xmax) {
            return [[NSMutableArray alloc] initWithObjects:
                    [NSNumber numberWithDouble:xmin],
                    [NSNumber numberWithDouble:y_for_xmin],
                    [NSNumber numberWithDouble:x_for_ymax],
                    [NSNumber numberWithDouble:ymax],
                    nil];
        }

        if(xmin <= x_for_ymin <= xmax) {
            return [[NSMutableArray alloc] initWithObjects:
                    [NSNumber numberWithDouble:xmin],
                    [NSNumber numberWithDouble:y_for_xmin],
                    [NSNumber numberWithDouble:x_for_ymin],
                    [NSNumber numberWithDouble:ymin],
                    nil];
        }
    }

    if(ymin <= y_for_xmax <= ymax) {

        if(xmin <= x_for_ymin <= xmax) {
            return [[NSMutableArray alloc] initWithObjects:
                    [NSNumber numberWithDouble:x_for_ymin],
                    [NSNumber numberWithDouble:ymin],
                    [NSNumber numberWithDouble:xmax],
                    [NSNumber numberWithDouble:y_for_xmax],
                    nil];
        }

        if(xmin <= x_for_ymax <= xmax) {
            return [[NSMutableArray alloc] initWithObjects:
                    [NSNumber numberWithDouble:x_for_ymax],
                    [NSNumber numberWithDouble:ymax],
                    [NSNumber numberWithDouble:xmax],
                    [NSNumber numberWithDouble:y_for_xmax],
                    nil];
        }
    }

    return nil;
}

Will it be hard for you to get there with debugger or is there any problem inspecting the values ? — A-Live, Mar 26 '13 at 17:38
Let me give you a hint then, you don't have sufficient conditions to cover all the cases. — A-Live, Mar 26 '13 at 18:05

Martin R · Accepted Answer · 2013-03-26T19:42:59.623

if (ymin <= y_for_xmin <= ymax)

does not do do what you expect (perhaps in Python, but definitely not in C), you have to write this as

if (ymin <= y_for_xmin && y_for_xmin <= ymax)

I don't know if your algorithm covers all cases, so I tried to find an algorithm independently. This is what I got:

- (NSArray *) extendAlgorithm:(CGPoint)start withEnd:(CGPoint)end withBorderMin:(CGPoint)min andBorderMax:(CGPoint)max
{
    CGFloat u1 = MAXFLOAT;
    CGFloat u2 = -MAXFLOAT;
    CGFloat tmp;
    if (end.x != start.x) {
        tmp = (max.x - start.x)/(end.x - start.x);
        if (tmp > 0 && tmp < u1)
            u1 = tmp;
        else if (tmp < 0 && tmp > u2)
            u2 = tmp;
        tmp = (min.x - start.x)/(end.x - start.x);
        if (tmp > 0 && tmp < u1)
            u1 = tmp;
        else if (tmp < 0 && tmp > u2)
            u2 = tmp;
    }
    if (end.y != start.y) {
        tmp = (max.y - start.y)/(end.y - start.y);
        if (tmp > 0 && tmp < u1)
            u1 = tmp;
        else if (tmp < 0 && tmp > u2)
            u2 = tmp;
        tmp = (min.y - start.y)/(end.y - start.y);
        if (tmp > 0 && tmp < u1)
            u1 = tmp;
        else if (tmp < 0 && tmp > u2)
            u2 = tmp;
    }
    CGPoint newStart, newEnd;
    newStart.x = start.x + u2 * (end.x - start.x);
    newStart.y = start.y + u2 * (end.y - start.y);
    newEnd.x = start.x + u1 * (end.x - start.x);
    newEnd.y = start.y + u1 * (end.y - start.y);
    NSLog(@"%@, %@", NSStringFromCGPoint(newStart), NSStringFromCGPoint(newEnd));

    return [[NSArray alloc] initWithObjects:
            [NSNumber numberWithDouble:newStart.x],
            [NSNumber numberWithDouble:newStart.y],
            [NSNumber numberWithDouble:newEnd.x],
            [NSNumber numberWithDouble:newEnd.y],
            nil];
}

(The idea is to consider the line

(x, y) = (start.x, start.y) + u * (end.x - start.x, end.y - start.y)

and then determine the parameters u1, u2 where the line crosses the boundary.)

@Christian'fuzi'Orgler: I tried to figure something out, I hope that works. — Martin R, Mar 26 '13 at 19:44

score 0 · Answer 2 · answered Mar 26 '13 at 17:36

0

I didn't check anything about the algorithm, but the thing that jumps out are these lines:

double y_for_xmin = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
// ...

The end of that expression is an integer divide (you cast xmin, x1, x2 etc to ints). Those will have integer results, truncated. So if you're expecting something like 1/2 == 0.5, you'll get surprised by (int)0 there.

Try declaring the stack vars as CGFloat, which is how they are in the CGPoint structs.

answered Mar 26 '13 at 17:36

danh

62,181
10
95
136

I tried it with CGFloats,.. no other result, look at the top: I edited my question because some lines work! – Christian 'fuzi' Orgler Mar 26 '13 at 17:46

How to fit a line in a rectangle

2 Answers2