Доброго времени суток!

Имеется окружность (строю по Брезенхему) и много всяких кривых линий. Требуется на построенной окружности найти точки, в которых линии касаются её, но не пересекают.

Как понимаю, формул кривых у Вас нет, только их растровые изображения. А данные для построения окружности  есть (иначе какая разница каким алгоритмом строили?). 

Я бы сделал так.

1. Растр с кривыми бинаризуется (если он уже не бинаризован): скажем, точкам, принадлежащим кривым присваиваем единицы, без кривых нули. Бинаризованный растр храним, скажем, в Integer формате.

2. Рисуем окружность по Брезенхему, при этом пикселям 0 присваиваем значение 2, а пикселям 1 - значение 3; т.е проводим окружность не присваивая какое-то значение, а прибавляя к имеющемуся +2.

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

И еще:

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

ii) Все это будет работать если и кривые и окружность имеют толщину не в один пиксель. Если же они однопиксельные, сначала нужно их "утолстить". Будет некоторая потеря точности, но с ней можно будет побороться последующими проверками.

Это сообщение отредактировал(а) _Y_ - 24.5.2014, 09:04

Спасибо за ответ, помогли)