Клуб API Карт

Выпуклая оболочка

Пост в архиве.

Есть несколько окружностей на плоскости. Как построить красивую выпуклую оболчку(не ломануюлинию, а плавную кривую)? 

5 комментариев
Sergey Konstantinov
28 января 2016, 01:53
Алгоритм быстрой оболочки вроде бы сработает, если научиться искать наиболее удалённую от прямой точку окружности. Оболочка таким образом будет состоять из касательных к окружностям.

Проблема скорее в том, как потсроить их плавно и красиво.

Строить то можно вроде и за O(n^2), где n-кол-во окружностей следующим образом.

1) Рассмотрим все пары окружностей

2) Выберем те которые нужно соединить

3) Соединим их центры, построим перпендикуляры через центры к прямой, соединяющей радиусы

4) Получим 4 точки, соединим их что-то вроде прямоугольника(две соединенные полуокружности)

5) Найдём пересечение всех таких фигур(ну там ещё могут появиться компоненнты связности, т.е. две окружности в одной оболчки, две в другой) 

Но у такого способа есть недостаток -могут образовываться пустоты: 

http://joxi.ru/Yl_YUdg5CbB4Qt7ZqZ4

http://joxi.ru/oWHYUdg5CbBBQ7w6Ofs (полуокружности должны были быть закрашены тоже)

Как вариант можно выбрать только одну из двух таких прямых, такую, чтобы площадь итоговой была максимальна(не совсем представляю как это сделать)

 

Ну и я совершенно не представляю как это карсиво рисовать средстваим JS. + хотелось бы соединять не прямыми, а как Metaball, но это скорее всего будет совсем сложно.

Есть несколько пересеющихся кругов, надо отобразить их общий контур?

Места стыков сглажены внутрь(как если один кружок наложить на другой) или вовне(как если этот стык замазать)?

Те что-то простое или из ряздяда Metaball 

Нужно соединять не только пересекающиеся окружности, а окружности, расстояние между центрами которых не больше k*(R+r) (k=3/2, но константа может измениться). 

 

Если окружности пересекаются - места стыков сглажены вгутрь, но без острых углов.

Хотелось бы наодобии Metaball, но слабо представляю как это реализовать.

 

В API ничего подобного не предусмотрено?

 

В АПИ такие хитрые, да и сильнее менее хитрые шаманства не предусмотрены.

В принципе вам могли бы помочь "heatmaps", но и их у нас нет.

Так как требуемое не очень просто отобрзить как полигонами, так и параметрическими фигурами остается один путь - создать свой "pane", поднять на нем canvas и отрендерить там heatmap.

Как это сделать, и даже готовые скрипты можно найти  в инете (и пару раз в клубе упоминались библиотеки)