6

alt text

Не знаю как правильно называется эта задача. Так же не представляю к чему её отнести. К графам или же к упаковке прямоугольников.

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

  • Точки соединены: ближайшая с ближайшей. То есть это не линия. Могут быть ответвления.
  • Расстояние между точками можно сделать единым. То есть всегда 10 px. Также можно предположить, что направлений может быть только 8. (верх,право-верх,право,право-низ,низ,лево-низ,лево,лево-верх)(это для тех случаев если алгоритм основан на матрице, простой карте 32x32,64x64).
  • Очень желательно иметь возможность задавать интервалы, через которые требуется размешать прямоугольник.

Если где нибудь есть реализация на си/с++ то это просто замечательно.

Нейронные сети здесь помочь не могут?

5
  • 1
    Найдите кривую линию, удалённую от реки на нужное число пикселей, и нанесите кривую надпись (побуквенно) вдоль этой линии. Вроде не сложно. 21 апр 2013 в 7:41
  • 2
    А какое положение называется оптимальным? Без формального определения непонятно, что делать.
    – VladD
    21 апр 2013 в 11:56
  • Я пока сам не очень понял. В атласах где обычные карты, там для дорог, рек вручную название помещается в подходящее место? Ну может быть так: Отсортировать отрезки по направлениям. Сколько у данного отрезка точек подряд с одинаковым направлением. И получить стартовую точку этого отрезка. Но в таком случаи если точки образуют дугу или круг, то получить оптимальное место не удастся. Хотя.. @Egor Skriptunoff Наносить текст побуквенно вокруг каждой точки образующей дугу может быть интересным. Надо подумать.
    – manking
    21 апр 2013 в 12:15
  • 1
    @manking: может, попробовать так: 1. строим окрестность реки (10 px?) 2. для каждой точки окрестности (с некоторым шагом) пробуем разместить текст, начиная с этой точки. поскольку река может виться по синусоиде, направление "производной" нам не поможет, надо перебирать все возможные углы. 3. из всевозможных положений выбираем то, которое (1) не пересекает окрестность, (2) имеет от неё наименьшее суммарное удаление 4. из всех точек выбираем те, где суммарное удаление наименьшее.
    – VladD
    21 апр 2013 в 12:43
  • +ую оформление вопроса
    – user3545
    21 апр 2013 в 13:37

1 ответ 1

1

Из комментария пользователя @VladD:

Можно попробовать так:

  1. Строим окрестность реки (10 px?)

  2. Для каждой точки окрестности (с некоторым шагом) пробуем разместить текст, начиная с этой точки. Поскольку река может виться по синусоиде, направление «производной» нам не поможет, надо перебирать все возможные углы.

  3. Из всевозможных положений выбираем то, которое (1) не пересекает окрестность и (2) имеет от неё наименьшее суммарное удаление

  4. Из всех точек выбираем те, где суммарное удаление наименьшее.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.