Постановка задачи: Имеется карта мира с беспорядочно расбросанными по ней объектами (аэропорты и самолеты). Рядом с каждым объектом отображается короткое текстовое описание (для аэропорта - трехбуквенный код, например, "GML", для самолёта в аэропорту - бортовой номер и код аэропорта, напр. "UR-82007 GML", для летящего самолёта - бортовой номер и маршрут, напр. "UR-82007 GML-LEJ").
Требуется расположить текстовые описания таким образом, чтобы они не перекрывались друг другом.
Примечание: требуется решить задачу максимально тупым способом "в лоб", чтобы формально задача была решена, но у заказчика впредь пропало всякое желание обращаться к автору с такими вопросами.
Решение.
Итак. Сформулируем и решим задачу для одномерного случая.
Пусть на рабочем отрезке расположены n точек с коордитатами Ai, i=1..n. В районе каждой точки требуется разместить надпись длиной Li, i=1..n, так, чтобы надписи не перекрывались.
Далее, для простоты, длину надписи будем называть весом точки.
Шаг 1. Если надписи двух соседних точек перекрываются (Ax+Lx/2 > Ax+1-Lx+1/2), то эти две точки объединяются в одну.
Объединенная точка находится между двумя исходными, ближе к более тяжелой точке, пропорционально распределению весов точек (Ay = Ax+Lx+1*(Ax+1-Ax)/(Lx+Lx+1)).
Вес объединенной точки равен сумме весов исходных точек (Ly = Lx+Lx+1).
Повторяем первый шаг, пока не останется соседних точек, надписи которых перекрывается.
Шаг 2. Отобразить надписи, считая оставшиеся точки центрами для отрисовки составляющих их элементов.
Решаемость одномерной задачи. Одномерная задача решаема, если сумма весов точек не привышает длины рабочего отрезка.
Двухмерная задача.
При вертикальном эшелонировании надписей, решение двухмерной задачи сводится к решению серии одномерных задач.
Возможная оптимизация: если один из эшелонов оказывается переполненным, то можно распределить часть элементов по соседним эшелонам.
С нетерпением жду возможности продемонстрировать этот бред заказчику.
No comments:
Post a Comment