Нахождение границы множества

Форум для обсуждения вопросов математики

Модератор: Admin

aBoomest
Сообщения: 5
Зарегистрирован: Ср дек 10, 2014 10:33 am

Нахождение границы множества

Сообщение aBoomest » Ср дек 10, 2014 11:03 am

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

Kitonum
Сообщения: 2083
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Re: Нахождение границы множества

Сообщение Kitonum » Ср дек 10, 2014 1:23 pm

aBoomest писал(а):Доброго дня.
Есть задача. Рассмотрена ли она математиками, не знаю. Пробовал сформулировать разными способами и задать в гугле - поиски не увенчались успехом. Может быть кто знает, решалась ли такая задача классиками, или может быть современниками.
Есть множество точек на плоскости. Необходимо найти границу области, такую чтобы все точки множества (за исключением тех которые лежат на границе) были внутри области. Т.е. нужно среди всех точек найти такое подмножество точек, последовательно соединив которые мы определяем ломаную линию внутри которой лежат все остальные точки множества.
Изображение

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

Пример с 8 точками (3 способа выбора границы, есть и другие способы):
Изображение
Однозначно определён только последний способ. Это называется выпуклая оболочка множества. Вот пример нахождения такой оболочки в Maple для 100 случайных точек в квадрате 0..10 (точки с целыми координатами):

L:=[seq(RandomTools[Generate](list(integer(range=0..10),2)), i=1..100)]; # Список случайных точек
H:=simplex[convexhull](L); # Список точек, определяющих выпуклую оболочку
A:=seq(plottools[disk](L[i],0.1, color=red), i=1..100):
B:=plottools[curve]([op(H),H[1]],color=blue,thickness=3):
plots[display](A,B);

Изображение

aBoomest
Сообщения: 5
Зарегистрирован: Ср дек 10, 2014 10:33 am

Сообщение aBoomest » Чт дек 11, 2014 9:49 am

Все верно подмечено.
Как раз ради того что не знаю как определить критерий из-за того, что способов очень много, и решил написать на форуме.

Да, возможны вогнутости границы множества. (наиболее вероятно - одна вогнутость)

Что делать, еще не придумал :(
С уважением.

aBoomest
Сообщения: 5
Зарегистрирован: Ср дек 10, 2014 10:33 am

Сообщение aBoomest » Пт дек 12, 2014 9:22 am

Может кто-нибудь привести в пример конкретный критерий того как именно можно соединять точки для нахождения границы?
С уважением.

aBoomest
Сообщения: 5
Зарегистрирован: Ср дек 10, 2014 10:33 am

Сообщение aBoomest » Ср дек 17, 2014 8:32 am

Поиски в интернете ничего не дали до сих пор.
Есть у кого идеи?
С уважением.

Markiyan Hirnyk
Сообщения: 1354
Зарегистрирован: Вс дек 04, 2011 11:07 pm

Идея сфинкс

Сообщение Markiyan Hirnyk » Пт дек 19, 2014 9:58 am

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

aBoomest
Сообщения: 5
Зарегистрирован: Ср дек 10, 2014 10:33 am

Сообщение aBoomest » Вс дек 21, 2014 1:04 pm

Спасибо, обязательно обдумаю эту возможность.
С уважением.