线段相交

Question

如何确定一条直线是否被多边形所截？

- pradeep

---

请提供更多信息。 - Chathuranga Chandrasekara

请稍微澄清一下问题。您是指2D线段与2D多边形的相交吗？还是指一条穿过2D多边形所在平面的3D直线，并且直线与平面的交点也在多边形内部？这个多边形是任意的还是我们可以假设它是凸多边形？ - A. Levy

你在使用哪种编程语言？许多编程语言都内置了相关库。 - Ethan Heilman

Answer 1

您可以从某些网页中找到这个实现，并阅读一个合理的答案。

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 2

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

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

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

- Accipitridae

Answer 3

根据你需要的具体内容（我将假设是线段，因为我上周刚写了那段代码），你可以分成两个部分来实现：

首先，我建议将线段编码为

a*X + b*Y - c = 0

因为该表单对于像X=5，Y=4或X=3*Y之类的行没有任何特殊情况。

• 测试线是否与多边形的任何一侧相交
  • 测试两条线段的末端是否在另一条线段的不同侧。建议使用的形式可以通过仅检查LHS的极性来轻松完成此操作。
• 测试线上的一个点是否在多边形内部
  • 测试从输入线的某个点到多边形外部的一条直线是否在奇数个点处穿过多边形。请注意，您需要检查同一点是否从多个位置显示，并且由于FP错误，这不能通过精确匹配测试进行。

- BCS

Answer 4

你需要坐标图上多边形的点以及线的斜率、x和y截距来找到这些信息。从那里开始，它就是简单的数学计算。

- Bjorn