Вычисление точек пересечения линий на сетке типа трапеции ⇐ Python

[Anonymous]

• Мне нужно вычислить около 2 миллионов координат (64-битные кортежи с плавающей точкой)
• Это точки пересечения линий, образующих сетку в форме трапеции (см. изображение ниже)
• Форма параллелограмма разная для каждой итерации.
• У меня есть все граничные координаты (зеленые) в моем распоряжении.
• Линии, идущие с востока на запад, имеют постоянную широту.

Я уверен, что эта проблема решалась много раз, но, увы, я не знаю, какие ключевые слова мне следует искать, чтобы найти решение. Логические подходы, которые я рассматривал до сих пор:

• Рассчитать наклон линии с севера на юг (т. е.: (y2 - y1) / (x2 - x1)). Определите значение x (т. е. долготу линии восток-запад в месте пересечения).
• Вычислите длину линии восток-запад. Вычтите общую постоянную ширину (т. е. 6 узких полосок). Разделите остаток на 6. Примените результат как продольное смещение для каждой точки на линии восток-запад.
• Пытался использовать функцию shapely Split(), чтобы разделить многоугольник в форме параллелограмма строками линий, но быстро стало ясно, что обработка возвращаемой коллекции GeometryCollection и ее сортировка будут кошмаром.

Я уверен, что вы ребята знают гораздо лучшие способы.
Вопросы:

• Какой математический вычислительный подход лучше всего подходит для этого? и
• Есть ли какие-нибудь библиотеки Python, которые я мог бы использовать для ускорения работы?
• Бонус: мне, вероятно, придется запустить это как многопроцессный процесс, когда придет время генерировать набор данных. Можете ли вы подтвердить, что эти типы вычислений лучше всего выполнять на ядрах ЦП, а не на графических процессорах?

Подробнее здесь: https://stackoverflow.com/questions/798 ... -type-grid