Астрономическая задача для программистов
Почему она астрономическая - в самом конце. А сама задача такая.
Вариант 1, простой, но бесполезный.
Дано конечное множество точек на плоскости. Построить выпуклый многоугольник минимальной площади (такой, что его вершинами являются только точки из множества), и найти эту площадь.
Решение, возможно, не самое быстрое, находится сразу. Выбрать произвольную окружность, залючающую все точки множества (это возможно, ибо множество конечно). Выбрать любую точку вне окружности, выпустить из этой точки луч, не пересекающий окружность. Начать вращать луч в каком-то направлении до первого пересечения с точкой множества. Эта точка будет первой вершиной искомого многоугольника. Затем продолжить вращать луч в том же направлении вокруг этой вершины до касания следующей точки множества. И т.д. В итоге построим многоугольник.
Алгоритм нужно еще формализовать, но идея, думаю, понятна.
Вариант 2, реальный, но непонятный.
Есть конечное множество точек в трехмерном пространстве. Построить выпуклый многогранник минимального объема (такой, что его вершинами являются только точки из множества), и найти этот объем.
Если рассуждать по аналогии, то нужно заключить множество в сферу, выбрать точку вне её... А дальше как? Можно, конечно, родить некую плоскость, проходящую через эту точку, а потом вращать её так, чтобы "обернуть" множество, но совершенно неясно, как формализовать процесс, т.е. как вычислисть следующую вершину многогранника.
Задача, таким образом, не математическая, а алгоритмическая.
К астрономии имеет отношение вот какое. Есть облако частиц. Первоначально оно занимает очень небольшой объем вокруг известной точки. Затем частицы начинают двигаться под действием различных сил (в моем случае - гравитация и световое давление). Через какое-то время облако "расплывается". Требуется оценить объем и плотность расплывшегося облака.
Как я делал до сих пор? Рисовал проекции облака на две взаимно перпендикулярные плоскости и перемножал площадь одной проекции на характерную толщину другой. Вполне себе оценка. Но хочется как-то поизящнее.
UPD. Оказалось, задача эта хорошо известна в вычислительной геометрии и называется "построением выпуклой оболочки".
Оригинал этого сообщения находится здесь.
Вариант 1, простой, но бесполезный.
Дано конечное множество точек на плоскости. Построить выпуклый многоугольник минимальной площади (такой, что его вершинами являются только точки из множества), и найти эту площадь.
Решение, возможно, не самое быстрое, находится сразу. Выбрать произвольную окружность, залючающую все точки множества (это возможно, ибо множество конечно). Выбрать любую точку вне окружности, выпустить из этой точки луч, не пересекающий окружность. Начать вращать луч в каком-то направлении до первого пересечения с точкой множества. Эта точка будет первой вершиной искомого многоугольника. Затем продолжить вращать луч в том же направлении вокруг этой вершины до касания следующей точки множества. И т.д. В итоге построим многоугольник.
Алгоритм нужно еще формализовать, но идея, думаю, понятна.
Вариант 2, реальный, но непонятный.
Есть конечное множество точек в трехмерном пространстве. Построить выпуклый многогранник минимального объема (такой, что его вершинами являются только точки из множества), и найти этот объем.
Если рассуждать по аналогии, то нужно заключить множество в сферу, выбрать точку вне её... А дальше как? Можно, конечно, родить некую плоскость, проходящую через эту точку, а потом вращать её так, чтобы "обернуть" множество, но совершенно неясно, как формализовать процесс, т.е. как вычислисть следующую вершину многогранника.
Задача, таким образом, не математическая, а алгоритмическая.
К астрономии имеет отношение вот какое. Есть облако частиц. Первоначально оно занимает очень небольшой объем вокруг известной точки. Затем частицы начинают двигаться под действием различных сил (в моем случае - гравитация и световое давление). Через какое-то время облако "расплывается". Требуется оценить объем и плотность расплывшегося облака.
Как я делал до сих пор? Рисовал проекции облака на две взаимно перпендикулярные плоскости и перемножал площадь одной проекции на характерную толщину другой. Вполне себе оценка. Но хочется как-то поизящнее.
UPD. Оказалось, задача эта хорошо известна в вычислительной геометрии и называется "построением выпуклой оболочки".
Оригинал этого сообщения находится здесь.