Геометрический центр (не центр тяжести) многоугольника произвольной формы

[alex.gomel.75]

Здравствуйте!

Речь пока про алгоритм. Имеется контур многоугольника, без самопересечений, в остальном по конфигурации - все что можно представить (речь про площадные объекты генпланов - проезды, тротуары, газоны и т.п.). Необходимо программно найти его геометрический центр (не центр тяжести), расположенный обязательно внутри контура, для размещения в этом месте блока с обозначением номера участка. Логика размещения блока должна быть максимально "человеческой". Аналитического алгоритма не нашел вообще никакого. Есть варианты графических решений (создание смещения во внутрь контура, наложение сетки и т.д.), но слишком много частных случаев...

Может кто-то подбросит мысль?

[Alexander.Rivilis]

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

[alex.gomel.75]

Согласен, но это пожалуй наиболее близкое определение. 

[kpblc2000]

ИМХО можно работать по алгоритму наподобие:
1 Найти центр описанного прямоугольника
2. Если центр внутри многоугольника, все ок.
3. Если нет - найти ближайшую точку на многоугольнике к этому центру
4. Найти пересечения луча с многоугольником (допустим, их 6 штук)
5. Выбрать 3 и 4 точки пересечения.
6. Середина между 3 и 4 точкой наверняка и будет вменяемой точкой вставки марки.

[alex.gomel.75]

Для выпуклого многоугольника вполне сработало бы... но при осреднении координат на вогнутом многоугольнике (или частично вогнутом) - результат может быть весьма "интересным". Есть другая идея - разметить многоугольник сеткой, найти самые длинные горизонтальный и вертикальный участок отрезков сетки, принадлежащих контуру. Их точка пересечения - искомый центр. Это будут как раз самые большие визуально участки многоугольника. Понадобиться поправка для "очеловечивания" результата и учета возможности нахождения этого центра вне контура. 

[Alexander.Rivilis]

Вполне приличный алгоритм.

[alex.gomel.75]

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

[Alexander.Rivilis]

---

@alex.gomel.75 wrote:

...Для контуров близким по форме к параллелограмму - не подходит совсем...

---

Почему не подходит?

[alex.gomel.75]

Если стороны контура параллельны - нет выраженного максимума, что первый фрагмент, что последний, что средний  - длина фрагментов сетки одинакова. Можно конечно считать количество одинаковых фрагментов и брать средний... Штатный центроид был бы проще и точнее. Попробую все-таки делить на простые и сложные контуры - как минимум это оптимальней. Но похоже надо пробовать и то и другое.

[IgorSkljarov8965]

Есть такое мнение. Я очень часто задачу автоматизации чего-нибудь рутинного сводил к полуавтоматизации. Например, как я понял Вашу проблему: необходимо пробежаться по большому числу контуров и проставить некий текст внутри каждого контура. Если этот процесс полностью автоматизировать, то нормальный чертежник потом все равно постарается проверить как сработала программа и сдвинуть если что-то неудачно разместилось. Я в этом случае сделал бы так: 
1. прога просит выбрать все интересующие контуры.
2. Формируется список выбранных поллилиний. НАчинает работать цикл.
3. Цикл выбирает первую полилинию, подсвечивает ее, зуммирует экран на точке, допустим, координаты которой представляют среднее арифметическое координат всех вершин данной полилинии, формирует текст надписи или нужный блок, вставляет это в точку первой вершины полилинии или в центр экрана, вызывает команду "Переместить" и передает ей вставляемый объект, координаты первой вершины и запрашивает у пользователя вторую точку переноса.
4. После переноса объекта, список полилиний уменьшаем на один первый член и переходим к началу цикла.
5. После окончания списка полилиний - останов.

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

[alex.gomel.75]

Нумерация контуров была частью общей задачи... и как показывает практика, проверенная ни одним годом работы в проектной фирме , чем меньше пользователь принимает решений именно при выполнении рутинных операций - тем выше качество конечного продукта. Полуавтоматы имеют право быть, но хочется выжать максимум... Спасибо за высказанное мнение.

Видео работы приложения по "сеточному алгоритму":

[IgorSkljarov8965]

Понятно, что это была только часть задачи... Но уточню свою мысль: определить место вставки объекта определенного габарита в "человеческое" место внутри неправильного многоугольника - для меня это не тривиальная задача, поэтому чем долго писать, исследовать и тестировать алгоритм, использовал бы изложенный практический подход. 
Что касается метода сетки, то он тоже не решает 100 %но задачу, так как возможны случаи выхода блока за границы контура хоть краешком, как мне кажется. Ведь если контур изначально уже диаметра блока, то этот случай надо обрабатывать как-то по-другому. Я хотел предложить разбивать многоугольник на треугольники, но проблема та же - проверять на вписываемость и если нет, то предстоит , видимо, непростой перебор вариантов. Мне при разработке тоже хотелось выжать максимум, но дело бесконечно ждать не может...

Спасибо за видео, кстати чем писалось, не подскажете, оно впечатлило как пользователя, но для алгоритмиста слегка не наглядно 

[alex.gomel.75]

Все верно. Упомянутый сеточный алгоритм позволяет определить самый большой участок контура, визуально, по-человечески, куда тяготеет взгляд пользователя. Естественно пришлось учитывать возможность расположения центра за пределами контура, тут все просто - из найденного центра нормаль к контуру, найти все точки пересечения полученного отрезка и контура, отсортировать по удалению от центра, выбрать ближайшую пару, середина этой пары - искомый центр. Таким образом кстати, сразу решалась и сопутствующая проблема - вероятность попадания центра в островки штриховки. Гораздо "интереснее" было определить критерий отбора контура для анализа - либо "сетка" либо центроид...

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

Писал на vlisp, в общей сложности пару дней на это ушло. Неделю приложение в эксплуатации - затраченное на разработку время перекрыто повышением производительности не единожды. Так что игра стоит свеч...

[IgorSkljarov8965]

Спасибо за ответ! Два дня это очень быстро, поэтому согласен, что стоило. И с алгоритмами быстро разобрались, снимаю шляпу!))) Если не в габарит, то я тоже делал вариант с выноской. Но мультивыносок тогда не было, а сейчас уже и не разберусь наверно))) Кстати, не попадалась программа преобразования псевдовыносок с текстом и полилинией в мультвыноску? А с сортиовкой на правильные и неправильные как разобрались? Я когда то пытался алгоритм такой разработать... И как показала эксплуатация: не приходится потом править отдельные случаи непопадания?

[alex.gomel.75]

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

---

IgorSkljarov8965 написано:

...Кстати, не попадалась программа преобразования псевдовыносок с текстом и полилинией в мультвыноску?

---

Не встречалась. По идее несложно написать: выбор текста, выбор близлежащей полилинии, создание мультивыноски - точка вставки (начало полилинии), тело мультивыноски - (конец полилинии), содержимое - найденный текст.

---

IgorSkljarov8965 написано:

...А с сортиовкой на правильные и неправильные как разобрались?

---

Для выбранного контура создавал Минимально Выпуклую Оболочку. Если разница площадей контура и его МВО меньше 20% (значение эмпирическое, для данного вида чертежей) - центроид, иначе "сетка". Прежде чем дошло - пришлось повозиться.

---

IgorSkljarov8965 написано:

...И как показала эксплуатация: не приходится потом править отдельные случаи непопадания?

---

Сколько бы проектировщиков не делали проект по одним и тем же исходникам - результат будет отличаться, но будет схож. Так и тут. С машинной логикой не поспоришь (при условии отсутствия системных ошибок). Есть нюансы при наложении маркера на условные обозначения и т.п., иногда теряется читаемость при распечатке. Но когда маркеров сотни - немного передвинуть один-два не критично. Главное ничего не надо перенумеровывать и ничего не теряется при выборке площадей. Самое страшное в этой работе когда что-то потерялось, а так баланс сходиться с самого начала.