Нахождение центра произвольного многоугольника

[GANJE]

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

[wrest]

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 писал(а):

А если обе величины отрицательные, то что?

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

[GANJE]

Блин, как же всё оказалось просто! У меня есть 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$. А если точка пересечения лежит на отрезке, то расстоянием будет расстояние от точки клика до точки пересечения.

(Оффтоп)

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


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

[slavav]

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

-- 15.02.2018, 00:58 --

[GANJE]

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

[wrest]

GANJE в сообщении #1292558 писал(а):

И если $d_1$ или $d_2$ больше $d$, то точка находится за пределами отрезка (конечно, достаточно квадратов), и расстоянием до отрезка будет меньшее из $d_i$

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

[wrest]

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}$, конец.

[slavav]

Надеюсь, что это будет проще:

# расстояние от отрезка [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): # возвращает число - расстояние между точками

[wrest]

(slavav)

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

[slavav]

wrest в сообщении #1292678 писал(а):

(slavav)

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

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

[GANJE]

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

[GANJE]

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


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

M лежит прямо на AB, но расстояние посчитается больше, чем до BC.

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