Заполнение Многоугольника:Производительность Правила намотки по сравнению с Четным Нечетным правилом

Question

Для сложного многоугольника (т.е.:самопересекающийся) выбор между правилами наматывания или Четно-нечетной заливки влияет на способ заливки полигона.

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

Последующий вопрос, какова сложность (т.е. O (чего?) ) каждого из этих алгоритмов.Я хочу знать, стоит ли избавляться от некоторых точек в полигоне (в основном дубликатов или тех, которые находятся на одной линии), чтобы повысить производительность.

PS:Если это вообще имеет значение, я использую xlib

ППС:Я могу подтвердить, что проблема не связана с оборудованием, поскольку использование другой видеокарты не изменяет производительность

Answer 1

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

Поскольку это вопрос производительности, вероятность того, что мой ответ будет правильным, составляет около 10%, хотя (что касается производительности, у вас есть 90% шанс ошибиться без измерения).Если вы хотите быть уверены, нет другого способа, кроме как написать небольшой тест производительности и убедиться в этом сами.

x11перф могло бы помочь.

Вы можете найти алгоритм аппаратно независимой заливки полигонов здесь: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

Существует вторая версия, которая намного быстрее, если вы уверены, что ваш многоугольник выпуклый: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

Вторая версия игнорирует правило заливки (которое не применяется к выпуклым многоугольникам).Комментарии об алгоритме: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipoly.h?rev=HEAD

Алгоритм работает следующим образом:Он вычисляет контур, затем создает объекты span (которые представляют собой просто координаты x, y и ширину) между краями.Если вы используете правило EvenOdd, при наличии пересечений будет создано больше объектов span.Если их нет (например, когда многоугольник выпуклый), то вы не заметите разницы во время выполнения, потому что правило заполнения равнозначно логической переменной в главном цикле miFillPolygon (т.е.большая часть кода одинакова для обоих правил заполнения).

Попытка повысить производительность путем оптимизации контура полигона не принесет вам большой пользы в обычном случае, за исключением того случая, если вы знаете, что ваши полигоны содержат очень большое количество ненужных точек (скажем, вы можете избавиться от половины количества точек в обычном случае).Оптимизация многоугольника с помощью < 10 баллов, вероятно, будут стоить дороже, чем это достигается.

Но опять же:Все это основано на интуиции или знании старой статьи.Если вы хотите знать, влияют ли ошибки в драйвере вашей карты gfx на результат, вам придется испачкать руки и написать тест, который измеряет, сколько времени занимает каждый случай.Невозможно определить время выполнения какого-либо сложного алгоритма, просто взглянув на него из-за внешних факторов:Скорость процедур выделения памяти, объем свободной памяти (когда начинается замена), количество ядер процессора, которые вы можете использовать, сколько других процессов будут бороться с вами за процессор, обрезка конечного полигона на экране, детали реализации и оптимизации, ошибки и т.д.