Given a set of lines in 2d space, how to truncate them to be within bounds?

Question

Background:

Heya! I'm trying to generate a circuit board which has a subset of San Francisco printed on it. Most of the pieces of this are done, and I'm generating images that look like this:

The problem is that I am rendering lines which extend outside my hardcoded cutoff boundary (I am rendering lines which one side is in and one side is out of bounds).

Question:

Given a set of lines like this:

# x1,y1,  x2,y2
10,10,40,40
80,80,120,120

How can I modify the co-ordinates of each line such that it 'cuts off' at a specific bound?

In the case above, the second line (which in original form) extends to (120,120), should only extend to (100,100) assuming bounds of 100,100.

Thoughts

Based on what I remember from high-school math, I should plug something into the formula y=mx+b yeah? Even then, how would I deal with an infinite gradient or the like?

Thanks for any and all help :D Puesdocode/python/Go preferred, but explanations just as graciously recieved.

<3 Tom

SO is not a tutorial site or free code writing service. Please check out [ask], as well as look at the [help/on-topic] to see which topics are appropriate to ask about here. — user3483203, Jun 06 '18 at 20:25
As far as I can tell I meet everything mentioned in the How to Ask section? I'm asking for algorithmic advice, not dev freebies. — 64bit_twitchyliquid, Jun 06 '18 at 20:27
I ran into this issue recently, but I didn't bother to write code that solved the problem perfectly. In other words, my lines do fall off the canvas a little bit, not that the user can tell. Is there a reason why you must solve this problem? — Ben Quigley, Jun 06 '18 at 20:28
Hi Ben. Some PCB fabricators (eg: mine) care if your generated drawings exceed the bounds of your design, so I need a clean cutoff at exactly the board edge. — 64bit_twitchyliquid, Jun 06 '18 at 20:30
Find the point where your boundary and road intersect: https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect — c2huc2hu, Jun 06 '18 at 21:26
@meowgoesthedog: Sutherland-Hodgman is a little overkill for an axis-aligned rectangular window. Cohen–Sutherland is more specialized. — , Jun 07 '18 at 08:23

score 1 · Accepted Answer · answered Jun 07 '18 at 08:20

1

Your best friend is the Cohen–Sutherland line clipping algorithm.

https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm

answered Jun 07 '18 at 08:20

score 0 · Answer 2 · answered Jun 06 '18 at 23:35

Sat down and worked it out. My rudimentary approach was to:

Compute the slope of the line & the y-intercept
Check both points on all four sides to see if they exceed bounds, and if they do, recompute the necessary co-ordinate by plugging the bound into the formula y=mx+b.

Here is my Go code:

func boundLine(line *kcgen.Line) {
if line.Start.X == line.End.X {
    panic("infinite slope not yet supported")
}
slope := (line.End.Y - line.Start.Y) / (line.End.X - line.Start.X)
b := line.End.Y - (slope * line.End.X) //y = mx + b which is equivalent to b = y - mx
if line.Start.X < (-*width/2) {
    line.Start.Y = (slope * (-*width/2)) + b
    line.Start.X = -*width/2
}
if line.End.X < (-*width/2) {
    line.End.Y = (slope * (-*width/2)) + b
    line.End.X = -*width/2
}
if line.Start.X > (*width/2) {
    line.Start.Y = (slope * (*width/2)) + b
    line.Start.X = *width/2
}
if line.End.X > (*width/2) {
    line.End.Y = (slope * (*width/2)) + b
    line.End.X = *width/2
}

if line.Start.Y < (-*height/2) {
    line.Start.Y = -*height/2
    line.Start.X = ((-*height/2) - b) / slope //y = mx + b equiv. (y-b)/m = x
}
if line.End.Y < (-*height/2) {
    line.End.Y = -*height/2
    line.End.X = ((-*height/2) - b) / slope //y = mx + b equiv. (y-b)/m = x
}
if line.Start.Y > (*height/2) {
    line.Start.Y = *height/2
    line.Start.X = ((*height/2) - b) / slope //y = mx + b equiv. (y-b)/m = x
}
if line.End.Y > (*height/2) {
    line.End.Y = *height/2
    line.End.X = ((*height/2) - b) / slope //y = mx + b equiv. (y-b)/m = x
}
}

Given a set of lines in 2d space, how to truncate them to be within bounds?

2 Answers2