2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Нахождение центра произвольного многоугольника
Сообщение13.02.2018, 03:08 
Аватара пользователя


05/02/18
31
Новосибирск
Да, спасибо, сейчас как раз читаю аналитическую геометрию для начальной школы чтобы найти этот самый перпендикуляр. А если обе величины отрицательные, то что? Котелок не варит. Значит, если прямая задана параметрически (там что-то связанное с $x = f(t), y = g(t)$), то $t$ будет комплексным?

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение13.02.2018, 09:56 


05/09/16
11468
GANJE в сообщении #1292146 писал(а):
Да, спасибо, сейчас как раз читаю аналитическую геометрию для начальной школы чтобы найти этот самый перпендикуляр.

Высота $h_x$ треугольника со сторонами $x,y,z$, опущенная к стороне $x$ равна $h_x=\dfrac{2S}{x}$ где $S$ - площадь треугольника. Площадь треугольника можно искать по формуле Герона.
Так что сначала определяете является ли треугольник тупоугольным с тупым углом образованным ребром и отрезком от конца ребра до курсора, и если не является, считаете высоту. А если является -- то ваше искомое расстояние -- это расстояние от курсора до одного из концов ребра.
Можно еще по другой формуле высоту искать, раз уж вы на первом шаге все равно вычисляете квадраты длин сторон треугольника, то
$h_x^2=\dfrac{2y^2+2z^2-x^2+\frac{(y^2-z^2)^2}{x^2}}{4}$

-- 13.02.2018, 10:03 --

GANJE в сообщении #1292146 писал(а):
А если обе величины отрицательные, то что?

Это значит, что ваш калькулятор поломался :mrgreen:

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение14.02.2018, 23:57 
Аватара пользователя


05/02/18
31
Новосибирск
Блин, как же всё оказалось просто! У меня есть 2 точки, находим разность и из неё угловой коэффициент $k$. Конечно, надо смотреть, чтобы $dx \ne 0$, если $dx = 0$, то ещё проще - перпендикуляр будет параллелен $Ox$. Находим его $y$, отсюда находим $x$ пересечения, готова точка $O$. Если же $\tg \alpha \ne \infty$, находим по формуле коэффициент перпендикуляра, и с использованием точки находим полное уравнение. Затем решаем систему из двух перпендикулярных уравнений и находим точку. Я обозвала расстояния $d_1$, $d_2$ и $d$, где $d_1$ - расстояние от точки пересечения до первой точки ребра, 2 - до второй, $d$ - длина ребра. И если $d_1$ или $d_2$ больше $d$, то точка находится за пределами отрезка (конечно, достаточно квадратов), и расстоянием до отрезка будет меньшее из $d_i$. А если точка пересечения лежит на отрезке, то расстоянием будет расстояние от точки клика до точки пересечения.

(Оффтоп)

Со всей этой математикой чувствую себя как товарищ на картинке.
Изображение

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

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение15.02.2018, 00:54 
Заслуженный участник


26/05/14
981
Мой долг сказать вам что вы решили задачу сложнее чем предлагал wrest. Но главное чтобы вы были уверены в том что вы делаете.

-- 15.02.2018, 00:58 --


 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение15.02.2018, 02:37 
Аватара пользователя


05/02/18
31
Новосибирск
Придётся нарисовать на бумажке. Беда была в том, что когда была бумажка и желание, не было интернета, а сейчас, когда есть интернет и бумажка, нет желания.
В общем, когда напишу комплекс программ 8-), спрошу имена-фамилии для благодарности в хелпе.

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение15.02.2018, 07:37 


05/09/16
11468
GANJE в сообщении #1292558 писал(а):
И если $d_1$ или $d_2$ больше $d$, то точка находится за пределами отрезка (конечно, достаточно квадратов), и расстоянием до отрезка будет меньшее из $d_i$

Нет, не будет. Вам надо дополнительно посчитать расстояние от курсора до одного из концов ребра, у вас на предыдущих шагах это не нигде не считается.

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение15.02.2018, 13:16 


05/09/16
11468
GANJE в сообщении #1292558 писал(а):
Конечно, надо смотреть, чтобы $dx \ne 0$, если $dx = 0$,

Я бы сказал так. Если длина ребра, в ваших обозначениях это $\sqrt{(dx)^2+(dy)^2}$, существенно меньше чем расстояние от курсора до какого-то из концов ребра (то есть ребро по сути - точка а не отрезок), то за расстояние до ребра можно принять расстояние до одного из концов ребра -- погрешность будет не больше длины ребра, и дальше не считать попадает ли перпендикуляр на ребро или нет.

Вообще, если вы заботитесь о скорости\оптимальности вычислений, я бы наверное посоветовал делать так:
1. Вычисляем длину ребра, пусть будет $x$
2. Вычисляем расстояние до первого конца ребра, пусть будет $y$
3. Если $x/y \ll 1$ (например $<0,001$) то квадрат искомого расстояния $d^2\approx y^2$, конец.
4. Вычисляем расстояние до второго конца ребра, пусть будет $z$
5. Определяем наибольшую из длин $x,y,z$. Если это $x$, то высота точно попадает на ребро, переходим к вычислению высоты, пункт 8. Здесь можно добавить еще проверку: если $\dfrac{y+z}{x}-1\ll1$ то у треугольника почти развернутый угол против ребра, и можно прикинуть чему равна высота.
6. Если наибольшая из длин это $y$, то вычисляем знак у $x^2+z^2-y^2$, если меньше или равно нулю, то треугольник тупоугольный с тупым углом против $y$ или прямоугольный с гипотенузой $y$, тогда квадрат искомого расстояния $d^2=z^2$, конец. Если $x^2+z^2-y^2>0$, переходим к пункту 7.
7. Наибольшая из длин это $z$, вычисляем знак у $x^2+y^2-z^2$, если меньше или равно нулю, то треугольник тупоугольный с тупым углов против $z$ или прямоугольный с гипотенузой $z$, тогда квадрат искомого расстояния $d^2=y^2$, конец. Если $x^2+y^2-z^2>0$, переходим к пункту 8.
8. Оба угла, прилежащие к ребру острые, высота попадает на ребро, вычисляем её квадрат $d^2=\dfrac{2y^2+2z^2-x^2+\frac{(y^2-z^2)^2}{x^2}}{4}$, конец.

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение15.02.2018, 14:54 
Заслуженный участник


26/05/14
981
Надеюсь, что это будет проще:
Код:
# расстояние от отрезка [a, b] до точки c
# все точки представлены в виде массивов из двух элементов a = [ax, ay]
def dist(a, b, c):
  ab = sub(a, b) # вектор разницы межу двумя точками
  bc = sub(b, c)
  alpha = dot(ab, bc) / dot(ab, ab)

  if alpha < 0: # перпендикуляр опирается на прямую ab "правее" конца отрезка (b)
    return dist(b, c) # расстояние до конца отрезка (b)

  if alpha > 1: # перпендикуляр опирается на прямую ab "левее" начала отрезка (a)
    return dist(a, c) # расстояние до начала отрезка (a)

  # перпендикуляр попадает на отрезок
  # основание перпендикуляра опущенного из c на прямую ab
  d = add(mul(alpha, a), mul(1 - alpha, b))
  return dist(d, c)

def sub(a, b): # возвращает вектор - разницу точек/векторов
def add(a, b): # возвращает вектор - сумму точек/векторов
def mul(f, a): # возвращает вектор умноженный на число [f * a[0], f * a[1]]
def dot(a, b): # возвращает число - скалярное произведение векторов
def dist(a, b): # возвращает число - расстояние между точками

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение15.02.2018, 17:10 


05/09/16
11468

(slavav)

slavav
у вас там кажись два разных определения dist

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение15.02.2018, 17:44 
Заслуженный участник


26/05/14
981
wrest в сообщении #1292678 писал(а):

(slavav)

slavav
у вас там кажись два разных определения dist

Да. Это псевдокод на некотором языке который разрешает перегрузку по числу аргументов.

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение21.02.2018, 06:50 
Аватара пользователя


05/02/18
31
Новосибирск
Прошу прощения, что долго не отвечала.
Точка на прямой может пригодиться как в других программах векторной графики. Если точка пересечения попадает на отрезок, надо предложить её как точку разбиения, а если не попадает, то предложить разделить ребро пополам.

 Профиль  
                  
 
 Re: Нахождение центра произвольного многоугольника
Сообщение17.06.2020, 16:16 
Аватара пользователя


05/02/18
31
Новосибирск
Задача расстояния до отрезка решена. Я очень умная, поэтому посмотрела как в учебнике (в конце концов, пользуюсь же я ножами или ноутбуками, сделанными другими людьми). Словосочетание "линейная алгебра" ужасает, а ведь есть ещё и нелинейная! Как хорошо, что умные люди решили всё 100 лет назад, а ещё написали про это так, что невоенные могут легко понять.
Изображение

Теперь возникает другой вопрос: корни тяжёлые, а если отрезков много, тысяч 50, например, то даже Пентиум-2 затормозит. Поэтому можно использовать квадраты - если расстояния >1 (да?).
Родилась такая эвристика: чем читать учебник, не проще ли взять сумму квадратов расстояний до хвостов отрезка? Правда, тут беда: отрезки-то разные! Как на картинке.
Изображение
M лежит прямо на AB, но расстояние посчитается больше, чем до BC.

Не беда! Домножим сумму квадратов расстояний так, как относятся квадраты длин отрезков. То есть поделим AB на BC, и на полученное число умножим "расстояние" до отрезка BC. Когда отрезков много, находим самый большой и самый маленький и получаем общий множитель для всех "расстояний". Всяко интереснее, чем определители считать. Почему-то такая тактика не работает: отношения расстояний получаются неправильные. :cry:
Почему? Поможете найти контрпример? Просто любопытно...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group