Интерполяция в многоугольнике - найти значение неизвестной точки

@x_Alex_x · Регистрация: 07.02.2014

Студворк — интернет-сервис помощи студентам

Никак не могу придумать алгоритм. Нужны подсказки.
Итак, условие: есть несколько точек. Их координаты известны. Каждая точка содержит значение. На чертеже я дорисовал эти значения. Значение одной из точек неизвестно. Нужно его посчитать (на чертеже помечено вопросом, в скобках то, что должно получиться).

@VTsaregorodtsev · 06.05.2015, 22:36

Взвешивание обратно пропорционально расстоянию от известной точки до неизвестной точки.

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

@x_Alex_x · 06.05.2015, 22:55 **[ТС]**

Сообщение от VTsaregorodtsev

обратно пропорционально расстоянию от известной точки до неизвестной точки

Не совсем понял, но кажется, я как-то так пытался уже.

Сообщение от VTsaregorodtsev

мозги в полтретьего ночи не работают

Надеюсь у Вас найдётся для меня время завтра)

@VTsaregorodtsev · 06.05.2015, 23:07

x_Alex_x, я, кстати, просмотрел, что нужно совпадение с ответом (4) - может, для этого надо как-то по-другому придумывать. Но мне будет лень подставлять значения-расстояния и проверять, так что...

@x_Alex_x · 06.05.2015, 23:12 **[ТС]**

Чтож, надеюсь ещё найдётся доброволец )

@Igor3D · 07.05.2015, 14:58

Сообщение от x_Alex_x

Чтож, надеюсь ещё найдётся доброволец )

Ну считать за Вас калькуляторе вряд ли кто будет

Задача интерполяции точки по известным - это Вам не "хухры-мухры"

- для трех исходных точек все совершенно однозначно
- для 4 (выпуклых) хорошо подходит bilinear, вероятно от Вас этого и хотят в школе
- для 5 и более... там (если не ошибаюсь) 10 различных методов, в общих чертах: или разные варианты взвешивания, или диаграмма Вороного и там уже своя песня. Конечно все это можно использовать и для 4

Поэтому если метод не указан - наверное читайте bilinear

Добавлено через 10 минут

Сообщение от VTsaregorodtsev

Взвешивание обратно пропорционально расстоянию от известной точки до неизвестной точки.

Возьмем точку на ребре многоугольника, напр (2-5). В ней вес остальных вершин (3, 6) ненулевой. А если мы выскочим из многоугольника, то вместо (3, 6) будут уже какие-то др вершины. Т.е. значения в соседних точках меняются скачком, обычно это неприемлемо.

@x_Alex_x · 07.05.2015, 15:32 **[ТС]**

Сообщение от Igor3D

читайте bilinear

Я уже как-то использовал этот метод. И если я не ошибаюсь, он годится только для прямоугольника.

Сообщение от Igor3D

Ну считать за Вас калькуляторе вряд ли кто будет

Именно поэтому я сделал небольшой набросок в эксель. Он даже почти работает ) Правда только если указывать одинаковые длины отрезков.

@Igor3D · 07.05.2015, 16:28

Сообщение от x_Alex_x

Я уже как-то использовал этот метод. И если я не ошибаюсь, он годится только для прямоугольника.

Не только, для любого выпуклого ("квадлитерала"), вот навскидку ссылочка
https://www.particleincell.com... rpolation/

Добавлено через 33 минуты
Если не хотите возиться, то есть решение проще и тоже с неплохим качеством

- разбиваете 4-угольник на 2 треугольника, смотрите куда попала точка и интерполируете в том тр-ке (там все однозначно). Потом разбиваете на 2 других тр-ка, получаете тем же образом второй рез-т и осредняете

@x_Alex_x · 07.05.2015, 17:44 **[ТС]**

Сообщение от Igor3D

квадлитерал

Гугл не знает этого слова. Как я понял, это искажённый прямоугольник? Но опять же, у меня может быть разное количество вершин.

Сообщение от Igor3D

- разбиваете 4-угольник на 2 треугольника, смотрите куда попала точка и интерполируете в том тр-ке (там все однозначно). Потом разбиваете на 2 других тр-ка, получаете тем же образом второй рез-т и осредняете

Немного изменю алгоритм:
Для каждой вершины многоугольника искать такой треугольник в который входила бы искомая точка, состоящий из этой вершины и двух других соседних друг с другом вершин многоугольника. Суммировать значения, полученные при интерполяции в этом треугольнике. После всех итераций делить сумму на число вершин.
Я проверил. Этот алгоритм работает. Большое спасибо за подсказку!

@Igor3D · 07.05.2015, 18:03

Сообщение от x_Alex_x

Гугл не знает этого слова. Как я понял, это искажённый прямоугольник?

Да, набираете просто "bilinear interpolation q" - и оно Вам допоолнит до этого мудреного латинского слова

Сообщение от x_Alex_x

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

Какое "опять же"? Специально перечитал весь тред - не вижу НИ ОДНОГО упоминания о "разном кол-ве вершин". А разница здесь принципиальная. Товарищ, давайте ценить время свое и других, нечего воздух гонять.

Сообщение от x_Alex_x

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

Ну это все-таки "fake", хотя да, рабочий. Посмотрите
http://geometry.caltech.edu/pubs/MHBD02.pdf
На практике это спорно, но все равно идея интересная

@x_Alex_x · 07.05.2015, 18:21 **[ТС]**

Сообщение от Igor3D

Какое "опять же"?

Сообщение от x_Alex_x

Итак, условие: есть несколько точек.

Так вот же.

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

@Igor3D · 08.05.2015, 08:06

Сообщение от x_Alex_x

Кстати, алгоритм оказался неверным.

Я его использовал не один раз, он хоть и оставляет заметные "ребра", но намного лучше чем просто триангуляция и использование одного тр-ка. Можно немного улучшить ослабив вес "внутреннего" ребра.

Сообщение от x_Alex_x

А при проверке я использовал частный случай, который даёт правильный результат.

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

@x_Alex_x · 08.05.2015, 11:16 **[ТС]**

Igor3D, я использовал примерно такой многоугольник. В первом случае я получил тройку, а во втором что-то около единицы.

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

@x_Alex_x · 08.05.2015, 11:26 **[ТС]**

Хотя ведь всё правильно!

Ведь тройкой во втором случае и не пахнет. Что-то я сам себя запутал. Сейчас перепроверю ещё раз.

@x_Alex_x · 08.05.2015, 11:32 **[ТС]**

Вот это похоже на правду?

@Igor3D · 08.05.2015, 11:55

Сообщение от x_Alex_x

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

Да, ну и на всякий случай: внутри тр-ка интерполяция barycentric. По тому pdf я сам пробовал неск раз - ну не всегда рез-т меня устраивал.

Сообщение от x_Alex_x

Хотя ведь всё правильно! Ведь тройкой во втором случае и не пахнет. Что-то я сам себя запутал. Сейчас перепроверю ещё раз.

Чтобы прочувствовать как это работает: сделайте просто квадрат ABCD, значения в AC = 1, в BD = 0 (крестом). Выведите на экран интерполяцию сначала по первой паре тр-ков, потом по второй, потом среднее. Это будет гораздо быстрее чем муторные просчеты тестовых точек

Добавлено через 11 минут

Сообщение от x_Alex_x

Вот это похоже на правду?

Ну прикинем.

По обеим точкам 1: близко от ребра, что-то типа 0.95 * 2
По обеим точкам 2: тоже близко, где-то 1.95 * 2
По точке -1: на глазок 1.5

Итого (0.95 * 2 + 1.95 * 2 + 1.5) / 5 = 1.46
Да, похоже (все бралось на глаз). Все равно - визуализируйте цветом, не парьтесь с расчетами на бумаге

@x_Alex_x · 08.05.2015, 12:23 **[ТС]**

Igor3D, алгоритм выдаёт неверный результат когда точка находится снаружи треугольника:
1,00 0,75 0,50 0,25 0,00
1,00 0,75 0,50 0,25 0,33
1,00 0,75 0,50 0,50 0,50
1,00 0,75 0,67 0,63 0,60
1,00 0,83 0,75 0,70 0,67
Здесь начало координат слева сверху.
Так и должно быть?
Я использовал эту формулу:

@x_Alex_x · 08.05.2015, 12:52 **[ТС]**

Сообщение от Igor3D

Да, похоже (все бралось на глаз). Все равно - визуализируйте цветом

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

Сообщение от Igor3D

не парьтесь с расчетами на бумаге

Нуу! Какая бумага? Я слишком ленив для этого )

Добавлено через 22 минуты

Сообщение от x_Alex_x

Здесь начало координат слева сверху.

Исправлю. У вершин квадрата такие значения:
1 0
1 0
А треугольник построен на этих вершинах:
* *
* -

@Igor3D · 08.05.2015, 13:55

Сообщение от x_Alex_x

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

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

Добавлено через 3 минуты

Сообщение от x_Alex_x

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

"Ой напрасно тетя Вы таблетки пьете"

Ну как себе хотите

@Shamil1 · 12.05.2015, 07:03

Сообщение от x_Alex_x

Итак, условие: есть несколько точек. Их координаты известны. Каждая точка содержит значение. На чертеже я дорисовал эти значения. Значение одной из точек неизвестно. Нужно его посчитать (на чертеже помечено вопросом, в скобках то, что должно получиться).

А то, что значение в каждой точке равно координате по оси Y, это случайное совпадение?

Новые блоги и статьи Все статьи Все блоги /
изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

@x_Alex_x 20 / 20 / 3 Регистрация: 07.02.2014 Сообщений: 233

	Интерполяция в многоугольнике - найти значение неизвестной точки 06.05.2015, 21:31. Показов 2015. Ответов 20 Метки нет (Все метки) Никак не могу придумать алгоритм. Нужны подсказки. Итак, условие: есть несколько точек. Их координаты известны. Каждая точка содержит значение. На чертеже я дорисовал эти значения. Значение одной из точек неизвестно. Нужно его посчитать (на чертеже помечено вопросом, в скобках то, что должно получиться). Миниатюры 0

@VTsaregorodtsev 2625 / 1636 / 266 Регистрация: 19.02.2010 Сообщений: 4,348
	06.05.2015, 22:36
	Взвешивание обратно пропорционально расстоянию от известной точки до неизвестной точки. Взялся было писать формулу - но мозги в полтретьего ночи не работают, неправильная придумывается. 0

@VTsaregorodtsev 2625 / 1636 / 266 Регистрация: 19.02.2010 Сообщений: 4,348
	06.05.2015, 23:07
	x_Alex_x, я, кстати, просмотрел, что нужно совпадение с ответом (4) - может, для этого надо как-то по-другому придумывать. Но мне будет лень подставлять значения-расстояния и проверять, так что... 0

@x_Alex_x 20 / 20 / 3 Регистрация: 07.02.2014 Сообщений: 233
	06.05.2015, 23:12 [ТС]
	Чтож, надеюсь ещё найдётся доброволец ) 0

@x_Alex_x 20 / 20 / 3 Регистрация: 07.02.2014 Сообщений: 233
	08.05.2015, 11:16 [ТС]
	Igor3D, я использовал примерно такой многоугольник. В первом случае я получил тройку, а во втором что-то около единицы. Сейчас разбираю приведённый Вами pdf. Поправьте меня пожалуйста если я не прав: норма вектора это его длина? Миниатюры 0

@x_Alex_x 20 / 20 / 3 Регистрация: 07.02.2014 Сообщений: 233
	08.05.2015, 11:26 [ТС]
	Хотя ведь всё правильно! Ведь тройкой во втором случае и не пахнет. Что-то я сам себя запутал. Сейчас перепроверю ещё раз. 0

@x_Alex_x 20 / 20 / 3 Регистрация: 07.02.2014 Сообщений: 233
	08.05.2015, 11:32 [ТС]
	Вот это похоже на правду? Миниатюры 0

@x_Alex_x 20 / 20 / 3 Регистрация: 07.02.2014 Сообщений: 233
	08.05.2015, 12:23 [ТС]
	Igor3D, алгоритм выдаёт неверный результат когда точка находится снаружи треугольника: 1,00 0,75 0,50 0,25 0,00 1,00 0,75 0,50 0,25 0,33 1,00 0,75 0,50 0,50 0,50 1,00 0,75 0,67 0,63 0,60 1,00 0,83 0,75 0,70 0,67 Здесь начало координат слева сверху. Так и должно быть? Я использовал эту формулу: Миниатюры 0