Математики ауууу. Проверка вхождения точки в отрезок

Можешь нарисовать, как ты видишь «ширину» твоего отрезка?

Типовая задача, наверняка гуглится первой ссылкой для популярных ЯП.

Всё хорошо, но вот если точка C-vec2 как бы с лева или с права от отрезка и явно не входит в отрезок то всё равно определяется что отрезок содержит точку, я чёт не могу допетрить что я делаю не так, туплю =)

В твоем коде «ширина» содержит окружность радиуса width вокруг А и B.

Считать лень, но всё решается первыми двумя формулами https://ru.wikipedia.org/wiki/Расстояние_от_точки_до_прямой_на_плоскости#Прям...

Пусть `a` начало отрезка, `b` — конец, `c` — точка.

1. Если точка лежит на той же прямой, что и отрезок, то ориентированная площадь образованная векторами `(b - a)` и `c - a` равна нулю. Иначе говоря, равно нулю внешнее или косое произведение этих векторов.
2. Если `с` лежит внутри отрезка, то расстояние между `a` и проекцией `c` на прямую положительно направлено и меньше длины отрезка. Иначе говоря, скалярное произведение векторов `(b - a) / |b - a|` и `c - a` больше нуля но меньше чем `|b - a|`.

Попрошу без математических формул, я в них не разбираюсь

Ну извини, без линейной алгебры никак.

Если точка С справа или слева от А или Б (выходит за рамки отрезка), то сумма двух расстояний C-A и C-B будет больше ширины твоего отрезка, значит, не лежит C в отрезке A-B

Офигенная тема.

«Ничего не понимаю, ничего не хочу понимать, формулы не пишите, напишите мне код!»

Мальчик, уходи из программирования. Будет лучше, чем твой говнокод кому-то исправлять постоянно.

Понял, спасибо

ага )

Мальчик, уходи из программирования. Будет лучше, чем твой говнокод кому-то исправлять постоянно.

Дядя, кто тебе сказал что во первых я программист, во вторых читать учись я сказал псевдокод, а не готовое решение, в третьих никто мой код кроме меня и так не видит (исключая огрызки в постах, но это не в счёт)

Не будь таким нервным и попей чайку с ромашкой =)

Спасибо

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

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

Попробую, мне ещё бы как бы побыстрее всё это высчитывать надо =) Ибо по итогу мне надо искать на кривых, ну как на кривых, на полуотрезках короче.

Ну я просто с OpenGL lines разбирался, для типа там задела на нодную систему или графики там делать всякие, мне подсказали и я просто добавил учёт границ

//нахожу вхождение точки в отрезок
tatic bool ui_line_contains_point_point(vec2 start, vec2 end,float width, vec2 point)
{
   if (!( (start.x <= point.x && point.x <= end.x) || (end.x <= point.x && point.x <= start.x) ))
   {
        return false;
   }
   if (!( (start.y <= point.y && point.y <= end.y) || (end.y <= point.y && point.y <= start.y) ))
   {
        return false;
   }

   float m = (end.y - start.y) / (end.x - start.x);
   float b = start.y - m * start.x;
   return (fabs(point.y - (m*point.x+b)) < width);

}

//а потом этим прохожусь по всем полуотрезкам линии(кривой)
bool ui_line_contains_point(ui_line * line, vec2 point,int * point_id)
{
    for (int i = 0; i < line->num_points-1; ++i)
    {
        if(ui_line_contains_point_point(line->points[i],line->points[i+1],line->width,point))
        {
            if(point_id)
            *point_id = i;
            return true;
        }
    }
    if(point_id)
    *point_id = -1;
    return false;
}

В результате всё вроде корректно работает https://youtu.be/zrIfaW8osQI , но я думал можно ещё как то хакнуть матемачитеским выкрутасом каким-то которого я не знаю =) Полуотрезков может быть по итогу очень много и над каждыми vec2 start, vec2 end всё это считать чёт жирно, но по другому я хз как, ну разве что #pragma omp parallel for добавить и забить за оптимизации =)

А разве это задача уже не решена во всяких opengl frameworks? Это же типичная задачка из компьютерной графики, кстати вот статья https://habr.com/ru/post/257655/ http://nehe.gamedev.net/tutorial/collision_detection/17005/

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

насколько помню, это делалось подстановкой проверяемой точки в уравнение прямой, содержащей отрезок

без линейной алгебры никак.

тут скорее аналитическая геометрия

произведение векторов `(b - a) / |b - a|` и `c - a`

правильная формула: (b - a) . (c - a) / |b - a|^2

Ради интереса скостылял вот, может пригодится. Нулевые отрезки и прочие граничные хрени не тестил, естественно.

var p = console.log
var {sin, cos, atan2} = Math

var A = {x:0, y:0}
var B = {x:10, y:5}
var w = 1

p('inside:', inside(A, B, w, {x:5, y:3.0}))
p('inside:', inside(A, B, w, {x:5, y:3.1}))

function inside(A, B, w, C) {
    p('C:', C)

    // make A new origin
    B.x -= A.x
    B.y -= A.y

    // make B new x-axis
    var a = atan2(B.y, B.x)
    B = rot(B, -a)
    C = rot(C, -a)

    var h = w / 2

    p('new B:', B)
    p('new C:', C)

    return (
        (C.x >= 0 && C.x <= B.x) &&
        (C.y <= h && C.y >= -h)
    )

    function rot(v, a) {
        return {
            x: v.x * cos(a) - v.y * sin(a),
            y: v.x * sin(a) + v.y * cos(a),
        }
    }
}

Расстояние точки до прямой

Забыл A из C вычесть конечно же.

youtube

А че это за хренотень пилишь? Чтобы точки не отрывались при перемещении, делай софтовый граб, не опирайся на ширину. При клике проверяешь inside, ставишь global drag_point = mypoint, и при mousemove двигаешь drag_point, если он не null. По release ставишь в null. Чтобы за пределы окна тащить, нужен хард граб, но хз доступен ли он в твоем уи.

То же самое, просто лежит в [0; 1] вместо [0; |b - a|].

Есть отрезок A-vec2,B-vec2 с шириной width

прямо в первом сообщение, громко вопрошали - нарисуй на милимметровке!! У отрезков/линий физически нет толщины, а если она есть, то это в лучшем случае трапеция. Для линии нет операции «точка ей принадлежит (то есть внутри)».

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

и в любом случае всё-же надо для себя решить что такое «width» и как оно отсчитывается. по X ? по Y ?? по нормали..что делать с дробными значениями, что с краевыми которые вне bound-dox

да, точняк

(start.x <= point.x && point.x <= end.x) || (end.x <= point.x && point.x <= start.x)

Это неправильный способ. Я конечно не знаю специфики твоей задачи, но в общем случае ты так легко не отделаешься. Скажем, если отрезок ровно вертикальный (start.x == end.x), то эта функция тебе будет почти всегда возвращать false, даже если точка лежит внутри прямоугольника. Аналогично с ровно горизонтальным.

Для правильного решения тебе надо будет пойти сюда https://ru.wikipedia.org/wiki/Расстояние_от_точки_до_прямой_на_плоскости и посмотреть формулы для расстояния от точки до прямой, и для координаты наиболее близкой точки. Дальше тебе надо чтобы расстояние было не больше полуширины, а наиболее близкая точка лежала в пределах отрезка. Так будет работать. Кстати, чтобы не грузить проц корнями, имеет смысл сравнивать квадрат расстояния.

Эх, ща пойду разберусь, сначала вспомогательное доделать надо, а потом вернусь опять к точкам.

0) переходишь в систему отсчёта начала отрезка
1) проецируешь точку на прямую, на которой задан отрезок
2) проверяешь входит ли проекция в отрезок
3) если входит, проверяешь расстояние от проекции до точки больше ли оно толщины отрезка

Ну у меня два способа определения наличии точки, первая это просто истинная точка не имеющая ширины ну например когда указатель мыши пересекает отрезок и вот именно тут определяется что да полуотрезок от общей кривой пересекает координаты указателя, при этом кривая линия состоит как сказал из полуотрезков начало и конец которых являются явно заданными «точками» при этом и линия и явно заданные точки имеют ширину как + offset в каждом направлении от точки и тут уже включается другое, а именно вхождения координат например указателя в position_vec2 + offset_vec2. Первый вариант это когда мне нужно точно зна координаты на экране, задавать или получать точные значения координат, второй это относительные расчёты что бы я мог при надобности визуально задать размер точки в 10px к примеру и явно тыкнуть в неё мышкой, например если я хочу редактировать кривую, ну банальный пример реализовать нодную систему к примеру. В общем случае я хочу просто сделать для себя просто графический элемент типа линия, как окно и всё остальное и там уж делать из этого что мне потребуется в моём быдлогамедеве =) Ну вот как-то так

А че это за хренотень пилишь?

Это просто форк Corange, который адаптирую под игру свою, сейчас просто стали нужны линии

Чтобы точки не отрывались при перемещении, делай софтовый граб, не опирайся на ширину.

Точки не могут оторваться от линии это её часть просто режит отображения точек, да и в целом на видосе просто тестирование линии как ui элемента. Её задача только предоставлять api для создания/удаления/изменения, а уж что по итогу из неё делать дело десятое. Такалка мышкой это самый просто вариант тестирования по всем фронтам.

но хз доступен ли он в твоем уи.

Это и есть одна из реализаций ui элемента ))))) У меня на руках только SDL2 / C / OpenGL и всё =)

Ухх, ну я хз , попробую.

Спасибо за старания, как вернсь к точкам попробую

А разве это задача уже не решена во всяких opengl frameworks?

Не знаю, наверное, я весипедист =)

там всё просто
делается это на векторах
переход в систему координат начала отрезка — это значит ты из координат точки B отрезка вычитаешь координаты точки A отрезка.
Пусть это будет вектор V1.

Потом из координат проверяемой на пересечение точки C вычитаешь так же координаты точки A отрезка.
Это будет вектор V2.

Теперь тебе надо спроецировать V2 на V1, для этого умножаешь длину V2 на нормализованный вектор(направление) V1.
Получается вектор V3.

Теперь смотришь чтобы V3 лежал в пределах V1. Для этого можно проверить что они сонаправлены и длина V3 <= длине V1(с добавкой «толщины» линии).

Если V3 лежит на V1(если не лежит то значит дальше можно не проверять), тогда берёшь новый вектор V4 как вычитание координат V2 - V3. Сравниваешь длину V4 с «толщиной» линии и точки (если меньше или равно то линия касается точки).

Так, вернулся я кточкам, вроде разобрался и всё стало работать корректно, ну я ещё проестирую, сами расчёты да ты прав, просты

   vec2 v1 = vec2_sub(end,start);
   vec2 v2 = vec2_sub(point,start);
   vec2 v3 = vec2_mul(vec2_normalize(v1),vec2_length(v2));

   if(vec2_length(v3) > vec2_length(v1)){
       return false;
   }

   vec2 v4 = vec2_sub(v2,v3);
   if(v4.x <= width && v4.y <= width){
       return true;
   }

    return false;

эхх, хорошо думать головой, а не жопой как я ))))))) спасибо!

https://youtu.be/5Nl4vswFBlA <<< Всё вроде корректно (хотя иногда огрехи проступают, хотя может где в визуализации просто косяк)

Тут кто-то подписался на тему поэтому выложу сразу расчёты без зависимостей, может кому пригодится.

typedef struct
{
    float x;
    float y;
}vec2;

static bool ui_line_contains_point_point(vec2 start, vec2 end,float width, vec2 point)
{
   //--------------------------------------------------
   // precheck collide
   //--------------------------------------------------
   if (!( (start.x <= point.x && point.x <= end.x) || (end.x <= point.x && point.x <= start.x) ) && start.x != end.x){
        return false;
   }
   if (!( (start.y <= point.y && point.y <= end.y) || (end.y <= point.y && point.y <= start.y) ) && start.y != end.y){
        return false;
   }

   //--------------------------------------------------
   // check collision version 2
   //--------------------------------------------------
   vec2 v1 = (vec2){end.x - start.x, end.y - start.y};
   vec2 v2 = (vec2){point.x - start.x, point.y - start.y};

   float v1_lenght = sqrt(((v1.x * v1.x)+(v1.y * v1.y)));

   vec2  v1_normal = (vec2){ v1.x / v1_lenght,  v1.y / v1_lenght};

   float v2_lenght = sqrt(((v2.x * v2.x)+(v2.y * v2.y)));

   vec2  v3 = (vec2){v1_normal.x  * v2_lenght, v1_normal.y * v2_lenght };

   float v3_lenght = sqrt(((v3.x * v3.x)+(v3.y * v3.y)));

   if(v3_lenght > v1_lenght){
       return false;
   }

   vec2 v4 = (vec2){ v2.x - v3.x, v2.y - v3.y }; 

   if(v4.x <= width && v4.y <= width){
       return true;
   }

   return false;

}

эхх, хорошо думать головой, а не жопой как я

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

if(vec2_length(v3) > vec2_length(v1)) return false;

Перед этим надо проверить что они сонаправлены, насколько помню скалярное произведение должно быть больше нуля

if(vec2_scalarProduct(v1,v3) < 0 || vec2_length(v3) > vec2_length(v1)) return false;

if(v4.x <= width && v4.y <= width)

так нельзя
тут должно быть vec2_length(v4) <= width, либо, чтобы была выше производительность то выкинуть квадратный корень и соответственно возвести во 2ю степень толщину

vec2_scalarProduct(v4,v4) <= width*width

А, да, тьфу, спасиб

Есть отрезок A-vec2,B-vec2 с шириной width

Это называется прямоугольник.

Есть ещё способ с комплексными числами.

Пусть A и B - комплексные числа, соответствующие концам отрезка. X - комплексное число, соответствующее проверяемой точке.

def wtf(A, B, w, X):
  X = X - A
  B = B - A
  T = X * conj(B) / abs(B)
  along = 0 < real(T) < abs(B)
  across = abs(imag(T)) < w
  return (along and across)

Сорян за питонокод, но тут всё очевидно, и кроме проверки на A≠B ничего особого вроде бы дополнительно не нужно.

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

  bool tlx = ( pos.x > top_left.x     );
  bool tly = ( pos.y > top_left.y     );
  bool brx = ( pos.x < bottom_right.x );
  bool bry = ( pos.y < bottom_right.y );

  return ( (tlx) && (brx) && (tly) && (bry) );
   

Это будет работать? p_P щя попробую, спасиб

Математики ауууу

Могу напомнить вам таблицу умножения...

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

В принципе, видно из Дуальности Ходжа для двумерия i=(e_x)∧(e_y).

можно напрямую 0<(B,X)<(B,B) && |[B,X]|^2 < w^2 * |B|^2 , где (,) - скалярное произведение, [,] - векторное. Квадраты во втором условии - т.к. наверно быстрее пару раз возвести в квадрат, чем извлекать корень.

(a,b) = a.x*b.x+a.y*b.y; |[a,b]| = |a.x*b.y-a.y*b.x|

Как-то так. Но тебе с такими вопросами и правда следовало бы открыть школьные учебники. Лезть в программирование не зная школьной программы?

В случае линейной алгебры лучше всё-таки брать не школьные учебники, а нормальные.

Лезть в программирование не зная школьной программы?

Вот такой я нехороший =) Базовые вещи я начисто забыл и помнил слабо, а в профессиональную деятельность я не лезу, мой быдлокод только для меня. Я конечно не оправдываюсь, но и не комплексую особо =)

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

В случае линейной алгебры лучше всё-таки брать не школьные учебники, а нормальные.

Автору темы уже никакие учебники не помогут.

:D Мы все умрём