Оптимальное расположение триангулярной сетки по заданным точ

[alexiy]

Имеется: ограниченный набор точек на плоскости с известными координатами.
Требуется разработать алгоритм генерации регулярной шестигранной сетки с заданным шагом, чтобы узлы сетки были максимально близки к заданным точкам.

Прошу сориентировать и наставить.

[Macavity]

alexiy писал(а):

...чтобы узлы сетки были максимально близки к заданным точкам.

Это очень неточно (речь идет о максимальном расстоянии до узла или о сумме растояний и т.д.).

[alexiy]

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

[yupa]

alexiy писал(а):

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

Вы не ответили на вопрос. Необходимо четко сформулировать критерий оценки "хорошести" выбора узлов сетки. Например -- сетка тем лучше, чем меньше величина

$$ \max\limits_j\min\limits_i|x_i-a_j|, $$

где $a_j$ -- заданные точки, $x_i$ -- узлы построенной сетки.

Дело в том что в качестве критерия можно выбрать не указанный, а скажем вот такой: необходимо минимизировать величину

$$ \sum\limits_j\min_i|x_i-a_j|, $$

где $a_j$ -- заданные точки, $x_i$ -- узлы построенной сетки. А это будет уже несколько другая задача, потому что например, если так волшебно совпало, что можно сетку просто совместить со всеми точками, кроме одной, расстояние до которой будет $\frac{h}{2},\ h=|x_i-x_{i+1}|,$ то в этом случае первая задача в качестве решения нам даст сетку, нигде не сопдающую с исходно заданными точками, при этом расстояние от узлов сетки до заданных точек всюду будет $\frac{h}{4}.$ Вторая же задача, если только узлов в сетке больше двух, даст в качестве решения сетку, всюду совпадающую с исходнозадаными точками, кроме одной точки, которая окажется на расстоянии $\frac{h}{2}$ от ближайшего к ней узла сетки.

[Zai]

alexiy писал(а):

Имеется: ограниченный набор точек на плоскости с известными координатами.
Требуется разработать алгоритм генерации регулярной шестигранной сетки с заданным шагом, чтобы узлы сетки были максимально близки к заданным точкам.

Я не понял термина "шестигранной сетки" на плоскости. Грани обычно имеют пространственные объекты. На какие конечные ячейки Вы хотите разбить область(трехуголные, четырехугольные или шестиугольные)?

[alexiy]

Прошу прощения, что ввел в заблуждение.
Ячейки создаваемой сетки - равносторонние треугольники с заданной длиной стороны.
Сетку нужно расположить (сдвигая и поворачивая) таким образом, чтобы заданные точки оказались как можно ближе к узлам полученной сетки.
2yupa:
Нужно использовать второй критерий::

[yupa]

alexiy писал(а):

Прошу прощения, что ввел в заблуждение.
Ячейки создаваемой сетки - равносторонние треугольники с заданной длиной стороны.
Сетку нужно расположить (сдвигая и поворачивая) таким образом, чтобы заданные точки оказались как можно ближе к узлам полученной сетки.
2yupa:
Нужно использовать второй критерий::

Тогда вопрос становится уж совсе непонятен. У вас есть координаты точек заданных заранее. Есть координаты точек моделируемой на 1-м шаге итер. процесса сетки. Есть аналитически сформулированный критерий выполнения следующего шага итер. процесса. Что собственно нужно? Програмку написать и выслать почтой?

[alexiy]

Цитата:

Что собственно нужно?

Как строить итерации: последовательно меняя угол поворота сетки (от 0 до $60^o$) и сдвигая на некий начальный шаг (от 0 до $h\sqrt{3}$ по x и y) с последующим дроблением этого шага?
Будет ли обеспечена сходимость?
Нельзя ли повысить оптимальность перебора?

P.S. Прошу прощения за бестолковость. Соображал бы лучше - не просил бы помощи.

[yupa]

alexiy писал(а):

Цитата:

Что собственно нужно?

Как строить итерации: последовательно меняя угол поворота сетки (от 0 до $60^o$) и сдвигая на некий начальный шаг (от 0 до $h\sqrt{3}$ по x и y) с последующим дроблением этого шага?
Будет ли обеспечена сходимость?
Нельзя ли повысить оптимальность перебора?

P.S. Прошу прощения за бестолковость. Соображал бы лучше - не просил бы помощи.

Ага. Ну вот стало боле менее понятно -- требуется видимо построить оптимальный алгоритм поиска сетки. Можно поступить следующим образм: точки сетки все до единой определяются местоположением пары ее различных узлов. Например пусть это будут $z_1,\ z_2.$ Выражая все остальные узлы через $z_1,\ z_2,$ приходим к задаче: требуется найти точку глобального минимума функции:

$$ \sum_j\min_i\bigl|z_i(z_{1,x},z_{1,y},z_{2,x})-a_j\bigr| $$

на множестве

$$\Omega=\biggl\{z_{1,x},z_{1,y},z_{2,x}\ \bigg|\ -h\le z_{1,x}\le h,\ -h\le z_{1,y}\le h,\ z_{1,x}+\frac{h}{2}\le z_{2,x}\le z_{1,x}+h\biggr\}. $$

Здесь $z_{i,x}$ -- $x$-я, $z_{i,y}$ -- $y$-я компонента точек $z_i,$ причем по определению сетки

$$z_{2,y}=\sqrt{h^2-(z_{2,x}-z_{1,x})^2}+z_{1,y}. $$

Надеюсь экстремумы функции трех переменных искать вы умеете.

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

$$ \sum_j\min_i\bigl(z_i(z_{1,x},z_{1,y},z_{2,x})-a_j\bigr)^2 $$

Эта функция принадлежит $C^2(\Omega)$. Удачи.

[Zai]

Цитата:

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

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

Сетки с равносторонними треугольниками сейчас очень редко используются. Почему бы Вам не воспользоваться free mesh сеткой?

[alexiy]

Zai писал(а):

Сетки с равносторонними треугольниками сейчас очень редко используются. Почему бы Вам не воспользоваться free mesh сеткой?

Эта задача не из области компьютерной графики.

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