2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 12:47 
Аватара пользователя
ну, есть что-то такое...
ключевые слова: выпуклая оболочка (англ. convex hull).

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 12:48 
Выпуклая оболочка множества Вам не подходит? Или Вы про неё не знаете?

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 13:10 
Насколько я понимаю, здесь речь идет о построении невыпуклой оболочки, т. е. замкнутой полилинии без самопересечений, охватывающей все точки совокупности и ограничивающей минимальную площадь.

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

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

-- 06.10.2011, 13:17 --

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

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


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

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

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

AlexeyA в сообщении #490011 писал(а):
То есть эта синяя точка, о которой вы сказали, перестанет быть граничной и станет внутренней?
Да. Кроме этого, точка с координатами (4, 4) является внешней вне зависимости от выпуклости оболочки.

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 13:23 
Аватара пользователя
Maslov в сообщении #490013 писал(а):
после ее построения задача классификации точек на внешние/внутренние уже решена
Это если бы у него изначально был массив всех точек - граничных и внутренних. А ведь его нет.

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 13:25 
ИСН в сообщении #490015 писал(а):
Это если бы у него изначально был массив всех точек - граничных и внутренних. А ведь его нет.
Стесняюсь спросить: а как можно построить выпуклую оболочку, не имея массива (или какой-нибудь другой коллекции) всех точек?

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

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

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 13:31 
Я правильно понимаю, что с помощью выпуклой оболочки, например, для такой фигуры, я не смогу классифицировать точки так, как нарисовано?
Изображение

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

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 13:39 
Maslov в сообщении #490020 писал(а):
Правильно.
Выпуклая оболочка будет содержать отрезок, соединяющий точки (6, 8) и (9, 4). Точки (6, 6) и (7, 5) будут внутренними.


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

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 13:47 
Аватара пользователя
Maslov в сообщении #490016 писал(а):
Стесняюсь спросить: а как можно построить выпуклую оболочку, не имея массива (или какой-нибудь другой коллекции) всех точек?

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

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 14:03 
Аватара пользователя
 i  Переношу из математики в Computer Science.


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

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

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

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

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

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

 
 
 
 Re: Классификация точек множества
Сообщение06.10.2011, 16:40 
PAV в сообщении #490032 писал(а):

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



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

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

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



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

 
 
 
 Re: Найти внутренние точки фигуры, заданной опорными точками
Сообщение06.10.2011, 16:48 
Аватара пользователя
При изменении границ нужно будет аккуратно следить, чтобы ни одна из синих точек не оказалась снаружи.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group