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

@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, это случайное совпадение?

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

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

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

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

@VTsaregorodtsev 2622 / 1633 / 266 Регистрация: 19.02.2010 Сообщений: 4,335
	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