Клуб API Карт

Построение выпуклой оболочки конечного множества точек

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

Здравствуйте. У меня имеется, к примеру, 10 разных точек, они случайным образом отображаются на карте, нужно нарисовать polygon который объеденял бы контур. Если я просто добовляю их, то получается пересекание областей как бы XORом.

 

Нужно вот получить такое http://algolist.manual.ru/maths/geom/convhull/ есть алгоритмы, только не знаю как реализовать алгоритм на js, да и думаю что есть способ по проще. Только вот как. Заранее спасибо.

5 комментариев

Никаких других вариантов кроме как работать честными алгоритмами не предвидиться.

Так же уточните что требуется - нарисовать некую фигуру без XOR(точнее без even-odd типа заливки) или все же построить конвекс на основе ее точек( это совершенно разные алгоритмы и получаемые эффекты)

Вроде как нужно что-то типа http://algolist.manual.ru/maths/geom/intersect/convex_intersect.php

Проблему можно решить также другим путем - изменив тип заливки фигуры SVG(все что не ИЕ), изменить тип заливки в ИЕ( там VML) нельзя.

Ждем ваших комментариев

Следуя данному премеру http://api.yandex.ru/maps/jsapi/examples/mapstylepolygon.html

начал добавлять точки в произвольном порядке на карту методом addPoint(point, index), и вместо залитой области у меня получается порезаная кривая фигура. (если я плохо объясняю то понять что у меня за проблема можно путем переставления в вышеуказанном примере координат, что бы они шли в другом порядке, тогда получится "резаный торт", а не "круглая" Москва)

 

Нужно сделать так что бы из количества точек получить обведенную область как на этом рисунке http://algolist.manual.ru/maths/geom/convhull/gif/chull_ex.gif

 

Спасибо за помощь!

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

АПИ данного функионала не предоставляет.

Такс, о чем же я спрашивал - если нарисовать звезду, так как рисуете ее ручкой - в ее центре получиться дырка( так как полигон сам себя перекроет )

Если посмотроить на ней конвекс - получите образно говоря "знак качества", если использовать алгоритмы трасировки контура( ссылка что я привел ) получиться звезда без дырки.

ПС: и не надо москву на куски резать

Хороший пример со звездой, вот мне знак качества и нужно получить из звезды, я так понимаю нужно сидится и писать алгоритмы на js? А так хотелось бы что бы все как в сказке... :)

других вариантов покуда нет.

Прийдется писать.