iphone - 坐标中两条线的交点

Question

我可以检测到两条线的交点，但如果我的线没有屏幕的长度，它会检测到不应该在的点。

这是一个预览：所以，它不应该检测到这个交叉点，因为水平线没有那么长。

代码：

- (NSMutableArray *) intersectWithLines:(CGPoint)startPoint andEnd:(CGPoint)endPoint {
    NSMutableArray *intersects = [[NSMutableArray alloc] init];

    for(GameLine *line in [_lineBackground getLines]) {

        double lineStartX = line.startPos.x;
        double lineStartY = line.startPos.y;
        double tempEndX = line.endPos.x;
        double tempEndY = line.endPos.y;

        double d = ((startPoint.x - endPoint.x)*(lineStartY - tempEndY)) - ((startPoint.y - endPoint.y) * (lineStartX - tempEndX));

        if(d != 0) {            
            double sX = ((lineStartX - tempEndX) * (startPoint.x * endPoint.y - startPoint.y * endPoint.x) - (startPoint.x - endPoint.x) * (lineStartX * tempEndY - lineStartY * tempEndX)) / d;
            double sY = ((lineStartY - tempEndY) * (startPoint.x * endPoint.y - startPoint.y * endPoint.x) - (startPoint.y - endPoint.y) * (lineStartX * tempEndY - lineStartY * tempEndX)) / d;


            if([self isValidCGPoint:CGPointMake(sX, sY)]) {
                [intersects addObject:[NSValue valueWithCGPoint:CGPointMake(sX, sY)]];
            }            
        }
    }

    return intersects;
}

score 31 · Accepted Answer

如果我正确理解您的问题，您需要确定两条线段的交点。这应该使用以下方法：

- (NSValue *)intersectionOfLineFrom:(CGPoint)p1 to:(CGPoint)p2 withLineFrom:(CGPoint)p3 to:(CGPoint)p4
{
    CGFloat d = (p2.x - p1.x)*(p4.y - p3.y) - (p2.y - p1.y)*(p4.x - p3.x);
    if (d == 0)
        return nil; // parallel lines
    CGFloat u = ((p3.x - p1.x)*(p4.y - p3.y) - (p3.y - p1.y)*(p4.x - p3.x))/d;
    CGFloat v = ((p3.x - p1.x)*(p2.y - p1.y) - (p3.y - p1.y)*(p2.x - p1.x))/d;
    if (u < 0.0 || u > 1.0)
        return nil; // intersection point not between p1 and p2
    if (v < 0.0 || v > 1.0)
        return nil; // intersection point not between p3 and p4
    CGPoint intersection;
    intersection.x = p1.x + u * (p2.x - p1.x);
    intersection.y = p1.y + u * (p2.y - p1.y);

    return [NSValue valueWithCGPoint:intersection];
}

score 8 · Accepted Answer

这是Hayden Holligan 对 Swift 3的回答稍作修改的版本：

func getIntersectionOfLines(line1: (a: CGPoint, b: CGPoint), line2: (a: CGPoint, b: CGPoint)) -> CGPoint {

    let distance = (line1.b.x - line1.a.x) * (line2.b.y - line2.a.y) - (line1.b.y - line1.a.y) * (line2.b.x - line2.a.x)
    if distance == 0 {
        print("error, parallel lines")
        return CGPoint.zero
    }

    let u = ((line2.a.x - line1.a.x) * (line2.b.y - line2.a.y) - (line2.a.y - line1.a.y) * (line2.b.x - line2.a.x)) / distance
    let v = ((line2.a.x - line1.a.x) * (line1.b.y - line1.a.y) - (line2.a.y - line1.a.y) * (line1.b.x - line1.a.x)) / distance

    if (u < 0.0 || u > 1.0) {
        print("error, intersection not inside line1")
        return CGPoint.zero
    }
    if (v < 0.0 || v > 1.0) {
        print("error, intersection not inside line2")
        return CGPoint.zero
    }

    return CGPoint(x: line1.a.x + u * (line1.b.x - line1.a.x), y: line1.a.y + u * (line1.b.y - line1.a.y))
}

score 4 · Accepted Answer

斯威夫特版本

func getIntersectionOfLines(line1: (a: CGPoint, b: CGPoint), line2: (a: CGPoint, b: CGPoint)) -> CGPoint {
        let distance = (line1.b.x - line1.a.x) * (line2.b.y - line2.a.y) - (line1.b.y - line1.a.y) * (line2.b.x - line2.a.x)
        if distance == 0 {
            print("error, parallel lines")
            return CGPointZero
        }

        let u = ((line2.a.x - line1.a.x) * (line2.b.y - line2.a.y) - (line2.a.y - line1.a.y) * (line2.b.x - line2.a.x)) / distance
        let v = ((line2.a.x - line1.a.x) * (line1.b.y - line1.a.y) - (line2.a.y - line1.a.y) * (line1.b.x - line1.a.x)) / distance

        if (u < 0.0 || u > 1.0) {
            print("error, intersection not inside line1")
            return CGPointZero
        }
        if (v < 0.0 || v > 1.0) {
            print("error, intersection not inside line2")
            return CGPointZero
        }

        return CGPointMake(line1.a.x + u * (line1.b.x - line1.a.x), line1.a.y + u * (line1.b.y - line1.a.y))
    }

score 2 · Accepted Answer

这是正确的等式：

+(CGPoint) intersection2:(CGPoint)u1 u2:(CGPoint)u2 v1:(CGPoint)v1 v2:(CGPoint)v2 {  
    CGPoint ret=u1;  
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))  
    /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));  
    ret.x+=(u2.x-u1.x)*t;  
    ret.y+=(u2.y-u1.y)*t;  
    return ret;  
}

score 2 · Accepted Answer

这是 Swift 4.2 中的另一个解决方案。这在功能上与 MartinR 的解决方案相同，但使用 simd 向量和矩阵来清理它。

/// Protocol adoped by any type that models a line segment.
protocol LineSegment
{
    /// Point defining an end of a line segment.
    var p1: simd_double2 { get }
    /// Point defining an end of a line segment.
    var p2: simd_double2 { get }
}

extension LineSegment
{
    /// Calcualte the intersection between this line segment and another line
    /// segment.
    ///
    /// Algorithm from here:
    /// http://www.cs.swan.ac.uk/~cssimon/line_intersection.html
    ///
    /// - Parameter other: The other line segment.
    /// - Returns: The intersection point, or `nil` if the two line segments are
    ///            parallel or the intersection point would be off the end of
    ///            one of the line segments.
    func intersection(lineSegment other: LineSegment) -> simd_double2?
    {
        let p3 = other.p1 // Name the points so they are consistent with the explanation below
        let p4 = other.p2
        let matrix = simd_double2x2(p4 - p3, p1 - p2)
        guard matrix.determinant != 0 else { return nil } // Determinent == 0 => parallel lines
        let multipliers = matrix.inverse * (p1 - p3)
        // If either of the multipliers is outside the range 0 ... 1, then the
        // intersection would be off the end of one of the line segments.
        guard (0.0 ... 1.0).contains(multipliers.x) && (0.0 ... 1.0).contains(multipliers.y)
            else { return nil }
        return p1 + multipliers.y * (p2 - p1)
    }
}

该算法有效，因为如果您有由两个点p ₁和p ₂定义的线段a和由p ₃和p ₄定义的线段b ，则a和b上的点分别由

p ₁ + t _a ( p ₂ - p ₁ )
p ₃ + t _b ( p ₄ - p ₃ )

所以交点在哪里

p ₁ + t _a ( p ₂ - p ₁ ) = p ₃ + t _b ( p ₄ - p ₃ )

这可以重新排列为

p ₁ - p ₃ = t _b ( p ₄ - p ₃ ) + t _a ( p ₁ - p ₂ )

并且通过一些棘手的扑克，您可以得到以下等价物

p ₁ - p ₃ = A。 _ 吨

其中t是向量 (t _b , t _a )，A是矩阵，其列是p ₄ - p ₃和p ₁ - p ₂

方程可以重新排列为

一个^-1 ( p ₁ - p ₃ ) = t

左边的一切都是已知的，或者可以计算得到我们t。t的任何一个分量都可以插入各自的原始方程以获得交点（NB 浮点舍入误差意味着两个答案可能不完全相同但非常接近）。

请注意，如果线平行，则A的行列式将为零。此外，如果任一组件超出范围0 ... 1，则需要扩展一个或两个线段以到达交点。

score 0 · Accepted Answer

我知道答案已经给出，而且所有答案都是正确的，我觉得要对这个问题给出我的答案。所以就在这里。

func linesCross(start1: CGPoint, end1: CGPoint, start2: CGPoint, end2: CGPoint) -> (x: CGFloat, y: CGFloat)? {
// calculate the differences between the start and end X/Y positions for each of our points
let delta1x = end1.x - start1.x
let delta1y = end1.y - start1.y
let delta2x = end2.x - start2.x
let delta2y = end2.y - start2.y

// create a 2D matrix from our vectors and calculate the determinant
let determinant = delta1x * delta2y - delta2x * delta1y

if abs(determinant) < 0.0001 {
    // if the determinant is effectively zero then the lines are parallel/colinear
    return nil
}

// if the coefficients both lie between 0 and 1 then we have an intersection
let ab = ((start1.y - start2.y) * delta2x - (start1.x - start2.x) * delta2y) / determinant

if ab > 0 && ab < 1 {
    let cd = ((start1.y - start2.y) * delta1x - (start1.x - start2.x) * delta1y) / determinant

    if cd > 0 && cd < 1 {
        // lines cross – figure out exactly where and return it
        let intersectX = start1.x + ab * delta1x
        let intersectY = start1.y + ab * delta1y
        return (intersectX, intersectY)
    }
}

// lines don't cross
return nil
}

我从这个网站得到这个。

这一个也非常简单易行。

快乐编码:)

score 0 · Accepted Answer

这个答案有多种编程语言可用

https://rosettacode.org/wiki/Find_the_intersection_of_two_lines

struct Point {
  var x: Double
  var y: Double
}
 
struct Line {
  var p1: Point
  var p2: Point
 
  var slope: Double {
    guard p1.x - p2.x != 0.0 else { return .nan }
 
    return (p1.y-p2.y) / (p1.x-p2.x)
  }
 
  func intersection(of other: Line) -> Point? {
    let ourSlope = slope
    let theirSlope = other.slope
 
    guard ourSlope != theirSlope else { return nil }
 
    if ourSlope.isNaN && !theirSlope.isNaN {
      return Point(x: p1.x, y: (p1.x - other.p1.x) * theirSlope + other.p1.y)
    } else if theirSlope.isNaN && !ourSlope.isNaN {
      return Point(x: other.p1.x, y: (other.p1.x - p1.x) * ourSlope + p1.y)
    } else {
      let x = (ourSlope*p1.x - theirSlope*other.p1.x + other.p1.y - p1.y) / (ourSlope - theirSlope)
      return Point(x: x, y: theirSlope*(x - other.p1.x) + other.p1.y)
    }
  }
}
 
let l1 = Line(p1: Point(x: 4.0, y: 0.0), p2: Point(x: 6.0, y: 10.0))
let l2 = Line(p1: Point(x: 0.0, y: 3.0), p2: Point(x: 10.0, y: 7.0))
 
print("Intersection at : \(l1.intersection(of: l2)!)")

iphone - 坐标中两条线的交点

7 回答 7

Related

Reference