Trimming a straight line (2 CGPoint) inside a CGRect

Question

Given a CGRect and a line created with 2 CGPoint is there a way to find the coordinates where the line intersects with the rect?

From the previous image: what I'm trying to achieve is to substitute the dots outside the rectangle with the red dots that are intersecting the rectangle borders.

In a few words I'm looking for a way to trim a line inside a rect.

This is a mathematical question but I'd like to know how to solve this problem using foundation if possible.

Following the latest comments: It seems that Core Graphics can't be really helpful in this process. Any other hint or formula that I can convert in Swift?

What have you tried? What research have you done? There must be countless examples of doing this already. Find a few, make some attempt to translate into your favorite language. [Edit] your question with what you have tried so far. — rmaddy, Feb 09 '17 at 18:08
Actually I'm asking for help because I cannot find anything similar and (as well specified in my question) I'm asking for any solution that leverages on foundation and core graphics. — MatterGoal, Feb 09 '17 at 18:15
You may be overly limited yourself by "leverages on foundation and core graphics." There is no specific function that does this. You'll need to do the math. You can of course return `CGPoint`, and in that way you'll "leverage core graphics." But the solution to this will involve solving a few linear equations. If you already know how to do that, you're done. Core Graphics offers nothing here but some types to work with (and Foundation doesn't really offer anything useful for this problem). You also need to define what happens if the line intersects multiple edges of the rectangle. — Rob Napier, Feb 09 '17 at 18:18
Right I'm looking for a way to solve this problem using something like `CGRectIntersection`. I'm trying to figure out a cleaver way to handle the line as a rect and have a big part of the job done without using to much mathematics... btw the "few linear equations" to trim a line inside a rectangle are not so easy to figure out, any hint on that side would be useful too. — MatterGoal, Feb 09 '17 at 18:26
At the moment the only solution that I can see is to split the CGRect in 4 lines and verify the intersection between lines (here is a good guide with math explanation and code https://martin-thoma.com/how-to-check-if-two-line-segments-intersect/#Where_do_two_line_segments_intersect) — MatterGoal, Feb 09 '17 at 18:59
Write your own function: it is explained here http://stackoverflow.com/a/385873/629014 — slcott, Feb 09 '17 at 20:14

score 3 · Accepted Answer · edited May 23 '17 at 10:29

Something like this (lightly tested), based on How do you detect where two line segments intersect?

import CoreGraphics

let rect = CGRect(x: 10, y: 10, width: 100, height: 100)

let point1 = CGPoint(x: 200, y: 200)
let point2 = CGPoint(x: 20, y: 20)

struct LineSegment {
    var point1: CGPoint
    var point2: CGPoint

    func intersection(with line: LineSegment) -> CGPoint? {
        // We'll use Gavin's interpretation of LeMothe:
        // https://stackoverflow.com/a/1968345/97337

        let p0_x = self.point1.x
        let p0_y = self.point1.y
        let p1_x = self.point2.x
        let p1_y = self.point2.y

        let p2_x = line.point1.x
        let p2_y = line.point1.y
        let p3_x = line.point2.x
        let p3_y = line.point2.y

        let s1_x = p1_x - p0_x
        let s1_y = p1_y - p0_y
        let s2_x = p3_x - p2_x
        let s2_y = p3_y - p2_y

        let denom = (-s2_x * s1_y + s1_x * s2_y)

        // Make sure the lines aren't parallel
        guard denom != 0 else { return nil } // parallel

        let s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / denom
        let t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / denom

        // We've parameterized these lines as "origin + scale*vector"
        // (s is the "scale" along one line, t is the "scale" along the other.
        // At scale=0, we're at the origin at scale=1, we're at the terminus.
        // Make sure we crossed between those. For more on what I mean by
        // "parameterized" and why we go from 0 to 1, look up Bezier curves.
        // We're just making a 1-dimentional Bezier here.
        guard (0...1).contains(s) && (0...1).contains(t) else { return nil }

        // Collision detected
        return CGPoint(x: p0_x + (t * s1_x), y: p0_y + (t * s1_y))
    }
}

extension CGRect {    
    var edges: [LineSegment] {
        return [
            LineSegment(point1: CGPoint(x: minX, y: minY), point2: CGPoint(x: minX, y: maxY)),
            LineSegment(point1: CGPoint(x: minX, y: minY), point2: CGPoint(x: maxX, y: minY)),
            LineSegment(point1: CGPoint(x: minX, y: maxY), point2: CGPoint(x: maxX, y: maxY)),
            LineSegment(point1: CGPoint(x: maxX, y: minY), point2: CGPoint(x: maxX, y: maxY)),
        ]
    }

    func intersection(with line: LineSegment) -> CGPoint? {

    // Let's be super-simple here and require that one point be in the box and one point be outside,
    // then we can ignore lots of corner cases
        guard contains(line.point1) && !contains(line.point2) ||
            contains(line.point2) && !contains(line.point1) else { return nil }

        // There are four edges. We might intersect with any of them (we know
        // we intersect with exactly one, based on the previous guard.
        // We could do a little math and figure out which one it has to be,
        // but the `if` would be really tedious, so let's just check them all.
        for edge in edges {
            if let p = edge.intersection(with: line) {
                return p
            }
        }

        return nil
    }
}

rect.intersection(with: LineSegment(point1: point1, point2: point2))

It seems to work with a single intersection, I'm trying to figure out how to make it work also with the line intersecting with 2 edges of the rect (I'll go trough a complete check tomorrow). — MatterGoal, Feb 09 '17 at 20:05
The main question will be defining what you want that answer to be. Note guard statement and comments at the top of `CGRect.intersection`. It currently omits that case intentionally. If you wanted to get a semi-arbitrary intersection, just remove the guard statement. — Rob Napier, Feb 09 '17 at 20:07
Thank you, this code is perfect. Instead of returning the intersection point, with a few edits I'm returning a line that is trimmed inside the rectangle: - I'm keeping the guard, returning the original line when both points are contained into the rectangle. -Then I check all the edges that intersect with the line - Depending on the edges I define which point substitute with the intersection point calculated. I'll update my question adding this code. — MatterGoal, Feb 10 '17 at 08:33

Trimming a straight line (2 CGPoint) inside a CGRect

1 Answers1