Алгоритм нахождения пересечений прямых

Question

есть проблема с пересечением линий, которую я где-то видел и пытался решить.

Имеется сетка размером 64x64 из 8 битных пикселей, на которой расположены несколько вертикальных и горизонтальных линий разного цвета шириной 1 пиксель.Все параллельные линии имеют по крайней мере один пробел между ними.Задача состоит в том, чтобы найти количество пересечений линий, которое делает каждый набор цветных линий (например, все пересечения зеленых линий учитываются в одну сумму).И найдите, какой набор линий имеет наименьшее количество пересечений.Кроме того, все вертикальные линии одного цвета имеют одинаковый размер, а все горизонтальные линии одного цвета имеют одинаковый размер.

У меня было несколько идей, но все они кажутся довольно неэффективными.Это будет связано с прохождением каждого пикселя в сетке, если вы столкнетесь с цветом, определите, является ли это вертикальной или горизонтальной линией, а затем все время идете в направлении линии, одновременно проверяя соседние стороны на наличие разных цветов.

Я пытаюсь решить, ускорит ли процесс первый подсчет длины горизонтальных и вертикальных линий для каждого цвета.У вас есть какие-нибудь блестящие идеи, как это сделать?

Вот два примера.Обратите внимание, что между параллельными линиями всегда есть пробел.

Answer 1

На сетке с вашими линиями ищите 2 типа квадратов 3х3:

1).a.  2).a.
  bab    bbb
  .a.    .a.

"" представляет фон (всегда черный?), «a» и «b» представляют 2 разных цвета (также отличающихся от цвета фона). Если найдено, увеличьте на 1 количество пересечений линий a-цвета и пересечений b-цвета.

Answer 2

Сканирование пиксельной сетки на самом деле очень быстро и эффективно. Это стандартно для систем компьютерного зрения. Многие из этих сканирований производят отфильтрованные по РПИ версии изображений, которые подчеркивают типы разыскиваемых деталей.

Основным техническим термином является «свертка» (см. http://en.wikipedia.org/wiki/Convolution).. Я думаю, что это своего рода взвешенное скользящее среднее, хотя веса могут быть отрицательными. Анимации в Википедии показывают свертку с использованием довольно скучного импульса ( могла бы быть более интересной формой) и для 1D-сигнала (например, звука), а не 2D-сигнала (изображения), но это очень общая концепция.

Соблазнительно думать, что можно сделать что-то более эффективное, если заранее не рассчитать эту отфильтрованную версию, но обычный эффект этого состоит в том, что, поскольку вы не рассчитали все эти пиксели заранее, вы в конечном итоге рассчитываете каждый пиксель несколько раз. Другими словами, представьте, что отфильтрованное изображение является оптимизацией на основе таблицы поиска, или разновидностью динамического программирования .

Некоторые конкретные причины, почему это быстро, это ...

1. Это очень удобно для кэширования, поэтому эффективно обращается к памяти.
2. Это именно то, для чего предназначены векторные инструкции (MMX, SIMD и т. Д.).
3. В наши дни вы даже можете разгрузить работу на вашей видеокарте.

Еще одним преимуществом является то, что вам нужно написать только одну функцию свертки с фильтрацией изображений. Специфичная для приложения часть - это то, как вы определяете ядро ​​фильтра, которое является просто сеткой весовых значений. На самом деле вам, вероятно, вообще не следует писать эту функцию самостоятельно - различные библиотеки числового кода могут предоставлять высокооптимизированные версии.

Для работы с разными цветами линий я просто сначала сгенерировал бы одно изображение в оттенках серого для каждого цвета, а затем отфильтровал и проверил каждое из них отдельно. Опять же, подумайте об этом как об оптимизации - попытка избежать создания отдельных изображений, скорее всего, приведет к увеличению работы, а не к снижению.

• Подумав, я понял это требование. Возможно, имеет смысл сгенерировать черно-белое изображение из черно-белого цвета, отфильтровать его и найти из него все пересечения. Получив точки пересечения, вернитесь к исходному черно-цветному изображению, чтобы классифицировать их для подсчета. Фильтрация и поиск пересечений остаются очень эффективными для каждого пикселя. Классификация не так эффективна для каждого пикселя, но выполняется только в нескольких точках.

Вы можете сделать свертку, основанную на следующем ядре FIR-фильтра ...

.*.
***
.*.

Точки - это нули (нерелевантные пиксели) или, возможно, отрицательные значения (предпочитают черный). Звездочки имеют положительные значения (предпочитают белый). То есть ищите кресты три на три на перекрестках.

Затем вы сканируете отфильтрованный результат в поисках пикселей в градациях серого, которые ярче, чем какой-либо порог, что наилучшим образом соответствует вашему шаблону. Если вам действительно нужны только точные точки пересечения, вы можете принять только цвет с идеальным соответствием, но вы можете сделать поправки на соединения в стиле Т и т. Д.

Answer 3

Простой способ найти прямое пересечение

def straight_intersection(straight1, straight2):
    p1x = straight1[0][0]
    p1y = straight1[0][1]
    p2x = straight1[1][0]
    p2y = straight1[1][1]
    p3x = straight2[0][0]
    p3y = straight2[0][1]
    p4x = straight2[1][0]
    p4y = straight2[1][1]
    x = p1y * p2x * p3x - p1y * p2x * p4x - p1x * p2y * p4x + p1x * p2y * p3x - p2x * p3x * p4y + p2x * p3y * p4x + p1x * p3x * p4y - p1x * p3y * p4x
    x = x / (p2x * p3y - p2x * p4y - p1x * p3y + p1x * p4y + p4x * p2y - p4x * p1y - p3x * p2y + p3x * p1y)
    y = ((p2y - p1y) * x + p1y * p2x - p1x * p2y) / (p2x - p1x)
    return (x, y)

Answer 4

Ваш единственный вход - сетка 64x64? Если это так, то вы смотрите на что-то со вкусом 64x64, поскольку нет другого способа убедиться, что вы обнаружили все строки. Поэтому я предполагаю, что вы говорите об оптимизации на операционном уровне, а не асимптотически. Кажется, я помню, что в старых сериях «Graphics Gems» было много подобных примеров с упором на уменьшение количества команд. Я лучше справляюсь с асимптотическими вопросами, но вот несколько небольших идей:

Ячейки сетки имеют свойство, что сетка [i, j] является зеленым пересечением, если

(grid[i,j] == green)
&&
(grid[i+1,j]==green || grid[i-1,j]==green)
&&
(grid[i,j+1]==green || grid[i, j-1]==green)

Таким образом, вы можете просто сканировать массив один раз, не беспокоясь о явном обнаружении горизонтальных и вертикальных линий ... просто пройдитесь по нему, используя это соотношение, и подсчитывайте пересечения по мере их нахождения. По крайней мере, вы просто используете один цикл 64x64 с довольно простой логикой.

Так как нет двух параллельных линий, непосредственно примыкающих, вы знаете, что вы можете увеличить свой счетчик внутреннего цикла на 2, когда проходите заполненную ячейку. Это сэкономит вам немного работы.

В зависимости от вашей архитектуры у вас может быть быстрый путь к И всей сетке со смещенными копиями самого себя, что будет отличным способом для вычисления приведенной выше формулы пересечения. Но тогда вам все равно придется пройтись по всем вещам, чтобы найти оставшиеся заполненные ячейки (которые являются точками пересечения).

Даже если у вас нет чего-то вроде графического процессора, который позволял бы вам И всю сетку, вы можете использовать эту идею, если количество цветов меньше половины размера вашего слова. Например, если у вас 8 цветов и 64-битный компьютер, вы можете втиснуть 8 пикселей в одно целое число без знака. Так что теперь вы можете выполнять операцию сравнения внешнего цикла для 8 ячеек сетки одновременно. Это может сэкономить вам столько работы, что стоит сделать два прохода, один для горизонтального внешнего цикла и один для вертикального внешнего цикла.