Точки пересечения прямой биссектрисы с прямоугольником

Question

Я пытался обернуться вокруг этого весь день ...

По сути, у меня есть координаты двух точек, которые всегда будут находиться внутри прямоугольника. Я также знаю положение углов прямоугольника. Эти две точки входа задаются во время выполнения.

Мне нужен алгоритм, чтобы найти 2 точки, где линия биссектрисы, образованная отрезком линии между данными точками, пересекает этот прямоугольник.

image http://f.cl.ly/items/0o3g1G0F0V120R3S2Q3H/coop.jpg

Некоторые детали:

На изображении выше A и B задаются своими координатами: A (x1, y1) и B (x2, y2). В основном, мне нужно найти положение C и D. Красный X - центр сегмента AB. Эта точка (назовем ее центром) должна быть на линии CD.

Что я сделал:

• найден центр:

  center.x = (A.x+B.x)/2;
  center.y = (A.y+B.y)/2;
  

• найден наклон CD:

  AB_slope =  A.y - B.y / A.x - B.x;
  CD_slope = -1/AB_slope;
  

Знание угла наклона центра и CD дало мне уравнение CD, и я попытался найти решение, попробовав положение точек на всех 4 границах прямоугольника. Однако по какой-то причине это не работает: каждый раз, когда у меня есть решение, скажем, для C, D строится снаружи или наоборот.

Вот уравнения, которые я использую:

• зная x:

  y = (CD_slope * (x - center.x)) + center.y;
  if y > 0 && y < 512: #=> solution found!
  

• зная y:

  x = (y - center.y + CD_slope*center.x)/CD_slope;
  if x > 0 && x < 512: #=> solution found!
  

Из этого я мог бы также получить еще один сегмент (скажем, я нашел C и знаю центр), но геометрия не смогла найти продолжение этого сегмента, пока он не пересекает другую сторону прямоугольника .

Обновлено для включения фрагмента кода

(см. Комментарии в основной функции)

typedef struct { double x; double y; } Point;

Point calculate_center(Point p1, Point p2) {
    Point point;
    point.x = (p1.x+p2.x)/2;
    point.y = (p1.y+p2.y)/2;
    return point;
}

double calculate_pslope(Point p1, Point p2) {
    double dy = p1.y - p2.y;
    double dx = p1.x - p2.x;
    double slope = dy/dx; // this is p1 <-> p2 slope

    return -1/slope;
}

int calculate_y_knowing_x(double pslope, Point center, double x, Point *point) {
    double min= 0.00;
    double max= 512.00;
    double y = (pslope * (x - center.x)) + center.y;

    if(y >= min && y <= max) {
        point->x = corner;
        point->y = y;
        printf("++> found Y for X, point is P(%f, %f)\n", point->x, point->y);
        return 1;
    }
    return 0;
}

int calculate_x_knowing_y(double pslope, Point center, double y, Point *point) {
    double min= 0.00;
    double max= 512.00;
    double x = (y - center.y + pslope*center.x)/pslope;

    if(x >= min && x <= max) {
        point->x = x;
        point->y = y;
        printf("++> found X for Y, point is: P(%f, %f)\n", point->x, point->y);
        return 1;
    }
    return 0;
}

int main(int argc, char **argv) {
    Point A, B;

    // parse argv and define A and B
    // this code is omitted here, let's assume:
    // A.x = 175.00;
    // A.y = 420.00;
    // B.x = 316.00;
    // B.y = 62.00;

    Point C;
    Point D;

    Point center;
    double pslope;

    center = calculate_center(A, B);
    pslope = calculate_pslope(A, B);

    // Here's where the fun happens:
    // I'll need to find the right succession of calls to calculate_*_knowing_* 
    // for 4 cases: x=0, X=512 #=> call calculate_y_knowing_x
    // y=0, y=512 #=> call calculate_x_knowing_y
    // and do this 2 times for both C and D points.
    // Also, if point C is found, point D should not be on the same side (thus C != D)

    // for the given A and B points the succession is:
    calculate_y_knowing_x(pslope, center, 0.00, C);
    calculate_y_knowing_x(pslope, center, 512.00, D);
    // will yield: C(0.00, 144.308659), D(512.00, 345.962291)

    // But if A(350.00, 314.00) and B(106.00, 109.00)
    // the succesion should be:
    // calculate_y_knowing_x(pslope, center, 0.00, C);
    // calculate_x_knowing_y(pslope, center, 512.00, D);
    // to yield C(0.00, 482.875610) and D(405.694672, 0.00)


    return 0;
}

Это код С.

Примечания:

• Изображение было нарисовано от руки.
• Система координат повернута на 90 ° против часовой стрелки, но не должна влиять на решение
• Я ищу алгоритм на C, но могу читать другие языки программирования
• Это 2D проблема

Answer 1

У вас есть уравнение для CD (в форме (y - y0) = m (x - x0) ), которое вы можете преобразовать в форму y =mx + c .Вы также можете преобразовать его в форму x = (1 / m) y - (c / m) .

Затем вам просто нужно найти решения, когда x = 0, x = 512 , y = 0 , y = 512 .

Answer 2

Следующий код должен помочь:

typedef struct { float x; float y; } Point;
typedef struct { Point point[2]; } Line;
typedef struct { Point origin; float width; float height; } Rect;
typedef struct { Point origin; Point direction; } Vector;

Point SolveVectorForX(Vector vector, float x)
{
    Point solution;
    solution.x = x;
    solution.y = vector.origin.y +
        (x - vector.origin.x)*vector.direction.y/vector.direction.x;
    return solution;
}

Point SolveVectorForY(Vector vector, float y)
{
    Point solution;
    solution.x = vector.origin.x +
        (y - vector.origin.y)*vector.direction.x/vector.direction.y;
    solution.y = y;
    return solution;
}

Line FindLineBisectorIntersectionWithRect(Rect rect, Line AB)
{
    Point A = AB.point[0];
    Point B = AB.point[1];
    int pointCount = 0;
    int testEdge = 0;
    Line result;
    Vector CD;

    // CD.origin = midpoint of line AB
    CD.origin.x = (A.x + B.x)/2.0;
    CD.origin.y = (A.y + B.y)/2.0;

    // CD.direction = negative inverse of AB.direction (perpendicular to AB)
    CD.direction.x = (B.y - A.y);
    CD.direction.y = (A.x - B.x);

    // for each edge of the rectangle, check:
    // 1. that an intersection with CD is possible (avoid division by zero)
    // 2. that the intersection point falls within the endpoints of the edge
    // 3. if both check out, use that point as one of the solution points
    while ((++testEdge <= 4) && (pointCount < 2))
    {
        Point point;

        switch (testEdge)
        {
            case 1: // check minimum x edge of rect
                if (CD.direction.x == 0) { continue; }
                point = SolveVectorForX(CD, rect.origin.x);
                if (point.y < rect.origin.y) { continue; }
                if (point.y > (rect.origin.y + rect.height)) { continue; }
                break;

            case 2: // check maximum x edge of rect
                if (CD.direction.x == 0) { continue; }
                point = SolveVectorForX(CD, rect.origin.x + rect.width);
                if (point.y < rect.origin.y) { continue; }
                if (point.y > (rect.origin.y + rect.height)) { continue; }
                break;

            case 3: // check minimum y edge of rect
                if (CD.direction.y == 0) { continue; }
                point = SolveVectorForY(CD, rect.origin.y);
                if (point.x < rect.origin.x) { continue; }
                if (point.x > (rect.origin.x + rect.width)) { continue; }
                break;

            case 4: // check maximum y edge of rect
                if (CD.direction.y == 0) { continue; }
                point = SolveVectorForY(CD, rect.origin.y + rect.height);
                if (point.x < rect.origin.x) { continue; }
                if (point.x > (rect.origin.x + rect.width)) { continue; }
                break;
        };

        // if we made it here, this point is one of the solution points
        result.point[pointCount++] = point;
    }

    // pointCount should always be 2
    assert(pointCount == 2);

    return result;
}

Answer 3

Мы начинаем с центральной точки C и направления AB, D:

C.x = (A.x+B.x) / 2
C.y = (A.y+B.y) / 2
D.x = (A.x-B.x) / 2
D.y = (A.y-B.y) / 2

, тогда, если P - точка на линии, CP должен быть перпендикулярен D. Уравнение линии:

DotProduct(P-C, D) = 0

или

CD = C.x*D.x + C.y*D.y
P.x * D.x + P.y * D.y - CD = 0

для каждого из четырех ребер квадрата, у нас есть уравнение:

P.x=0 -> P.y = CD / D.y
P.y=0 -> P.x = CD / D.x
P.x=512 -> P.y = (CD - 512*D.x) / D.y
P.y=512 -> P.x = (CD - 512*D.y) / D.x

За исключением вырожденных случаев, когда 2точки совпадают, только 2 из этих 4 точек будут иметь Px и Py между 0 и 512. Вам также нужно будет проверить для особых случаев Dx = 0 или Dy = 0.