алгоритм прилипания панелек при перетаскивании

[anmelegov]

есть некий интерфейс с панельками, которые можно перетаскивать драг эн дропом, я хочу сделать так чтобы панельки "прилипали" друг к другу, а не наезжали друг на друга... каритнка
27910
красным цветом показано как сейчас, синим как я хочу сделать. По идее алгоритм простой, но к концу рабочего дня что-то уже совсем не думается...

Добавлено через 2 минуты
П.С. точка 0,0 панелек в левом верхнем углу

[wvxvw]

Я бы делал сетку и записывал в нее свободные/занятые ячейки. Каждая панелька имела бы заданый размер в ячейках сетки. Чтобы проверить помещается ли панелька ничего лучше обычного перебора всех ячеек сетки не придумать, если минимальный размер панели = одна ячейка. Алгоритм поиска положения ближжайшего к текущему неподходящему наверное проще всего сделать имитируя физику т.е. "прикладывая силу" двигать панельку в каком-то направлении, пока ее нельзя полностью поместить. Почти наверняка есть более сложные алгоритмы как разместить объект на сетке, но почти так же наверняка они более сложные. В общем, этот класс проблем известен как http://en.wikipedia.org/wiki/Packing_problem

[expl]

ИМХО какая сетка, зачем сетка?
- Задаемся допуском TOLERATE, начиная с которого всё будет прилипать;
- берем таскаемую панельку;
- гоним циклом по всем остальным (сложность линейная, не квадратичная - ничего страшного);
- смотрим i-ю панельку если Math.abs(panelI.x - draggedPanel.x) < TOLERATE - то делаем draggedPanel.x = panelI.x и прекращаем перебор;
- снова перебираем панельнки, но делаем то же самое уже для y-координаты.
Вот вобщем-то и всё. Только лучше дополнительно учесть, что если Math.abs(panelI.x - draggedPanel.x) < TOLERATE, но по y панельнки друг друга не перекрывают - то ничего делать не нужно.

[Wolsh]

Оторвать не сможешь.

[Aquahawk]

А ещё можно вокруг таскаемой панельки сделать прямоугольник на TOLERATE в каждую сторону больше, и проверять пересечение его с имеющимися панельками, из них определять ближайшие по осям и к ним прилипать.

[Wolsh]

Строго говоря задача нерешаема, так как нет никакой гарантии, что есть вообще свободное место, в которое панель поместится, не перекрывая ни одну другую панель. Следовательно необходимо при перегруппировке решать и этот конфликт – то есть перемещать еще и остальные панели, чтобы освободить место для таскаемой. И всё это – только при заданном условии, что площадь всех панелей меньше площади экрана.

[Aquahawk]

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

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

[expl]

Оторвать не сможешь.
Чтой-то вдруг? Пользователь оттащил больше чем на допуск - отлепилось. Их же не надо прилепленными таскать, насколько я понял.

[Wolsh]

А, ну если снепить только по отпускании, это конечно проще.
Но попробуйте рассматривать не идеальные ситуации, а возможные.
Как бы в этом задача программиста – сделать не так чтобы нечто работало при соблюдении 100500 идеальных условий, а чтобы работало в случае 100500 враждебных.
Вот на картинке топикстартера представьте что синий прямоугольник УЖЕ там стоит, а красную панельку вот в этом месте отпустили. Куда ей бедной прыгать?
Эта ситуация похожа на надуманную, или она будет происходить в 80% случаев?

[anmelegov]

кароче проще забить да?

Добавлено через 5 минут
ладно, а если не учитывать перекрытие других панелек и прилипать только к той, по которой первым срабатывает хитТест, то какой самый простой способ?

[wvxvw]

ИМХО какая сетка, зачем сетка?
Сетка для того, чтобы меньше проверять. Т.как если минимальный размер панельки 10х10, например, то передвигать на 1 пиксел для того, чтобы посмотреть помещается или нет - как бы нет резона.

[Wolsh]

Антон, панельки все разных размеров или это одинаковые плашки (типа как иконки в Метро)?
Может тут "табличный" способ лучше, о котором говорит wvxvw? То есть панельки снепятся не столько друг к другу, сколько к сетке.
Нет, ну правда, я просто даже визуально не представляю как это может работать так, как Вы описали.
Я понимаю например такой способ, как перемещаются драгом вкладки (табы) в браузере. Все прижаты друг к другу, но когда несешь над ними другой таб, они разъезжаются, освобождая место для отпускания этого таба между.