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:

Rendered San Francisco

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条回答 默认 最新

  • 已采纳
    douluan5444 douluan5444 2018-06-07 08:20

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

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

    点赞 评论 复制链接分享
  • duanputian5341 duanputian5341 2018-06-06 23:35

    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
    }
    }
    
    点赞 评论 复制链接分享

相关推荐