线的平分线与矩形的交点

Question

整整一天我都在试图理解这个问题...

基本上，我有两个点的坐标，它们总是在矩形内部。我还知道矩形四个角的位置。这两个点是在运行时给定的。

我需要一个算法来找到这条线段的平分线与矩形相交的2个点。

以下是一些细节：

在上图中，A和B由它们的坐标给出：A(x1, y1)和B(x2, y2)。基本上，我需要找到C和D的位置。 红色X是AB线段的中心点。这个点（让我们称之为中心）必须位于CD线上。

我的做法：

• found the center:

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

• found CD slope:

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

我知道中心和CD斜率后，得到了CD的方程，然后尝试通过在矩形的4个边界上尝试点的位置来找到解决方案。 但是，出于某种原因它不起作用：每次当我有一个解决方案，比如对于C，D就会被绘制在外面，反之亦然。

以下是我使用的方程：

• knowing x:

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

• knowing 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;
}

这是C代码。

注：

• 图片是手绘的。
• 坐标系逆时针旋转90度，但不会对解决方案产生影响。
• 我需要用C语言编写算法，但我也可以阅读其他编程语言。
• 这是一个二维问题。

- apann

---

你手动尝试过一些简单的例子吗？这是你（或在这里的任何人）需要做的，以找出错误所在。 - Oliver Charlesworth

我认为这个问题严格来说是数学问题。是否应该将其转移到Math.SE？ - jweyrich

@jweyrich，我不这么认为。这是一个编程问题。 - Tomas

@apann，继续加油，原则很简单，你只需要仔细处理所有可能性和情况。然后，也许需要进行仔细的调试。祝你好运。 - Tomas

公平地说，这是一个简单的代数问题；它只是两条直线的交点。编程实现只是小问题。 - Oliver Charlesworth

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 时的解决方案。

- Oliver Charlesworth

Answer 2

我们从中心点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

除了两个点重合的退化情况外，这4个点中只有2个点的P.x和P.y都在0到512之间。您还需要检查特殊情况D.x = 0或D.y = 0。

- Jeffrey Sax

---

你能否编辑一下，使用我图中的相同符号表示吗？"中心点C"这个概念有些让我困惑。谢谢！ - apann

Answer 3

以下代码应该可以解决问题：

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;
}

- e.James

---

我使用它是因为我认为它读起来更好。如果你有更好的选择，我很乐意看看（无恶意 - 我自己对循环和开关也不是100％满意）。 - e.James

@e.James：我正在使用与您发布的内容类似的东西（除了我使用CD的斜率而不是方向）。问题是...使用这段代码，我可能会让C和D在矩形的同一侧，基本上C将与D在同一点。 - apann

@apann：我测试过了，它是有效的。C和D肯定是独特的点。一定有微妙的差别。 - e.James

实际上，看看我的“循环和开关”代码。它可能不太好看，但它处理了你在问题末尾提到的“有趣”部分。你最终会得到4个可能的点，但只有其中2个是C和D的有效解决方案。 - e.James

哎呀，没错！我对 switch 里面的 continue 指令感到困惑 :| - apann

那段代码需要一些优化 :)。如果你有更简洁的解决方案，请发表出来！ - e.James