Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 26 сентября 2021 года; проверки требует 1 правка.
Построение точки Ферма для треугольников с углами, не превосходящими 120°.
Точка Ферма — точка плоскости, сумма расстояний от которой до вершин треугольника является минимальной. Точку Ферма также иногда называют точкой Торричелли или точкой Ферма-Торричелли. Точка Ферма даёт решение проблемы Штейнера для вершин треугольника. В английской литературе точку Ферма также называют изогональным центром (isogonic center) X(13).
История[править | править код]
Точка Ферма впервые предложена Ферма:
“Datis tribus punctis, quartum reperire, a quo si ducantur tres rectæ ad data puncta, summa trium harum rectarum sit minima quantitas”. P. de Fermat, «Œuvres de Fermat», 1679, Livre I, Paris.(лат. “Для трех заданных точек найти четвертую, такую что если от неё провести прямые линии до данных точек, сумма расстояний будет наименьшей”. П. Ферма).
Свойства[править | править код]
Теорема Лестера. В любом разностороннем треугольнике две точки Ферма, центр девяти точек и центр описанной окружности лежат на одной окружности (окружности Лестера).
Построение[править | править код]
Теорема (Э. Торричелли, Б. Кавальери, Т. Симпсон, Ф. Хейнен, Ж. Бертран). Построим на сторонах произвольного треугольника 
Теорема дает алгоритм построения точки Ферма с помощью циркуля и линейки. В нетривиальном случае, когда все углы треугольника меньше
Экспериментальное построение точки Ферма.
Физически эту точку можно построить так: отметим на плоской гладкой горизонтальной поверхности точки 
Замечание[править | править код]
Кстати, на первом рисунке справа центры трёх равносторонних треугольников сами являются вершинами нового равностороннего треугольника (Теорема Наполеона). Кроме того, 
Нахождение точки Ферма. Множители Лагранжа[править | править код]
Есть подход к нахождению точки внутри треугольника, для которой сумма расстояний до вершин треугольника минимальна, заключается в использовании одного из методов оптимизации в математике. В частности, метод множителей Лагранжа и теоремы косинусов.
Мы рисуем линии от точки внутри треугольника до его вершин и называем их X, Y и Z. Кроме того, пусть длины этих линий равны x, y и z соответственно. Пусть угол между X и Y равен α, Y и Z – β. Тогда угол между X и Z равен (2π – α – β). Используя метод множителей Лагранжа, мы должны найти минимум лагранжиана L, который выражается как:
- L = x + y + z + λ1 (x2 + y2 − 2xy cos(α) − a2) + λ2 (y2 + z2 − 2yz cos(β) − b2) + λ3 (z2 + x2 − 2zx cos(α + β) − c2)
где a, b и c – длины сторон треугольника.
Приравнивая каждую из пяти частных производных δL/δx, δL/δy, δL/δz, δL/δα, δL/δβ нулю и исключая λ1, λ2, λ3, в конечном итоге получаем sin (α) = sin (β) и sin (α + β) = – sin (β), поэтому α = β = 120 °. Однако выкладки являются долгим и утомительным делом, и конечный результат охватывает только Случай 2, когда ни один из углов ≥ 120°.
Точка Торричелли[править | править код]
Точка Торричелли — точка треугольника, из которой все стороны видны под углом в
См. также[править | править код]
- Замечательные точки треугольника
- Проблема Штейнера
- Окружность Лестера
- Точки Торричелли
Примечания[править | править код]
Литература[править | править код]
- Энциклопедия для детей / Глав. ред. М. Д. Аксёнова. — М.: Аванта+, 2001. — Т. 11. Математика. — 688 с.
- А. О. Иванов, А. А. Тужилин. Теория экстремальных сетей. — Москва–Ижевск: Институт компьютерных исследований, 2003. — ISBN 5-93972-292-X.
Ссылки[править | править код]
- Точка Ферма
- Точка Торричелли
- Практический пример построения точки Ферма (англ.)
Given a matrix mat[][] consisting of N pairs of the form {x, y} each denoting coordinates of N points, the task is to find the minimum sum of the Euclidean distances to all points.
Examples:
Input: mat[][] = { { 0, 1}, { 1, 0 }, { 1, 2 }, { 2, 1 }}
Output: 4
Explanation:
Average of the set of points, i.e. Centroid = ((0+1+1+2)/4, (1+0+2+1)/4) = (1, 1).
Euclidean distance of each point from the centroid are {1, 1, 1, 1}
Sum of all distances = 1 + 1 + 1 + 1 = 4
Input: mat[][] = { { 1, 1}, { 3, 3 }}
Output: 2.82843
Approach:
Since the task is to minimize the Euclidean Distance to all points, the idea is to calculate the Median of all the points. Geometric Median generalizes the concept of median to higher dimensions
Follow the steps below to solve the problem:
- Calculate the centroid of all the given coordinates, by getting the average of the points.
- Find the Euclidean distance of all points from the centroid.
- Calculate the sum of these distance and print as the answer.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>
using namespace std;
double find(double x, double y,
vector<vector<int> >& p)
{
double mind = 0;
for (int i = 0; i < p.size(); i++) {
double a = p[i][0], b = p[i][1];
mind += sqrt((x - a) * (x - a)
+ (y - b) * (y - b));
}
return mind;
}
double getMinDistSum(vector<vector<int> >& p)
{
double x = 0, y = 0;
for (int i = 0; i < p.size(); i++) {
x += p[i][0];
y += p[i][1];
}
x = x / p.size();
y = y / p.size();
double mind = find(x, y, p);
return mind;
}
int main()
{
vector<vector<int> > vec
= { { 0, 1 }, { 1, 0 }, { 1, 2 }, { 2, 1 } };
double d = getMinDistSum(vec);
cout << d << endl;
return 0;
}
Java
class GFG{
static double find(double x, double y,
int [][] p)
{
double mind = 0;
for(int i = 0; i < p.length; i++)
{
double a = p[i][0], b = p[i][1];
mind += Math.sqrt((x - a) * (x - a) +
(y - b) * (y - b));
}
return mind;
}
static double getMinDistSum(int [][]p)
{
double x = 0, y = 0;
for(int i = 0; i < p.length; i++)
{
x += p[i][0];
y += p[i][1];
}
x = x / p.length;
y = y / p.length;
double mind = find(x, y, p);
return mind;
}
public static void main(String[] args)
{
int [][]vec = { { 0, 1 }, { 1, 0 },
{ 1, 2 }, { 2, 1 } };
double d = getMinDistSum(vec);
System.out.print(d + "n");
}
}
Python3
from math import sqrt
def find(x, y, p):
mind = 0
for i in range(len(p)):
a = p[i][0]
b = p[i][1]
mind += sqrt((x - a) * (x - a) +
(y - b) * (y - b))
return mind
def getMinDistSum(p):
x = 0
y = 0
for i in range(len(p)):
x += p[i][0]
y += p[i][1]
x = x // len(p)
y = y // len(p)
mind = find(x, y, p)
return mind
if __name__ == '__main__':
vec = [ [ 0, 1 ], [ 1, 0 ],
[ 1, 2 ], [ 2, 1 ] ]
d = getMinDistSum(vec)
print(int(d))
C#
using System;
class GFG{
static double find(double x, double y,
int [,] p)
{
double mind = 0;
for(int i = 0; i < p.GetLength(0); i++)
{
double a = p[i,0], b = p[i,1];
mind += Math.Sqrt((x - a) * (x - a) +
(y - b) * (y - b));
}
return mind;
}
static double getMinDistSum(int [,]p)
{
double x = 0, y = 0;
for(int i = 0; i < p.GetLength(0); i++)
{
x += p[i,0];
y += p[i,1];
}
x = x / p.Length;
y = y / p.Length;
double mind = find(x, y, p);
return mind;
}
public static void Main(String[] args)
{
int [,]vec = { { 0, 1 }, { 1, 0 },
{ 1, 2 }, { 2, 1 } };
int d = (int)getMinDistSum(vec);
Console.Write(d + "n");
}
}
Javascript
<script>
function find(x, y, p)
{
let mind = 0;
for(let i = 0; i < p.length; i++)
{
let a = p[i][0], b = p[i][1];
mind += Math.sqrt((x - a) * (x - a) +
(y - b) * (y - b));
}
return mind;
}
function getMinDistSum(p)
{
let x = 0, y = 0;
for(let i = 0; i < p.length; i++)
{
x += p[i][0];
y += p[i][1];
}
x = x / p.length;
y = y / p.length;
let mind = find(x, y, p);
return mind;
}
let vec = [[ 0, 1 ], [ 1, 0 ],
[ 1, 2 ], [ 2, 1 ]];
let d = getMinDistSum(vec);
document.write(d);
</script>
Time Complexity: O(N)
Auxiliary Space: O(1)
Last Updated :
11 May, 2022
Like Article
Save Article
|
|
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code…/code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии “срочно надо”, заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке 
Минимальная сумма расстояний до данных точек
, надо найти такую точку
- Подписаться на тему
- Сообщить другу
- Скачать/распечатать тему
|
|
|
|
Senior Member
Рейтинг (т): 23 |
На плоскости дано конечное к-во точек. Сообщение отредактировано: prografix – 19.03.08, 11:37 |
|
albom |
|
|
Senior Member
Рейтинг (т): 20 |
Цитата prografix @ 19.03.08, 08:08 Расстояние обычное ( квадратный корень от нормы )
|
Странные у тебя понятия об обычном расстоянии. |
AllEX5 |
|
|
Его можно решить, по идее, точно. Посмотрим… Ряд должен сходиться к искомой точке. (Если я ничего не напутал; вроде нет). |
|
prografix |
|
|
Senior Member
Рейтинг (т): 23 |
Есть тут и деление на ноль и сходимость небыстрая. -Added 19.03.08, 11:18 Цитата albom @ 19.03.08, 10:18 Цитата prografix @ 19.03.08, 08:08 Расстояние обычное ( квадратный корень от нормы )
Прикол понял – надо квадратный корень от квадрата нормы. |
|
AllEX5 |
|
|
Функционал тот же F(X0, Y0) = sum(sqrt((Xi-X0)^2+(Yi-Y0)^2)); i). |
 darcus |
|
|
Full Member
Рейтинг (т): 18 |
В справочнике Бронштейна – Семедяева есть простая итерационная формула (наверняка известная тебе), |
|
prografix |
|
|
Senior Member
Рейтинг (т): 23 |
Не видел такого справочника и не знаю о какой формуле идёт речь. |
darcus |
|
|
Full Member
Рейтинг (т): 18 |
Лови: x0,y0 — целевая точка x0(0)=Sum(xi)/N <– 0-приближение x0(k+1)=Sum[xi/sqrt((x0(k)-xi)^2+(y0(k)-yi)^2)] / Sum[1/sqrt((x0(k)-xi)^2+(y0(k)-yi)^2)] Sum — сумма по i; |
|
prografix |
|
|
Senior Member
Рейтинг (т): 23 |
Понятно. Здесь тоже возможны деление на ноль и медленная сходимость. |
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
- Предыдущая тема
- Алгоритмы
- Следующая тема
[ Script execution time: 0,0366 ] [ 15 queries used ] [ Generated: 15.05.23, 14:38 GMT ]
Отсортируйте массив. Рассмотрим некоторое фиксированное K. Пусть для данного K уже посчитана минимальная сумма некоторого числа q, т.е. известно min_sum(q, K). Также для данной пары (q, K) известно число элементов element_count, которые при вычислении min_sum были больше числа q. Тогда легко вычислить, что количество элементов, которые были меньше q, равно (K – element_count(q, K)).
Пусть надо найти min_sum(p, K), где p входит в множество оптимальных соседей числа при вычислении min_sum(q, K).
Так как числа p и q расположены достаточно близко, то наверняка у них достаточно большой набор общих оптимальных соседей. Самое худшее, что может случиться, это то, что числа p и q имеют близкие индексы, но очень большой разрыв по значениям. В этом случае среди оптимальных соседей чисел p и q может не оказаться ни одного общего. Но нет худа без добра, так как любой такой разрыв хоть и отдаляет числа p и q, но “сближает” числа p и r, если они находятся по одну сторону разрыва.
Пересчитываем min_sum*(p, K) = min_sum(q, K) + (p – q) * (K – element_count(q, K)) + (p – q) * element_count(q, K), где min_sum*(p, K) – это минимальная сумма для числа p, при условии, что у пар (q, K) и (p, K) множества оптимальных соседей совпадают. Далее мы пересчитываем min_sum*(p, K), сдвигая множество оптимальных соседей влево или вправо на один индекс в сторону числа p от числа q и проверяя, не нашли ли мы более оптимальное множество. Делаем это, пока min_sum перестало уменьшаться или число q не оказалось на краю этого множества.
Добавлено через 14 минут
Пересчет min_sum(p, K) через min_sum(q, K) по предлагаемому алгоритму занимает не K шагов как в случае вычисления в лоб, а от 1 до K.
Например, для равномерного распределения чисел алгоритм сработает за время O(n). Можно показать, что наихудшее время составляет O(n^2/K). А вы так боялись этого K.
Добавлено через 49 секунд
Могу в деталях ошибаться.
Мне кажется, у вас где-то потерялся физический смысл задачи. Насколько я понимаю, в экономической географии силы притягивания и отталкивания не сводятся к евклидовому расстоянию на плоскости.
Давайте для определённости возьмём задачу где выбрать съемную квартиру. В точке 0.0 есть супермаркет, где всё есть (сильная притягивающая точка), но постоянно толкутся люди (слабое отталкивание). В точке (10,1) есть магазин, где продается еда на каждый день (слабое притяжение) но он не вызывает никакого негатива. И в координатах (10,-1) есть завод, где шум, гам, и работяги (сильная отталкивающая точка).
То, насколько сильно отталкивают и притягивают объекты, должны нам сказать социологи. Для вычисления потенциала притягивания и отталкивания я от балды взял механизм штрафов: чем дальше вы от притягивающей точки, тем жальче вам от неё удаляться, чем ближе вы к отталкивающей точке, тем больнее вам к ней приближаться.
Для притягивающей точки я заложил убывание штрафа к бесконечности – иначе нас бы давно всех порвало от тоски по какому-нибудь гипотетическому Уолл-Марту в гипотетическом Канзас-Сити.
# Штраф для функции притяжения - сначала нарастает, потом убывает. На большом расстоянии уже пофиг, что там притягивает.
def attract(power, distance):
# притягивающая часть - квадратичная сигмоидная функция
p1 = power*distance/np.sqrt(distance+1)
# забывание - степенная функция
p2 = p1*(1/(distance+1))
return p2
# Штраф для отталкивания - постепенно убывает.
def repell(power, distance):
return power*(1/(distance+1))
Конкретный вид потенциалов для притяжения отталкивания я просто выдумал. По-хорошему, нужно проводить исследования среди реальных людей, насколько меняются их отношения к притягательным и отталкивающим местам с расстоянием.
Дальше понятно. Задать потенциал по сумме точек и найти локальный минимум. Глобальный минимум с такими потенциалами искать бесполезно, он находится на бесконечности.
class Point:
def __init__(self, coords, attracting, repelling):
self.coords = np.atleast_2d(coords)
self.attracting_power = attracting
self.repelling_power = repelling
def potential(self, point):
point = np.atleast_2d(point)
distance = np.linalg.norm(point-self.coords)
attracting_penalty = attract(self.attracting_power, distance) if self.attracting_power > 0 else 0
repelling_penalty = repell(self.repelling_power, distance)
return attracting_penalty + repelling_penalty
class Potential:
def __init__(self, points):
self.points = points
def potential(self, v):
resPot = 0.0
for p in self.points:
potential = p.potential(v)
resPot += potential
return resPot
def __call__(self, v):
return self.potential(v)
Вернёмся к примеру.
supermarket = Point((0.0), attracting=10, repelling=0.5)
factory = Point((10, -1), attracting=0, repelling=5)
minishop = Point((10,1), attracting=3, repelling=0)
fn = Potential((supermarket, minishop, factory))
Супермаркет и магазин создают локальные минимумы, фабрика создаёт локальный максимум.
Далее ищем ограниченный локальный максимум и вуа-ля! Жить надо возле супермаркета ))
spo.minimize(fn, x0=(1,0), bounds=((-5, 15), (-10, 10)))
Результат
fun: 1.7733099211366816
hess_inv: <2x2 LbfgsInvHessProduct with dtype=float64>
jac: array([1.54659745, 0.5809764 ])
message: b'CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH'
nfev: 210
nit: 20
status: 0
success: True
x: array([-3.93721209e-09, -4.60977379e-09])
Jupyter Notebook c функциями и графиками
UPDATE
Отвечаю на вопросы, заданные в исходном посте и в комментариях.
Насколько я понял, вы настроились решать именно задачу Вебера, в которой стоимость расположения определяется взвешенной суммой расстояний до фиксированных точек и спрашиваете об универсальном решателе.
-
В
scipy.optimizeесть функцияminimizeкоторая реализует несколько общих методов поиска минимума многомерной функции. В силу своей универсальности функцияminimizeне гарантирует нахождение глобального минимума даже без отталкивающих точек. Например, в конфигурации “кластер близких слабо притягивающих точек и удалённая супер-притягивающая точка” общий метод вполне может “застрять” в локальном минимуме в центре кластера, а не в глобальном возле супер-притягивающей точки. -
С отталкивающими точками в задаче Вебера глобальный минимум может существовать только в том случае, если сумма позитивных весов по модулю больше суммы отрицательных. В противном случае отрицательные веса “перевесят” и глобальный минимум будет
-infна бесконечности. Это как бы намекает, что даже специализированный метод поиска минимумов в задаче Вебера может “сломаться”. Добавление отталкивающих точек полностью меняет задачу. -
Ну и в общем. Я категорически не согласен с применением простейшей линейной функции оценивания для реальных задач “пространственной” экономики. Функции оценивания, ИМХО, должны стремиться к константе на бесконечности – нам совершенно не важно, что там есть вдали. Есть и есть, как фон. Поэтому я за то, чтобы использовать сигмоидные функции, а это совсем другие методы поиска минимумов. Но и в этом случае универсальные минимизаторы из
scipy.optimize.minimizeсмогут застрять в локальных минимумах. -
Не существуют универсальные методы, которые гарантированно находят глобальный минимум. Глобальные минимумы могут находить только специализированные методы, заточенные под конкретную задачу. Но эти методы сразу перестают работать, как только меняется форма функции оценивания. Тот же метод Вайсфельда работает с притягивающими точками, но ломается при отталкивающих. С сигмоидными функциями оценивания он, возможно, справится, но для более конкретного ответа нужно смотреть доказательство сходимости этого метода, какие требования он предъявляет к норме.
-
Соответственно, я предлагаю вам попробовать использовать общие методы из
scipy.optimize, и переходить к специализированным только тогда, когда вы наткнётесь на явные промахи.
