Нахождение точек пересечения, которые образуют прямоугольники

Question

У меня есть несколько линий, описываемых их направлением, а также точка, которая описывает их происхождение. Я должен объединить эти линии, чтобы они образовали прямоугольники, которые могут внутри друг друга, но их края не могут перекрываться. Я также знаю, что начало линий l ie в пределах края прямоугольника, но это не обязательно l ie в середине этого края. По сути, мой ввод может выглядеть примерно так:

И то, что я пытаюсь достичь, выглядит примерно так:

Где каждая линия теперь описывается точками, где она пересекала другие линии, чтобы сформировать правильные прямоугольники.

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

Answer 1

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

Итак, вам необходимо определить цель, например:

• увеличить общее количество покрытых
• увеличить количество прямоугольников
• увеличить количество используемых линий
• ...

Здесь Я пытаюсь максимизировать количество прямоугольников, используя жадный подход. Имейте в виду, что жадный алгоритм никогда не гарантирует, что найдет оптимальное решение, но находит неоптимальное за разумное время.

Теперь в моем алгоритме есть два шага:

1. Найти все возможные прямоугольники
2. Выбрать набор прямоугольников, которые удовлетворяют ограничениям

Шаг 1: Найти все возможные прямоугольники

Две вертикали линии (l & r) плюс две горизонтальные линии (b & t) могут образовывать правильный прямоугольник, если:

1. l.x < r.x and b.y < t.y
2. l.y and r.y are between b.y and t.y
3. b.x and t.x are between l.x and r.x

В следующем псевдокоде Xs и Ys отсортированы списки вертикальная и горизонтальная линии соответственно:

function findRectangles
    for i1 from 1 to (nx-1)
        for i2 from (i1+1) to nx
            for j1 from 1 to (ny-1)
                if (Ys[j1].x>=Xs[i1].x and
                        Ys[j1].x<=Xs[i2].x and
                        Ys[j1].y<=Xs[i1].y and
                        Ys[j1].y<=Xs[i2].y)
                    for j2 from (j1+1) to ny
                        if (Ys[j2].x>=Xs[i1].x and
                                Ys[j2].x<=Xs[i2].x and
                                Ys[j2].y>=Xs[i1].y and
                                Ys[j2].y>=Xs[i2].y)
                            add [i1 j1 i2 j2] to results
                        end if
                    end for
                end if
            end for
        end for
    end for
end

Шаг 2. Выберите действительные прямоугольники

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

function selectRects( Xs, Ys, rects )
    results[];
    sort rectangles by their area;
    for i from 1 to rects.count
        if (non of edges of rects[i] are eliminated)&
                (rects[i] does not partially overlap any of items in results)
            add rects[i] to results;
            Xs[rects[i].left].eliminated = true;
            Xs[rects[i].right].eliminated = true;
            Ys[rects[i].bottom].eliminated = true;
            Ys[rects[i].top].eliminated = true;
        end if 
    end for
end