Оптимизация алгоритма поиска пересечений - PullRequest
Новая
       10

Оптимизация алгоритма поиска пересечений

2 голосов
/ 11 октября 2011

Я пытаюсь сильно оптимизировать фрагмент кода, который я написал, прежде чем писать его в сборке MIPS. Вот ссылка на мой код: http://dl.dropbox.com/u/7264839/P1-3.c

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

http://dl.dropbox.com/u/7264839/Pics/pile1.png

Мой основной алгоритм - смотреть на каждый пиксель (кроме тех, которые расположены по периметру) и, если он черный, игнорировать его. Если это не черный, проверьте две стороны, и если они одного цвета, а не черного, проверьте другие стороны, и если они одного цвета, а не черного, и другого цвета с других сторон, есть пересечение. Кроме того, если найдено пересечение, следующий пиксель можно игнорировать.

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

1 Ответ

1 голос
/ 04 февраля 2012

Вы можете оптимизировать свой алгоритм для черных зон: поскольку для пересечения линий потребуется длина не менее 3 пикселей в обоих направлениях, вы можете проверить только 3 пикселя на группу из 9, используя следующий шаблон: 

X  .  .
.  X  .
.  .  X

Если ни один пиксель не является черным на каждые 3х3 квадрата, пропустите квадрат.Если хотя бы один из них не черный, воспользуйтесь исходным алгоритмом.

Если у вас низкое соотношение цвета / черного, это может улучшить ваш код в ~ 3 *

раза.
...