Выбор точек внутри многоугольников (вдали от границ)

[histrix]

Даны многоугольники в 2D списками координат вершин (XY).
Нужно выбрать точки внутри многоугольников так, чтобы расстояние от точек до сторон многоугольника было максимальным (т.е. точки должны быть "максимально внутри" многоугольников).

Всё усложняется тем, что многоугольники могут иметь много вершин (порядка 500) и выколотые области внутри себя (т.е. "дырки"). Дырки, естественно, заранее известны, но всё равно усложнение, что многоугольники не всегда сплошные. Пересечений сторон между собой кроме как в вершинах нет.

Хотелось бы получить советы как наиболее просто и быстро (в плане вычислений) выбрать точки.

[Pavia]

histrix
Триангуляция_Делоне

[histrix]

Pavia в сообщении #841157 писал(а):

histrix
Триангуляция_Делоне

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

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

[nikvic]

Pavia в сообщении #841157 писал(а):

Триангуляция_Делоне

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

[histrix]

Исходно я строю многоугольники на плоскости, и надо потом каждый многоугольник "раскрасить" определённым цветом на основании того какое значение принимает функция внутри многоугольника. Т.е. нужно брать внутри каждого многоугольника точки для определения в них значения функции.
Многоугольники (которые, по сути, состоят из кусочно-линейных кривых) чётко разграничивают плоскость на области со "специфическими" значениями функции, т.е. тут проблем нет, проблема только как оптимально взять точки для проверки внутри каждого многоугольника.

Вообще исходная проблема это Д-разбиение (ТАУ), но я описал примерно ситуацию для тех, кто Д-разбиение не знает.

Если много локальных максимумов - не беда, можно их все взять. Главное исключить точки совсем рядом с границей многоугольника (т.к. граница может быть не 100% точной)

[nikvic]

Контур обычно задаётся кольцевым списком вершин. Остров с озёрами - деревом таких списков.
Для раскраски особая точность, наверное, не нужна. Можно попытаться использовать что-нибудь вроде градиентного спуска: скорость изменения мин. расстояние не более единицы. А для выделения подозрительных областей - сетку, сначала - крупную...

[histrix]

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

[nikvic]

histrix в сообщении #841607 писал(а):

Потому точки у границы брать не и стоит, а брать надо поглубже.

Гм, задача-то в этом и состоит

[histrix]

может у математиков на математическом форуме dxdy тоже спросить? Это нормально будет? Если ответ найдётся, я его сюда тоже впишу.

[nikvic]

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

[histrix]

про точку в многоугольнике я в курсе.. Можно ещё лучи кидать (ray casting)...
А вот что такое "полимодальность" не в курсе (в контексте данной задачи особенно)

[nikvic]

histrix в сообщении #842239 писал(а):

А вот что такое "полимодальность" не в курсе (в контексте данной задачи особенно)

Много точек экстремума.
Представьте себе канал с несколькими водохранилищами. В каждом - своя точка максимума расстояния до ближайшего берега.

[histrix]

Я вот думаю, а не построить ли Срединную ось или Скелет. Только вопрос как это попроще сделать. Я вообще не программист. Матлаб с диаграммами Вороного и Делоне имеется. Может на сайте Матлаба чего откопается... Но вообще я рад всем советам как лучше делать (и правильно ли я делаю). Я отпишу, если что хорошее найдётся.

(Оффтоп)

P.S.: Математикам репост темы не понравился... Я того пункта правил и не заметил, уж очень маленький

[nikvic]

histrix в сообщении #842352 писал(а):

Я вообще не программист.

Дай бог разобраться с алгоритмами...

histrix в сообщении #842352 писал(а):

Я вот думаю, а не построить ли

Очень может быть: нужная точка - на скелете. А "расстояние до берега" линейно вдоль каждого ребра.

[histrix]

nikvic в сообщении #842378 писал(а):

Дай бог разобраться с алгоритмами...

(Оффтоп)

Это в плане? Сложные алгоритмы потому что, или в смысле что если с алгоритмами разбираться умею, то не важно, что не программист?