Сканлайн / Коркарди рӯйдодҳо

Кадом навъҳои мушкилоти сканлайн вуҷуд доранд

Техникаи scanline (ҳамчунин коркарди рӯйдодҳо ё sweep line номида мешавад) як равиши пуриқтидори алгоритмӣ аст, ки ҳангоми кор бо интервалҳо, сегментҳо, росткунҷаҳо, геометрия, рӯйдодҳои ҷадвали вақт, ё ҳар гуна ҳолате истифода мешавад, ки чизе танҳо дар нуқтаҳои дискретӣ тағйир меёбад. Ба ҷои санҷидани ҳар як нуқтаи имконпазир, мо рӯйдодҳои калидии ``events''-ро ҷамъ мекунем, онҳоро тартиб медиҳем, ва сипас як sweep-ро аз чап ба рост (ё аз поён ба боло) модел мекунем.

Ин усул ба таври васеъ истифода мешавад барои:

• пӯшиш (coverage)-и интервалҳо ва ҳисоб кардани интервалҳои фаъол
• ёфтани буришҳои сегментҳо ё росткунҷаҳо
• ҳал кардани масъалаҳо бо рӯйдодҳои ҷадвали вақт (оғоз/анҷом)
• ҳисоб кардани иттиҳоди интервалҳо ё масоҳати росткунҷаҳо
• коркарди тағйирот дар сохторҳои додаҳо ҳангоми ҳаракати нишондиҳандаи sweep

Ғояи асосӣ: интервалҳо ё шаклҳоро ба ``events''-и шакли зерин табдил диҳед:

• (position, type, data) Сипас ҳамаи рӯйдодҳоро аз рӯи мавқеъ тартиб диҳед ва он чиро, ки байни рӯйдодҳо рӯй медиҳад, модел кунед.

Мисол 1: Шумораи максималии интервалҳои ҳампӯш

Масъала: Бо дода шудани $n$ интервал $[l_i, r_i]$, шумораи максималии интервалҳоеро ёбед, ки дар ягон нуқта ҳампӯш мешаванд.