Есть два двумерных полигона P1, P2, причём,
каждое ребро полигона параллельно одной из осей координат либо X либо Y.

Необходимы алгоритмы пересечения двух таких полигонов, объединения, вычитания.

Где почитать?

Заранее благодарен

Здравствуйте, Аноним, Вы писали:

А>Необходимы алгоритмы пересечения двух таких полигонов, объединения, вычитания.
Где почитать не скажу, скажу одну из популярных реализаций
заводишь структуру

struct Stroke {
    int Begin;
    int End;

    static Stroke Make( int begin, int end );
    
    static const Stroke Sentinel; // = { INT_MIN, INT_MAX }; например
    bool IsSentinel() const;
    int Length() const;
    // И т. д.
};

Потом заводишь полигон в виде строк таких штрихов.
Ну и пользуешься. Все операции реализуются тривиально....

Здравствуйте, Erop, Вы писали:

E>Потом заводишь полигон в виде строк таких штрихов.
E>Ну и пользуешься. Все операции реализуются тривиально....

Не так уж и тривиально
Но мысль в правильном направлении.
1. Представить полигон не массивом вершин, а коллекцией отрезков (избыточно, но удобно)
2. Перебирать по очереди все отрезки у обоих полигонов на предмет пересечения (пересечение отрезков находится гуглом в две секунды)
3. Анализировать полученные точки пересечения на предмет попадания в оба полигона. Это нужно для формирования результирующего полигона (в зависимости от операции: AND, OR, XOR)
4. Удаление лишних отрезков
5. А тут уже можно заняться оптимизацией.

Здравствуйте, akarinsky, Вы писали:

A>Но мысль в правильном направлении.
A>1. Представить полигон не массивом вершин, а коллекцией отрезков (избыточно, но удобно)
A>2. Перебирать по очереди все отрезки у обоих полигонов на предмет пересечения (пересечение отрезков находится гуглом в две секунды)
A>3. Анализировать полученные точки пересечения на предмет попадания в оба полигона. Это нужно для формирования результирующего полигона (в зависимости от операции: AND, OR, XOR)
A>4. Удаление лишних отрезков
A>5. А тут уже можно заняться оптимизацией.

Остановился на линейно-узловом алгоритме построения оверлеев...

Здравствуйте, akarinsky, Вы писали:

A>Здравствуйте, Erop, Вы писали:

E>>Потом заводишь полигон в виде строк таких штрихов.
E>>Ну и пользуешься. Все операции реализуются тривиально....

A>Не так уж и тривиально
Да ну? Какая операция нетривильная? Объединение или пересечение?
Только я с ограничителем наврал. Он должен быть таким:

const Stroke Stroke::Sentinel = { NIT_MAX, INT_MIN };

Лично мне больше всего нравится формулировка в виде автомата. Типа пропускаем начала/концы штриха по одному. Имеем 4 состояния

ee -- мы стоим в начале нового штриха. Левее нас находятся концы и src1 и src2
be -- мы пропустили начало штриха из src1, а конец src2 ещё не пропустили. В dst->Begin находится начало штриха
eb -- симметрично. На самом деле это состояние не нужно, так как можно менять src1 и src2 местами
bb -- мы пропустили начала обоих штрихов и теперь ищем какой бы конец пропустить первым. В dst->Begin нвчвло штриха

Stroke* orRleReg( Stroke* dst, const Stroke* src1, const Stroke* arc2, int linesCount = 1 )
{
    assert( dst != 0 && src1 != 0 && src2 != 0 && linesCount >= 0 );
    for( int i = 0; i < linesCount; i++ ) {

        //    Мы стоим после концов обоих штрихов. 
        //    В dst ничего нет
ee:        {    
            if( src1->Begin < src2->Begin ) {
                dst->Begin = src1->Begin;
                goto be;
            }
            if( src1->IsSentenel() ) {
                std::swap( src1, src2 );
                goto copyRestOfSrc1;
            }
            assert( src1->Begin >= src2->Begin && 
                !src1->IsSentenel() && src2->IsSentenel() );
            std::swap( src1, src2 );
            dst->Begin = src1->Begin;
            goto be;
        }

        //    Мы пропустили начало в src1 и не пропустили начало src2. 
        //    В dst->Begin -- начало штриха
be:         {    
            assert( !src1->IsSentenel() && 
                dst->Begin < src1->End && dst->Begin <= src2->Begin );
            if( src1->End < src2->Begin ) {
                dst->End = src1->End;
                assert( dst->IsValid() );
                dst++;
                src1++;
                goto ee;
            }
            assert( src1->End >= src2->Begin && !src2->IsSentenel() );
            goto bb;
        }

        //    Мы пропустили начало обоих штрихов, 
        //    в dst->Begin лежит начало найденного штриха
bb:        {
            assert( !src1->IsSentenel() && !src2->IsSentenel() &&
                dst->Begin < src1->End && dst->Begin < src2->End );
            if( src1->End < src2->End )
                std::swap( src1, src2 );
            assert( src1->End >= src2->End );
            src2++;
            goto be;
        }

//    заканчиваем копирование src1
copyRestOfSrc1:    {
            assert( src2->IsSentenel() );
            while( !src1->IsSentinel() )
                *dst++ = *src1++;
            assert( src1->IsSentenel() && src2->IsSentinel() );
            *dst++ = *src1++;
            src2++;
        }
    }
    return dst;
}

A>Но мысль в правильном направлении.
A>5. А тут уже можно заняться оптимизацией.
Кажется алгоритм с пересечениями отезков будет немного квадратичным
Представь себе полигоны в виде букв Ш и E с очень большим числом "лапок"...
А ещё полигон может ведь и несвязанным оказаться после пересечения, например...

Здравствуйте, Erop, Вы писали:


E>Да ну? Какая операция нетривильная? Объединение или пересечение?
Тривиально — это DataSet.Fill или Button.Click, все остальное — жуть как сложно
А по поводу попадания в невыпуклый полигон — это можно сделать ваще графически, а не аналитически.

Здравствуйте, akarinsky, Вы писали:

E>>Да ну? Какая операция нетривильная? Объединение или пересечение?
A>Тривиально — это DataSet.Fill или Button.Click, все остальное — жуть как сложно
A>А по поводу попадания в невыпуклый полигон — это можно сделать ваще графически, а не аналитически.
Это как? Будешь рисовать иногда на экране и пользователя спрашивать?

Здравствуйте, Erop, Вы писали:

E>Это как? Будешь рисовать иногда на экране и пользователя спрашивать?

Сделать невидимый монохромный битмап, нарисовать на нем наш полигон в масштабе и проверять попадание на нем. Идеально работает в масштабе 1:n, где n — целое число. Понятно, что при дробных n будут жуткие неточности. Само собой, дробные координаты тоже внесут ошибку.
Но если нужно быстро и для произвольных невыпуклых полигонов, то сгодится.
В игрушках таким образом анализируются попадания.

Здравствуйте, akarinsky, Вы писали:

A>В игрушках таким образом анализируются попадания.
это очень точно надо угадать масштаб...
Если перебдишь -- будет большой объём данных, недобдишь -- ошибки
Так что для произвольных полигонов, ИМХО, страшновато