Я дал набор линий в некотором координатном пространстве (в моем случае изображение). Теперь я наложил сетку на верхнюю часть изображения и хочу вычислить для каждой ячейки сетки линии, которые пересекаются с ней.
Каждая линия ломаной линии представлена в виде двух точек на изображении и некоторого дополнительного атрибута, который требует сохраняется также (на изображении ниже дополнительный атрибут - цвет [оранжевый или красный]). 
Линии имеют тенденцию распределяться по нескольким ячейкам сетки, что приводит к необходимости их обрезать, соответственно. В примере показан набор оранжевых и красных линий, которые должны быть обрезаны в соответствии с черной сеткой. Глядя на синюю ячейку, становится очевидной необходимость добавления дополнительных точек к линиям.
Моя исходная идея - вычислить все точки, где сетка пересекается с любой линией. Всякий раз, когда такое пересечение найдено, точка пересечения добавляется к исходному отрезку линии. На следующем шаге точки должны быть отсортированы в ячейки сетки с помощью простой операции по модулю. Т.е.
for each grid cell:
for each original line:
keep only the points from the line which lay in the current grid cell
- Я не уверен, может ли мой подход действительно работать. И если это работает, если это не ужасно неэффективно.
- Я борюсь с вычислением заявленных точек пересечения (где пересекаются сетка и отрезок)
Помощь для любого из двух очки высоко ценятся.