线相交

Question

如何判断一条线是否被多边形截断

Answer 1

根据您到底想要什么（我将假设一个线段，因为我本周刚刚编写了该代码），您可以将其分为两部分：

首先，我建议对行进行编码，

a*X + b*Y - c = 0

因为该形式没有行的极端情况例如 X=5、Y=4 或 X=3*Y。

• 测试直线是否与多边形的任意边相交
  • 测试两条线的端点是否位于另一条线的相对两侧。 建议的形式只需检查 LHS 的极性即可轻松实现此目的
• 如果线上的点位于多边形内部，
  • 测试从输入线上的某个点到多边形外部的一条线是否在奇数个点处与多边形相交。 请注意，您需要检查多个位置是否出现相同的点，并且由于 FP 错误，这无法通过精确匹配测试来完成。

Answer 2

这个问题有点含糊，但我们还是尝试一下：

假设直线上的点 (x,y) 由方程 Ax + By + C = 0 定义。
那么我们显然可以通过评估来确定点 (x,y) 是否在线上
Ax + By + C。如果该点不在直线上，则 Ax + By + C 的符号告诉我们该点位于直线的哪一侧。
因此，通过检查多边形每个顶点 (x,y) 的表达式 Ax + By + C 的符号，我们可以确定多边形的所有点是否在线的同一侧。

（一个稍微不同的问题是确定多边形是否与线段相交。）

Answer 3

中找到的此实现中阅读合理的答案

Point  * intersection2(Point * _line1, Point * _line2) {

Point  p1,p2,p3,p4;
p1=_line1[0]; p3=_line2[0];
p2=_line1[1]; p4=_line2[1];

// Store the values for fast access and easy
// equations-to-code conversion
double x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
double y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;

double A1 = y2-y1;
double B1 = x1-x2;
double C1 = (A1*x1)+(B1*y1);

double A2 = y4-y3;
double B2 = x3-x4;
double C2 = A2*x3+B2*y3;

double det = A1*B2 - A2*B1;

if (det==0){
    return NULL;
}else{
    // Return the point of intersection
    Point  * ret = new CvPoint2D64f ();
    ret->x = (B2*C1 - B1*C2)/det;
    ret->y = (A1*C2 - A2*C1)/det;
    return ret;

}

您可以从某些网页参考

。
C++ 示例：几何概念、线相交及其应用、2D 绘图
通过 lbackstrom
来自 ucancode 网站

Answer 4

您需要坐标图上多边形的点以及直线的斜率以及 x 和 y 截距来查找该信息。 从那里开始就是简单的数学计算。