 ###### duan010167787
2018-06-06 20:22 阅读 73

# 给定2d空间中的一组线，如何将它们截断为界？

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

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享

#### 2条回答默认 最新

• 已采纳

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

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

点赞 评论 复制链接分享
• Sat down and worked it out. My rudimentary approach was to:

1. Compute the slope of the line & the y-intercept
2. 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
}
}
``````
点赞 评论 复制链接分享