我如何确定两条直线是否相交,如果相交,在x,y点处?


当前回答

这个解决方案可能会有所帮助

public static float GetLineYIntesept(PointF p, float slope)
    {
        return p.Y - slope * p.X;
    }

    public static PointF FindIntersection(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End)
    {

        float slope1 = (line1End.Y - line1Start.Y) / (line1End.X - line1Start.X);
        float slope2 = (line2End.Y - line2Start.Y) / (line2End.X - line2Start.X);

        float yinter1 = GetLineYIntesept(line1Start, slope1);
        float yinter2 = GetLineYIntesept(line2Start, slope2);

        if (slope1 == slope2 && yinter1 != yinter2)
            return PointF.Empty;

        float x = (yinter2 - yinter1) / (slope1 - slope2);

        float y = slope1 * x + yinter1;

        return new PointF(x, y);
    }

其他回答

只是想提一下,一个很好的解释和明确的解决方案可以在数字食谱系列中找到。我有这本书的第三版,答案在1117页21.4节。另一种不同命名的解决方案可以在玛丽娜·加夫里洛娃(Marina Gavrilova)的论文中找到。在我看来,她的解决办法要简单一些。

我的实现如下:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
   return (x >= x0) && (x <= x1);
}

bool NuGeometry::FindIntersection(const double& x0, const double& y0, 
     const double& x1, const double& y1,
     const double& a0, const double& b0, 
     const double& a1, const double& b1, 
     double& xy, double& ab) {
   // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
   // returned values xy and ab are the fractional distance along xy and ab
   // and are only defined when the result is true

   bool partial = false;
   double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
   if (denom == 0) {
      xy = -1;
      ab = -1;
   } else {
      xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
      partial = NuGeometry::IsBetween(0, xy, 1);
      if (partial) {
         // no point calculating this unless xy is between 0 & 1
         ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; 
      }
   }
   if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
      ab = 1-ab;
      xy = 1-xy;
      return true;
   }  else return false;
}

许多答案把所有的计算都打包成一个函数。如果您需要计算直线斜率、y轴截距或x轴截距,以便在代码的其他地方使用,那么这些计算将是冗余的。我分离出了各自的函数,使用了明显的变量名,并注释了我的代码以使其更易于理解。我需要知道直线是否无限超出它们的端点,所以在JavaScript中:

http://jsfiddle.net/skibulk/evmqq00u/

var point_a = {x:0, y:10},
    point_b = {x:12, y:12},
    point_c = {x:10, y:0},
    point_d = {x:0, y:0},
    slope_ab = slope(point_a, point_b),
    slope_bc = slope(point_b, point_c),
    slope_cd = slope(point_c, point_d),
    slope_da = slope(point_d, point_a),
    yint_ab = y_intercept(point_a, slope_ab),
    yint_bc = y_intercept(point_b, slope_bc),
    yint_cd = y_intercept(point_c, slope_cd),
    yint_da = y_intercept(point_d, slope_da),
    xint_ab = x_intercept(point_a, slope_ab, yint_ab),
    xint_bc = x_intercept(point_b, slope_bc, yint_bc),
    xint_cd = x_intercept(point_c, slope_cd, yint_cd),
    xint_da = x_intercept(point_d, slope_da, yint_da),
    point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab),
    point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc),
    point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd),
    point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da);

console.log(point_a, point_b, point_c, point_d);
console.log(slope_ab, slope_bc, slope_cd, slope_da);
console.log(yint_ab, yint_bc, yint_cd, yint_da);
console.log(xint_ab, xint_bc, xint_cd, xint_da);
console.log(point_aa, point_bb, point_cc, point_dd);

function slope(point_a, point_b) {
  var i = (point_b.y - point_a.y) / (point_b.x - point_a.x);
  if (i === -Infinity) return Infinity;
  if (i === -0) return 0;
  return i;
}

function y_intercept(point, slope) {
    // Horizontal Line
    if (slope == 0) return point.y;
  // Vertical Line
    if (slope == Infinity)
  {
    // THE Y-Axis
    if (point.x == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return point.y - (slope * point.x);
}

function x_intercept(point, slope, yint) {
    // Vertical Line
    if (slope == Infinity) return point.x;
  // Horizontal Line
    if (slope == 0)
  {
    // THE X-Axis
    if (point.y == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return -yint / slope;
}

// Intersection of two infinite lines
function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) {
  if (slope_a == slope_b)
  {
    // Equal Lines
    if (yint_a == yint_b && xint_a == xint_b) return Infinity;
    // Parallel Lines
    return null;
  }
  // First Line Vertical
    if (slope_a == Infinity)
  {
    return {
        x: xint_a,
      y: (slope_b * xint_a) + yint_b
    };
  }
  // Second Line Vertical
    if (slope_b == Infinity)
  {
    return {
        x: xint_b,
      y: (slope_a * xint_b) + yint_a
    };
  }
  // Not Equal, Not Parallel, Not Vertical
  var i = (yint_b - yint_a) / (slope_a - slope_b);
  return {
    x: i,
    y: (slope_a * i) + yint_a
  };
}

找到两条线段的正确交点是一项具有大量边缘情况的非简单任务。下面是一个用Java编写的、有效的、经过测试的解决方案。

本质上,在求两条线段的交点时,有三种情况会发生:

线段不相交 有一个唯一的交点 交点是另一段

注意:在代码中,我假设x1 = x2和y1 = y2的线段(x1, y1), (x2, y2)是有效的线段。从数学上讲,线段由不同的点组成,但为了完整起见,我在这个实现中允许线段作为点。

代码是从我的github回购

/**
 * This snippet finds the intersection of two line segments.
 * The intersection may either be empty, a single point or the
 * intersection is a subsegment there's an overlap.
 */

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;

import java.util.ArrayList;
import java.util.List;

public class LineSegmentLineSegmentIntersection {

  // Small epsilon used for double value comparison.
  private static final double EPS = 1e-5;

  // 2D Point class.
  public static class Pt {
    double x, y;
    public Pt(double x, double y) {
      this.x = x; 
      this.y = y;
    }
    public boolean equals(Pt pt) {
      return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
    }
  }

  // Finds the orientation of point 'c' relative to the line segment (a, b)
  // Returns  0 if all three points are collinear.
  // Returns -1 if 'c' is clockwise to segment (a, b), i.e right of line formed by the segment.
  // Returns +1 if 'c' is counter clockwise to segment (a, b), i.e left of line
  // formed by the segment.
  public static int orientation(Pt a, Pt b, Pt c) {
    double value = (b.y - a.y) * (c.x - b.x) - 
                   (b.x - a.x) * (c.y - b.y);
    if (abs(value) < EPS) return 0;
    return (value > 0) ? -1 : +1;
  }

  // Tests whether point 'c' is on the line segment (a, b).
  // Ensure first that point c is collinear to segment (a, b) and
  // then check whether c is within the rectangle formed by (a, b)
  public static boolean pointOnLine(Pt a, Pt b, Pt c) {
    return orientation(a, b, c) == 0 && 
           min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && 
           min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
  }

  // Determines whether two segments intersect.
  public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {

    // Get the orientation of points p3 and p4 in relation
    // to the line segment (p1, p2)
    int o1 = orientation(p1, p2, p3);
    int o2 = orientation(p1, p2, p4);
    int o3 = orientation(p3, p4, p1);
    int o4 = orientation(p3, p4, p2);

    // If the points p1, p2 are on opposite sides of the infinite
    // line formed by (p3, p4) and conversly p3, p4 are on opposite
    // sides of the infinite line formed by (p1, p2) then there is
    // an intersection.
    if (o1 != o2 && o3 != o4) return true;

    // Collinear special cases (perhaps these if checks can be simplified?)
    if (o1 == 0 && pointOnLine(p1, p2, p3)) return true;
    if (o2 == 0 && pointOnLine(p1, p2, p4)) return true;
    if (o3 == 0 && pointOnLine(p3, p4, p1)) return true;
    if (o4 == 0 && pointOnLine(p3, p4, p2)) return true;

    return false;
  }

  public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {

    List<Pt> points = new ArrayList<>();

    if (p1.equals(p3)) {
      points.add(p1);
      if (p2.equals(p4)) points.add(p2);

    } else if (p1.equals(p4)) {
      points.add(p1);
      if (p2.equals(p3)) points.add(p2);

    } else if (p2.equals(p3)) {
      points.add(p2);
      if (p1.equals(p4)) points.add(p1);

    } else if (p2.equals(p4)) {
      points.add(p2);
      if (p1.equals(p3)) points.add(p1);
    }

    return points;
  }

  // Finds the intersection point(s) of two line segments. Unlike regular line 
  // segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
  public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {

    // No intersection.
    if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};

    // Both segments are a single point.
    if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
      return new Pt[]{p1};

    List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
    int n = endpoints.size();

    // One of the line segments is an intersecting single point.
    // NOTE: checking only n == 1 is insufficient to return early
    // because the solution might be a sub segment.
    boolean singleton = p1.equals(p2) || p3.equals(p4);
    if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};

    // Segments are equal.
    if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};

    boolean collinearSegments = (orientation(p1, p2, p3) == 0) && 
                                (orientation(p1, p2, p4) == 0);

    // The intersection will be a sub-segment of the two
    // segments since they overlap each other.
    if (collinearSegments) {

      // Segment #2 is enclosed in segment #1
      if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
        return new Pt[]{p3, p4};

      // Segment #1 is enclosed in segment #2
      if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
        return new Pt[]{p1, p2};

      // The subsegment is part of segment #1 and part of segment #2.
      // Find the middle points which correspond to this segment.
      Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
      Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;

      // There is actually only one middle point!
      if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};

      return new Pt[]{midPoint1, midPoint2};
    }

    /* Beyond this point there is a unique intersection point. */

    // Segment #1 is a vertical line.
    if (abs(p1.x - p2.x) < EPS) {
      double m = (p4.y - p3.y) / (p4.x - p3.x);
      double b = p3.y - m * p3.x;
      return new Pt[]{new Pt(p1.x, m * p1.x + b)};
    }

    // Segment #2 is a vertical line.
    if (abs(p3.x - p4.x) < EPS) {
      double m = (p2.y - p1.y) / (p2.x - p1.x);
      double b = p1.y - m * p1.x;
      return new Pt[]{new Pt(p3.x, m * p3.x + b)};
    }

    double m1 = (p2.y - p1.y) / (p2.x - p1.x);
    double m2 = (p4.y - p3.y) / (p4.x - p3.x);
    double b1 = p1.y - m1 * p1.x;
    double b2 = p3.y - m2 * p3.x;
    double x = (b2 - b1) / (m1 - m2);
    double y = (m1 * b2 - m2 * b1) / (m1 - m2);

    return new Pt[]{new Pt(x, y)};
  }

}

下面是一个简单的用法示例:

  public static void main(String[] args) {

    // Segment #1 is (p1, p2), segment #2 is (p3, p4)
    Pt p1, p2, p3, p4;

    p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
    p3 = new Pt(0, 0);  p4 = new Pt(2, 4);
    Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point = points[0];

    // Prints: (1.636, 3.273)
    System.out.printf("(%.3f, %.3f)\n", point.x, point.y);

    p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
    p3 = new Pt(-5, 0);  p4 = new Pt(+5, 0);
    points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point1 = points[0], point2 = points[1];

    // Prints: (-5.000, 0.000) (5.000, 0.000)
    System.out.printf("(%.3f, %.3f) (%.3f, %.3f)\n", point1.x, point1.y, point2.x, point2.y);
  }

这对我来说很有效。从这里拍的。

 // calculates intersection and checks for parallel lines.  
 // also checks that the intersection point is actually on  
 // the line segment p1-p2  
 Point findIntersection(Point p1,Point p2,  
   Point p3,Point p4) {  
   float xD1,yD1,xD2,yD2,xD3,yD3;  
   float dot,deg,len1,len2;  
   float segmentLen1,segmentLen2;  
   float ua,ub,div;  

   // calculate differences  
   xD1=p2.x-p1.x;  
   xD2=p4.x-p3.x;  
   yD1=p2.y-p1.y;  
   yD2=p4.y-p3.y;  
   xD3=p1.x-p3.x;  
   yD3=p1.y-p3.y;    

   // calculate the lengths of the two lines  
   len1=sqrt(xD1*xD1+yD1*yD1);  
   len2=sqrt(xD2*xD2+yD2*yD2);  

   // calculate angle between the two lines.  
   dot=(xD1*xD2+yD1*yD2); // dot product  
   deg=dot/(len1*len2);  

   // if abs(angle)==1 then the lines are parallell,  
   // so no intersection is possible  
   if(abs(deg)==1) return null;  

   // find intersection Pt between two lines  
   Point pt=new Point(0,0);  
   div=yD2*xD1-xD2*yD1;  
   ua=(xD2*yD3-yD2*xD3)/div;  
   ub=(xD1*yD3-yD1*xD3)/div;  
   pt.x=p1.x+ua*xD1;  
   pt.y=p1.y+ua*yD1;  

   // calculate the combined length of the two segments  
   // between Pt-p1 and Pt-p2  
   xD1=pt.x-p1.x;  
   xD2=pt.x-p2.x;  
   yD1=pt.y-p1.y;  
   yD2=pt.y-p2.y;  
   segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // calculate the combined length of the two segments  
   // between Pt-p3 and Pt-p4  
   xD1=pt.x-p3.x;  
   xD2=pt.x-p4.x;  
   yD1=pt.y-p3.y;  
   yD2=pt.y-p4.y;  
   segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // if the lengths of both sets of segments are the same as  
   // the lenghts of the two lines the point is actually  
   // on the line segment.  

   // if the point isn’t on the line, return null  
   if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)  
     return null;  

   // return the valid intersection  
   return pt;  
 }  

 class Point{  
   float x,y;  
   Point(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  

   void set(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  
 }  

我从《多视图几何》这本书里读到了这些算法

以下文本使用

'作为转置符号

*作为点积

当用作算子时,X作为叉乘

1. 线的定义

点x_vec = (x, y)'在直线ax + by + c = 0上

标记L = (a, b, c)',点为(x, y, 1)'为齐次坐标

直线方程可以写成

(x, y, 1)(a, b, c)' = 0或x' * L = 0

2. 直线交点

我们有两条直线L1=(a1, b1, c1)', L2=(a2, b2, c2)'

假设x是一个点,一个向量,x = L1 x L2 (L1叉乘L2)。

注意,x始终是一个二维点,如果你对(L1xL2)是一个三元素向量,x是一个二维坐标感到困惑,请阅读齐次坐标。

根据三重积,我们知道

L1 * (L1 x L2) = 0, L2 * (L1 x L2) = 0,因为L1,L2共平面

我们用向量x代替L1*x,那么L1*x=0, L2*x=0,这意味着x在L1和L2上,x是交点。

注意,这里x是齐次坐标,如果x的最后一个元素是零,这意味着L1和L2是平行的。