Попадание точки в контур - Алгоритмы

Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.

Здравствуйте, 777777w, Вы писали:

7>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.

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

Здравствуйте, 777777w, Вы писали:

7>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.

int inside(double px,double py,int n,double *x,double *y) {
    int i,j,s;
    s=0; j=n-1;
    for(i=0;i<n;j=i++) {
        if ( (py<y[i] ^ py<y[j]) || py==y[i] || py==y[j] ) {
            if ( (px<x[i] ^ px<x[j]) || px==x[i] || px==x[j] ) {
                if ( y[i]<y[j] ^ (x[i]-px)*(y[j]-py)>(y[i]-py)*(x[j]-px) ) s^=1;
            } else {
                if (px>x[i] && y[i]!=y[j]) s^=1;
            }
        }
    }
    return s;
}

Здравствуйте, kov_serg, Вы писали:

_>

_>int inside(double px,double py,int n,double *x,double *y) {
_>    int i,j,s;
_>    s=0; j=n-1;
_>    for(i=0;i<n;j=i++) {
_>        if ( (py<y[i] ^ py<y[j]) || py==y[i] || py==y[j] ) {
_>            if ( (px<x[i] ^ px<x[j]) || px==x[i] || px==x[j] ) {
_>                if ( y[i]<y[j] ^ (x[i]-px)*(y[j]-py)>(y[i]-py)*(x[j]-px) ) s^=1;
_>            } else {
_>                if (px>x[i] && y[i]!=y[j]) s^=1;
_>            }
_>        }
_>    }
_>    return s;
_>}
_>

А на словах можно объяснить, как это работает?

Здравствуйте, 777777w, Вы писали:

7>Здравствуйте, kov_serg, Вы писали:

_>>

_>>int inside(double px,double py,int n,double *x,double *y) {
_>>    int i,j,s;
_>>    s=0; j=n-1;
_>>    for(i=0;i<n;j=i++) {
_>>        if ( (py<y[i] ^ py<y[j]) || py==y[i] || py==y[j] ) {
_>>            if ( (px<x[i] ^ px<x[j]) || px==x[i] || px==x[j] ) {
_>>                if ( y[i]<y[j] ^ (x[i]-px)*(y[j]-py)>(y[i]-py)*(x[j]-px) ) s^=1;
_>>            } else {
_>>                if (px>x[i] && y[i]!=y[j]) s^=1;
_>>            }
_>>        }
_>>    }
_>>    return s;
_>>}
_>>

7>А на словах можно объяснить, как это работает?
Задаёшь массив точек

    enum { N=7 };
    double X[N]={ 10,10,20,40,50,50,32 }; 
    double Y[N]={ 40,10,20,20,12,40,15 };

Проверяешь попадает точка px,py внутрь

    double px=11, py=11;
    if (inside(px,py,N,X,Y)) { ... }

Если c=0 не попал, если с=1 попал.

Сам алгоритм работает очень просто переберает все грани и считает кол-во пересечений на отрезкке (-inf,py)..(px,py). Точнее четность этого количества.

Здравствуйте, SArd, Вы писали:

SA>Посчитайте количество пересечений луча начинающей из данной точки в любом направлении с отрезками. В случае непрерывной замкнутой кривой чётное количество означает точка снаружи, нечётное соответственно — внутри. Проанализируйте случаи когда пересечение идет по точкам вместо отрезков ... чтоб не считать их два раза ..., Еще надо по моему решить как быть когда отрезок параллелен лучу.

Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся.
Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники

+-----------+
|           |
| +-----------+
| |*<-точка | |
+-|---------|-+
  +---------+

Здравствуйте, alpha21264, Вы писали:

A>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся.
A>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники

A>

A>+-----------+
A>|           |
A>| +-----------+
A>| |*<-точка | |
A>+-|---------|-+
A>  +---------+ 
A>

И как такое обрабатывать? Заливать всё? Заливать всё, а то что внутри два раза?

Здравствуйте, alpha21264, Вы писали:

A>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся.

A>

A>+-----------+
A>|           |
A>| +-----------+
A>| |*<-точка | |
A>+-|---------|-+
A>  +---------+ 
A>

Самопересечения, выходы вырезов за пределы родительского контура лучше прибивать еще на подходе. Они ни в какой алгоритм не укладываются.
Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.

A>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники

В 80-х были те же учебники (кстати, рекомендую).

Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, alpha21264, Вы писали:

A>>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся.
A>>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники

A>>

A>>+-----------+
A>>|           |
A>>| +-----------+
A>>| |*<-точка | |
A>>+-|---------|-+
A>>  +---------+ 
A>>

TB>И как такое обрабатывать? Заливать всё? Заливать всё, а то что внутри два раза?

Ну, у меня был направленный по часовой стрелке контур.
Таким образом отрезки оказываются "открывающими" и "закрывающими" в зависимости от того, идут они вверх или вниз.
В данном случае мы имеем слева от точки два открывающих отрезка.

Задачка взята из проектирования печатных плат. Некоторые цепи на плате разводятся парами.
Цепь от своей парной цепи должна лежать в коридоре — не ближе чем, и не дальше чем.
То есть в неком коридоре. Построить коридор не проблема.
Но он, зараза, достаточно часто оказывается самопересечённым, с петельками в углах.
И тогда программа-трассировщик сходит с ума. Всё что внутри считает снаружи и наоборот.
Трассировщик — Specctra (Cadence).

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Самопересечения, выходы вырезов за пределы родительского контура лучше прибивать еще на подходе. Они ни в какой алгоритм не укладываются.

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

A>>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники

SVZ>В 80-х были те же учебники (кстати, рекомендую).

А в моём учебнике была примерно такая картинка:

И там же объяснялось, что, в зависимости от предметной области, можно выбрать то или иное определение «внутренности контура». Ну то есть делать как удобно, и что нет единственного верного и универсального определения.

SVZ>Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.
И при этом оно легко модифицируется в функцию, считающую весь winding number, а не только остаток от его деления на 2. Тогда случай с самопересечением уже не предоставляет таких проблем — просто выбирай подходящее правило из вышеприведённой картинки и используй его.

Здравствуйте, watchmaker, Вы писали:

SVZ>>В 80-х были те же учебники (кстати, рекомендую).

W>А в моём учебнике была примерно такая картинка:

	Кусь

W>И там же объяснялось, что, в зависимости от предметной области, можно выбрать то или иное определение «внутренности контура». Ну то есть делать как удобно, и что нет единственного верного и универсального определения.

Похоже на Vatti clipping. В gpc такое реализовано. Но в лучшем случае даст O(n log(n)), а в худшем — выродится в квадратичную сложность.

Подробностей, кроме работы на микроконтроллере, мы не знаем.
Простой луч с чет/нечет — линейный по сложности. Да и реализация простейшая. Для топикстартера это может иметь значение.

Но за мысль спасибо. Я для проверки попадания во вложенные полигоны использовал другие методы, благо у нас есть доп. информация (кто металл, а кто — вырез в металле).

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Похоже на Vatti clipping. В gpc такое реализовано. Но в лучшем случае даст O(n log(n)), а в худшем — выродится в квадратичную сложность.

Как-то не очень похоже

Да и на википедии прямо написано как за линейное время это считается.

SVZ>Простой луч с чет/нечет — линейный по сложности. Да и реализация простейшая.

Так и тут не сильно сложнее. Если взять за основу исходник из соседней ветки, то нужно просто заменить s ^= 1 на s += (условие из вики) ? +1 : -1.

Здравствуйте, watchmaker, Вы писали:

SVZ>>Похоже на Vatti clipping. В gpc такое реализовано. Но в лучшем случае даст O(n log(n)), а в худшем — выродится в квадратичную сложность.

W>Как-то не очень похоже

Да и на википедии прямо написано как за линейное время это считается.

Если мы всё еще про Vatti, то там используется sweep line. А в ней есть сортировка. Если про что-то другое, то уточни, про что именно.

SVZ>>Простой луч с чет/нечет — линейный по сложности. Да и реализация простейшая.

W>Так и тут не сильно сложнее. Если взять за основу исходник из соседней ветки, то нужно просто заменить s ^= 1 на s += (условие из вики) ? +1 : -1.

Насколько я понимаю, сперва придется вычислить winding с каждой стороны ребра (т.е. уже получается дополнительная процедура), а затем, перебирая ребра, определять, в какую область попадаем. Просто "s += (условие из вики) ? +1 : -1" не прокатит.
Скажем, если нет вырезов и надо игнорировать самопересечения, то нам подходит NONZERO.

Просчитай, что вернет проверка, если точка находится за пределами контура:

            +-------------+
            |             |
            |   +--------------+
          0 | 1 |    2    | 1  | * <-- точка
            |   |         |    | 
            +---|---------|----+
                |         | 
                +---------+

Если луч запускается, как рядом предложено, из (-inf,py) в (px,py), то проверка вернет попадание внутрь контура.
Мне кажется, вместо вычисления S, можно выбрать ближайшее к точке ребро, пересекаемое лучом и смотреть у него значение winding. Правда это потребует еще одной сортировки (а додумывать проверку лениво

).

Здравствуйте, SArd, Вы писали:

7>>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.

SA>Посчитайте количество пересечений луча начинающей из данной точки в любом направлении с отрезками. В случае непрерывной замкнутой кривой чётное количество означает точка снаружи, нечётное соответственно — внутри. Проанализируйте случаи когда пересечение идет по точкам вместо отрезков ... чтоб не считать их два раза ..., Еще надо по моему решить как быть когда отрезок параллелен лучу.

Обычно берется горизонтальный луч. И да, отдельно горизонтальный отрезок надо обрабатывать. Я такие вроде бы просто отбрасывал, но не уверен, не помню.

Еще нюанс — когда этот луч проходит ровно через точку, которая является общей для двух отрезков. Если точка ниже по Y второго конца отрезка, то игнорируем.

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

Еще нюансы могут быть, если контур не только из отрезков, а ещё из дуг окружности

Здравствуйте, alpha21264, Вы писали:

A>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся.
A>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники

A>

A>+-----------+
A>|           |
A>| +-----------+
A>| |*<-точка | |
A>+-|---------|-+
A>  +---------+ 
A>

Это как? На схеме вижу точку, которая внутри двух контуров. Ну, или внутри общего контура, полученного объединением двух. Я решил, что контуры удобнее сначала объединить.

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

	Иллюстрации

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Самопересечения, выходы вырезов за пределы родительского контура лучше прибивать еще на подходе. Они ни в какой алгоритм не укладываются.
SVZ>Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.

С любыми работает

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Но за мысль спасибо. Я для проверки попадания во вложенные полигоны использовал другие методы, благо у нас есть доп. информация (кто металл, а кто — вырез в металле).

О, а ты чем занимаешься? Я тут на досуге прожку для фрезеровки пишу, отлаживаю на своем картонном чпу. Ну, и еще удаленку не пыльную подыскиваю, где бы мозгами пораскидать можно. Нету такой?

Здравствуйте, kov_serg, Вы писали:

7>>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.

Сейчас что-то совсем не вникается что тут делается, но

если это

_>

_>int inside(double px,double py,int n,double *x,double *y) {
_>    int i,j,s;
_>    s=0; j=n-1;
_>    for(i=0;i<n;j=i++) {
_>        if ( (py<y[i] ^ py<y[j]) || py==y[i] || py==y[j] ) {
_>            if ( (px<x[i] ^ px<x[j]) || px==x[i] || px==x[j] ) {
_>                if ( y[i]<y[j] ^ (x[i]-px)*(y[j]-py)>(y[i]-py)*(x[j]-px) ) s^=1;
_>            } else {
_>                if (px>x[i] && y[i]!=y[j]) s^=1;
_>            }
_>        }
_>    }
_>    return s;
_>}
_>

работает, как заявлено, то мне пора в проф непригодности расписаться

Я месяца три вечерами потратил на эквидистантные контуры, кучу кода наколбасил, структуры там, классы, и всё такое, а надо было всего-то два три таких цикла родить

Здравствуйте, Marty, Вы писали:

SVZ>>Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.

M>С любыми работает

Просто для выпуклых полигонов есть еще проще решение.

Здравствуйте, Marty, Вы писали:

SVZ>>Но за мысль спасибо. Я для проверки попадания во вложенные полигоны использовал другие методы, благо у нас есть доп. информация (кто металл, а кто — вырез в металле).

M>О, а ты чем занимаешься? Я тут на досуге прожку для фрезеровки пишу, отлаживаю на своем картонном чпу. Ну, и еще удаленку не пыльную подыскиваю, где бы мозгами пораскидать можно. Нету такой?

САПРами для проектирования печатных плат, конкурент Альфе

Пару лет назад у нас была вакансия, новых пока нет.

	От:	777777w
	Дата:	15.11.16 18:46
	Оценка:

	От:	SArd
	Дата:	15.11.16 19:35
	Оценка:	+1

	От:	kov_serg
	Дата:	15.11.16 21:47
	Оценка:

	От:	777777w
	Дата:	16.11.16 06:07
	Оценка:

	От:	kov_serg
	Дата:	16.11.16 09:20
	Оценка:

	От:	Stanislav V. Zudin
	Дата:	16.11.16 11:20
	Оценка:

	От:	watchmaker
	Дата:	16.11.16 11:50
	Оценка:	10 (1) +1

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	16.11.16 16:36
Оценка: