Найти внутренние точки фигуры, заданной опорными точками

[AlexeyA]

Здравствуйте!
Помогите пожалуйста советом, как решить следующую задачу (может кто-нибудь сталкивался с подобным или есть известные методы решения?).
Пусть на сетке задано некоторое достаточно большое количество точек, которые, если их соединить линией, образуют ту или иную фигуру. Если мы эту линию мысленно проведём, то какие-то точки попадут внутрь фигуры, какие-то останутся снаружи. Вручную сделать это довольно просто - например на следующей картинке слева синим обозначены исходные точки, а на картинке справа красным обозначены точки, которые мы классифицировали как внутренние (понятно, что эта классификация довольно грубая, но всё-таки):

Вопрос в том, есть ли какие-то способы классифицировать эти точки не на глаз, а более или менее строгими математическими способами? В частности, когда у нас не двумерный случай, а трёхмерный?

[ИСН]

ну, есть что-то такое...
ключевые слова: выпуклая оболочка (англ. convex hull).

[Алексей К.]

Выпуклая оболочка множества Вам не подходит? Или Вы про неё не знаете?

[Maslov]

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

(Точка на юго-восток от самой верхней выпуклой оболочке не принадлежит, однако автор покрасил ее в синий цвет).

[AlexeyA]

ИСН, Алексей К. Спасибо, вроде это то, что нужно, надо почитать подробнее!
Я ещё в школе учусь, мы такое не проходили :(
Получается, после работы этого алгоритма мы будем знать координаты всех граничных точек, образующих эту самую оболочку? А классифицировать точки можно будет, проведя луч, например, из каждой точки (0,i), (i,0), (Nmax, i) и (i, Nmax) (i=0..Nmax) и помечать точки как внешние до того момента. пока мы не наткнёмся на границу?

-- 06.10.2011, 13:17 --

Maslov в сообщении #490010 писал(а):

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

(Точка на юго-восток от самой верхней выпуклой оболочке не принадлежит, однако автор покрасил ее в синий цвет).

То есть эта синяя точка, о которой вы сказали, перестанет быть граничной и станет внутренней?

[Maslov]

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

-- Чт окт 06, 2011 14:23:02 --

AlexeyA в сообщении #490011 писал(а):

То есть эта синяя точка, о которой вы сказали, перестанет быть граничной и станет внутренней?

Да. Кроме этого, точка с координатами (4, 4) является внешней вне зависимости от выпуклости оболочки.

[ИСН]

Maslov в сообщении #490013 писал(а):

после ее построения задача классификации точек на внешние/внутренние уже решена

Это если бы у него изначально был массив всех точек - граничных и внутренних. А ведь его нет.

[Maslov]

ИСН в сообщении #490015 писал(а):

Это если бы у него изначально был массив всех точек - граничных и внутренних. А ведь его нет.

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

-- Чт окт 06, 2011 14:31:14 --

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

[AlexeyA]

Я правильно понимаю, что с помощью выпуклой оболочки, например, для такой фигуры, я не смогу классифицировать точки так, как нарисовано?

[Maslov]

Правильно.
Выпуклая оболочка будет содержать отрезок, соединяющий точки (7, 9) и (9, 4). Точки (6, 6), (6, 8) и (7, 5) будут внутренними.

[AlexeyA]

Maslov в сообщении #490020 писал(а):

Правильно.
Выпуклая оболочка будет содержать отрезок, соединяющий точки (6, 8) и (9, 4). Точки (6, 6) и (7, 5) будут внутренними.

Теперь понятно, спасибо.

[ИСН]

Maslov в сообщении #490016 писал(а):

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

Ну, если иметь сразу массив более-менее граничных точек, а потом по сетке искать ещё и внутренние.
Впрочем, теперь понятно, что нужно вообще не это, а бог знает что.

[PAV]

Переношу из математики в Computer Science.

-- Чт окт 06, 2011 15:07:42 --

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

-- Чт окт 06, 2011 15:09:34 --

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

-- Чт окт 06, 2011 15:12:46 --

И еще заголовок сделал более информативным

[AlexeyA]

PAV в сообщении #490032 писал(а):

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

Спасибо, в принципе это не так сложно.

PAV в сообщении #490032 писал(а):

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

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

[PAV]

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