Учитывая набор строк в 2-мерном пространстве, как обрезать их, чтобы они были в пределах границ? - PullRequest
Новая
       43

Учитывая набор строк в 2-мерном пространстве, как обрезать их, чтобы они были в пределах границ?

0 голосов
/ 06 июня 2018

Фон:

Хейя!Я пытаюсь создать печатную плату, на которой напечатано подмножество Сан-Франциско.Большинство частей этого сделано, и я генерирую изображения, которые выглядят следующим образом:

Rendered San Francisco

Проблема в том, что я рендеринг линий, которыевыйти за пределы моей жестко заданной границы обрезки (я рендеринг линий, одна сторона которых находится, а одна сторона выходит за границы).

Вопрос:

Учитывая набор линийкак это: 

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

Как я могу изменить координаты каждой строки так, чтобы она «обрезалась» на определенной границе?

В приведенном выше случае вторая строка (который в первоначальной форме) распространяется на (120 120), должен распространяться только на (100 100), принимая за границы 100 100.

Мысли

Основываясь на том, что я помню из высокогошкольная математика, я должен вставить что-то в формулу y=mx+b да?Даже тогда, как бы я справился с бесконечным градиентом или тому подобным?

Спасибо за любую помощь: D Puesdocode / python / Go предпочтительнее, но объяснения так же любезно получены.

<3 Тома </p>

Ответы [ 2 ]

0 голосов
/ 07 июня 2018

Ваш лучший друг - алгоритм отсечения линий Коэна – Сазерленда.

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

0 голосов
/ 07 июня 2018

Сел и поработал.Мой элементарный подход заключался в следующем:

  1. Вычислить наклон линии и точку пересечения y
  2. Проверьте обе точки на всех четырех сторонах, чтобы увидеть, превышают ли они границы, и если они это делают, пересчитайте необходимую координату, включив границу в формулу y=mx+b.

Вот мой код Go: 

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
}
}
...