Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Самопересечения, выходы вырезов за пределы родительского контура лучше прибивать еще на подходе. Они ни в какой алгоритм не укладываются.
Это преувеличение, есть хорошие алгоритмы и для таких полигонов.
A>>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники
SVZ>В 80-х были те же учебники (кстати, рекомендую).
А в моём учебнике была примерно такая картинка:
И там же объяснялось, что, в зависимости от предметной области, можно выбрать то или иное определение «внутренности контура». Ну то есть делать как удобно, и что нет единственного верного и универсального определения.
SVZ>Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.
И при этом оно легко модифицируется в функцию, считающую весь winding number, а не только остаток от его деления на 2. Тогда случай с самопересечением уже не предоставляет таких проблем — просто выбирай подходящее правило из вышеприведённой картинки и используй его.
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Если мы всё еще про Vatti, то там используется sweep line. А в ней есть сортировка. Если про что-то другое, то уточни, про что именно.
Я про то, что неважно как устроен внутри Vatti и что он там требует — это не родственный алгоритм. Непонятно зачем его приплетать к задаче определения лежит-ли точка внутри контура.
SVZ>Насколько я понимаю, сперва придется вычислить winding с каждой стороны ребра (т.е. уже получается дополнительная процедура), а затем, перебирая ребра, определять, в какую область попадаем.
Не надо ничего выдумывать — это не нужно.
Делай как в википедии написано или как уже в соседней ветке сказали: выпускай из точки луч в любом направлении и считай число его пересечений с контуром, учитывая направление контура (т.е. +1 или -1 для направлений против и по часовой стрелке, соответственно). Это число и даст ответ о принадлежности точки полигону.
SVZ>Просчитай, что вернет проверка, если точка находится за пределами контура: SVZ>Если луч запускается, как рядом предложено, из (-inf,py) в (px,py), то проверка вернет попадание внутрь контура.
s = 0 — и значит точка находится вне контура в любой интерпретации из вышеуказанных (odd, nonzero и т.д.).
Здравствуйте, 777777w, Вы писали:
7>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.
Посчитайте количество пересечений луча начинающей из данной точки в любом направлении с отрезками. В случае непрерывной замкнутой кривой чётное количество означает точка снаружи, нечётное соответственно — внутри. Проанализируйте случаи когда пересечение идет по точкам вместо отрезков ... чтоб не считать их два раза ..., Еще надо по моему решить как быть когда отрезок параллелен лучу.
Имеется 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;
}
Здравствуйте, SArd, Вы писали:
SA>Посчитайте количество пересечений луча начинающей из данной точки в любом направлении с отрезками. В случае непрерывной замкнутой кривой чётное количество означает точка снаружи, нечётное соответственно — внутри. Проанализируйте случаи когда пересечение идет по точкам вместо отрезков ... чтоб не считать их два раза ..., Еще надо по моему решить как быть когда отрезок параллелен лучу.
Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся.
Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники
Здравствуйте, alpha21264, Вы писали:
A>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся. A>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники
A>
A>+-----------+
A>| |
A>| +-----------+
A>| |*<-точка | |
A>+-|---------|-+
A> +---------+
A>
И как такое обрабатывать? Заливать всё? Заливать всё, а то что внутри два раза?
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Здравствуйте, alpha21264, Вы писали:
A>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся.
A>
A>+-----------+
A>| |
A>| +-----------+
A>| |*<-точка | |
A>+-|---------|-+
A> +---------+
A>
Самопересечения, выходы вырезов за пределы родительского контура лучше прибивать еще на подходе. Они ни в какой алгоритм не укладываются.
Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.
A>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, alpha21264, Вы писали:
A>>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся. A>>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники
A>>
TB>И как такое обрабатывать? Заливать всё? Заливать всё, а то что внутри два раза?
Ну, у меня был направленный по часовой стрелке контур.
Таким образом отрезки оказываются "открывающими" и "закрывающими" в зависимости от того, идут они вверх или вниз.
В данном случае мы имеем слева от точки два открывающих отрезка.
Задачка взята из проектирования печатных плат. Некоторые цепи на плате разводятся парами.
Цепь от своей парной цепи должна лежать в коридоре — не ближе чем, и не дальше чем.
То есть в неком коридоре. Построить коридор не проблема.
Но он, зараза, достаточно часто оказывается самопересечённым, с петельками в углах.
И тогда программа-трассировщик сходит с ума. Всё что внутри считает снаружи и наоборот.
Трассировщик — Specctra (Cadence).
Здравствуйте, watchmaker, Вы писали: SVZ>>В 80-х были те же учебники (кстати, рекомендую). W>А в моём учебнике была примерно такая картинка:
Кусь
W>И там же объяснялось, что, в зависимости от предметной области, можно выбрать то или иное определение «внутренности контура». Ну то есть делать как удобно, и что нет единственного верного и универсального определения.
Похоже на Vatti clipping. В gpc такое реализовано. Но в лучшем случае даст O(n log(n)), а в худшем — выродится в квадратичную сложность.
Подробностей, кроме работы на микроконтроллере, мы не знаем.
Простой луч с чет/нечет — линейный по сложности. Да и реализация простейшая. Для топикстартера это может иметь значение.
Но за мысль спасибо. Я для проверки попадания во вложенные полигоны использовал другие методы, благо у нас есть доп. информация (кто металл, а кто — вырез в металле).
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Похоже на Vatti clipping. В gpc такое реализовано. Но в лучшем случае даст O(n log(n)), а в худшем — выродится в квадратичную сложность.
Как-то не очень похоже Да и на википедии прямо написано как за линейное время это считается.
SVZ>Простой луч с чет/нечет — линейный по сложности. Да и реализация простейшая.
Здравствуйте, 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.
Просчитай, что вернет проверка, если точка находится за пределами контура:
Если луч запускается, как рядом предложено, из (-inf,py) в (px,py), то проверка вернет попадание внутрь контура.
Мне кажется, вместо вычисления S, можно выбрать ближайшее к точке ребро, пересекаемое лучом и смотреть у него значение winding. Правда это потребует еще одной сортировки (а додумывать проверку лениво ).
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, SArd, Вы писали:
7>>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.
SA>Посчитайте количество пересечений луча начинающей из данной точки в любом направлении с отрезками. В случае непрерывной замкнутой кривой чётное количество означает точка снаружи, нечётное соответственно — внутри. Проанализируйте случаи когда пересечение идет по точкам вместо отрезков ... чтоб не считать их два раза ..., Еще надо по моему решить как быть когда отрезок параллелен лучу.
Обычно берется горизонтальный луч. И да, отдельно горизонтальный отрезок надо обрабатывать. Я такие вроде бы просто отбрасывал, но не уверен, не помню.
Еще нюанс — когда этот луч проходит ровно через точку, которая является общей для двух отрезков. Если точка ниже по Y второго конца отрезка, то игнорируем.
Там на самом деле куча всего вылезает. Для МК, если есть возможность и задача располагает, лучше делать целочисленно.
Еще нюансы могут быть, если контур не только из отрезков, а ещё из дуг окружности
Здравствуйте, alpha21264, Вы писали: A>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся. A>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники A>
A>+-----------+
A>| |
A>| +-----------+
A>| |*<-точка | |
A>+-|---------|-+
A> +---------+
A>
Это как? На схеме вижу точку, которая внутри двух контуров. Ну, или внутри общего контура, полученного объединением двух. Я решил, что контуры удобнее сначала объединить.
Пару месяцев назад решал задачку поиска эквидистантных контуров, тут на форумах тоже вопрошал, было несколько полезных ответов — один из них — по поводу того, как такие контуры называются
SVZ>Самопересечения, выходы вырезов за пределы родительского контура лучше прибивать еще на подходе. Они ни в какой алгоритм не укладываются. SVZ>Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Но за мысль спасибо. Я для проверки попадания во вложенные полигоны использовал другие методы, благо у нас есть доп. информация (кто металл, а кто — вырез в металле).
О, а ты чем занимаешься? Я тут на досуге прожку для фрезеровки пишу, отлаживаю на своем картонном чпу. Ну, и еще удаленку не пыльную подыскиваю, где бы мозгами пораскидать можно. Нету такой?
Здравствуйте, kov_serg, Вы писали: 7>>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере.
Сейчас что-то совсем не вникается что тут делается, но
Здравствуйте, Marty, Вы писали:
SVZ>>Но за мысль спасибо. Я для проверки попадания во вложенные полигоны использовал другие методы, благо у нас есть доп. информация (кто металл, а кто — вырез в металле).
M>О, а ты чем занимаешься? Я тут на досуге прожку для фрезеровки пишу, отлаживаю на своем картонном чпу. Ну, и еще удаленку не пыльную подыскиваю, где бы мозгами пораскидать можно. Нету такой?
САПРами для проектирования печатных плат, конкурент Альфе
Пару лет назад у нас была вакансия
Носик, ротик, оборотик,
Палка, палка, огуречик —
Вот и вышел
человечек
Обкатывал разные возможные случаи для проверки своего алгоритма, после каждой модификации исходного контура вылезали косяки. Но вроде всё поборол. Но возможно не всё. Буду рад идеям, как поломать мой алгоритм
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>>Но за мысль спасибо. Я для проверки попадания во вложенные полигоны использовал другие методы, благо у нас есть доп. информация (кто металл, а кто — вырез в металле).
M>>О, а ты чем занимаешься? Я тут на досуге прожку для фрезеровки пишу, отлаживаю на своем картонном чпу. Ну, и еще удаленку не пыльную подыскиваю, где бы мозгами пораскидать можно. Нету такой?
SVZ>САПРами для проектирования печатных плат, конкурент Альфе SVZ>Пару лет назад у нас была вакансия
Ясно. Если что будет, пиши, может пригожусь
Кстати, такой же вопрос к Альфе
Ты мне как-то с углами, помню, неплохо помог:
double calcAngleDelta_StanislavVZudinV01( double s, double e, bool ccw );
double calcAngleDelta_StanislavVZudin( double s, double e, bool ccw );
void calcAngleDelta_StanislavVZudin_TestStep( double s, double e, bool ccw );
void calcAngleDelta_StanislavVZudin_TestSuite( );
// ой, это уже моё пошло :))double calcAngleDelta_Marty01( double s, double e, bool ccw );
я там переосмыслил, сделал своё получше, но для истории оставил
PS Подыскиваю подработку для поддержания штанов. Штаны ближе к весне начнут хорошо падать Пока своим хочу позаниматься. Коллеги, тоже с RSDN, предложили удаленку получше текущей рутины, я уволился, но после теста я им не подошел. Слишком закрыт, сказали. Два-три раза за неделю клевал по скайпу, с остальным сам разбирался. Оказалось, надо было почаще клевать.
PSS Ну и откровенно, я не очень старался на тесте — это предложение новой работы было просто триггером, чтобы уволится и попробовать что-то новое. А новое я хотел либо новую интересную работу, либо попилить своё. Своё таки выиграло
PSSS Почему я в этой теме ищу работу? Потому, что в "о работе" кадровики и прочие рекрутеры, а тут мой "человечек" просто показал, что мне интересно и что я умею
SVZ>>>Решение с лучом годное. Быстрое и работает с невыпуклыми полигонами.
M>>С любыми работает
SVZ>Просто для выпуклых полигонов есть еще проще решение.
Протупил/недораспарсил, у меня просто были произвольные полигоны из дуг и отрезков, я что-то предположил, что грани могут быть заданы и сплайнами или еще как-то, а вырожденный случай забыл
Здравствуйте, alpha21264, Вы писали:
A>Здравствуйте, SArd, Вы писали:
SA>>Посчитайте количество пересечений луча начинающей из данной точки в любом направлении с отрезками. В случае непрерывной замкнутой кривой чётное количество означает точка снаружи, нечётное соответственно — внутри. Проанализируйте случаи когда пересечение идет по точкам вместо отрезков ... чтоб не считать их два раза ..., Еще надо по моему решить как быть когда отрезок параллелен лучу.
A>Не получится. Точка может быть два раза внутри контура. И тогда ты ошибёшся. A>Я понимаю, что ты взял решение из учебника, но вот такие нынче учебники
A>
A>+-----------+
A>| |
A>| +-----------+
A>| |*<-точка | |
A>+-|---------|-+
A> +---------+
A>
Если условие позволяет самопересечения, что я не учёл, то можно применить алгоритмы нормализации. Детально с ними не знаком. Те которые я видел в деле могут дать больше чем один нормализованный контур.
Здравствуйте, watchmaker, Вы писали:
SVZ>>Если мы всё еще про Vatti, то там используется sweep line. А в ней есть сортировка. Если про что-то другое, то уточни, про что именно.
W>Я про то, что неважно как устроен внутри Vatti и что он там требует — это не родственный алгоритм. Непонятно зачем его приплетать к задаче определения лежит-ли точка внутри контура.
Ты привел картинку, которая "работает" внутри Vatti. Поэтому и разговор о нём.
SVZ>>Насколько я понимаю, сперва придется вычислить winding с каждой стороны ребра (т.е. уже получается дополнительная процедура), а затем, перебирая ребра, определять, в какую область попадаем. W>Не надо ничего выдумывать — это не нужно. W>Делай как в википедии написано или как уже в соседней ветке сказали: выпускай из точки луч в любом направлении и считай число его пересечений с контуром, учитывая направление контура (т.е. +1 или -1 для направлений против и по часовой стрелке, соответственно). Это число и даст ответ о принадлежности точки полигону.
SVZ>>Просчитай, что вернет проверка, если точка находится за пределами контура: SVZ>>Если луч запускается, как рядом предложено, из (-inf,py) в (px,py), то проверка вернет попадание внутрь контура. W>s = 0 — и значит точка находится вне контура в любой интерпретации из вышеуказанных (odd, nonzero и т.д.).
Всё, понял о чем ты. Надо всего лишь учитывать направление входа ребра в луч.
Сбило с толку упоминание winding'ов. Я думал, что учитывается глубина вложенность контура (0,1,2... на картинке ).
Да, такой способ выглядит устойчивее, чем чет/нечет.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Marty, Вы писали: M>Здравствуйте, kov_serg, Вы писали: 7>>>Имеется N точек, при обходе которых образуется замкнутый контур. Нужно узнать, попадает ли заданная точка внутрь этого контура или остается снаружи. Желательно без тригонометрии, арктангенсов и прочих долгих вычислений т.к. выполняться это будет на микроконтроллере. M>Сейчас что-то совсем не вникается что тут делается, но M>
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Сбило с толку упоминание winding'ов. Я думал, что учитывается глубина вложенность контура (0,1,2... на картинке ).
Э... так глубина на самом деле и учитывается.
Выдал алгоритм значение s = 0 — значит точка не принадлежит полигону. Выдал значение s = 1 — значит принадлежит. Выдал значение s = 2 — значит не принадлежит по правилу ODD, но принадлежит по правилу POSITIVE. И так далее.
Собственно, алгоритм только и делает, что рассчитывает глубину вложенности. Что тут может сбивать с толку?
Кстате через это решалась более сложная задача — пересечение(наложение фигур), там решение сводилось к разнице векторов. Ну а классическим рациональным путём такие задачи не решаются.
Здравствуйте, Indy, Вы писали:
I>Посмотрите это решение, оно отрицает классическую геометрию(угла не существует, есть изменение направления).
I>http://files.rsdn.org/125374/sg.png
1. Сколько вершин требуется для описания такого полигона?
2. Как выполняется поиск точек на поверхности, по которым определяется принадлежность точки полигону?
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Здравствуйте, Indy, Вы писали:
I>>Посмотрите это решение, оно отрицает классическую геометрию(угла не существует, есть изменение направления).
I>>http://files.rsdn.org/125374/sg.png
SVZ>1. Сколько вершин требуется для описания такого полигона? SVZ>2. Как выполняется поиск точек на поверхности, по которым определяется принадлежность точки полигону?
1. Фигура описана в векторной форме, нет понятия вершин и это понятие не используется. Так как нет понятие угла для произвольной кривой. Угол это понятие из древней геометрии, которое не реально и которому нет даже чёткого определения — по смыслу это приращение вектора при описании кривой, упрощённое до одной точки.
2. Такая поверхность описывается элементарно — путём выборки следующей точки на основе текущего вектора. Проблема может быть только стандартная — выделение шумов на изображении, объединение частей и пр; это проблемы распознавания.
На основе этой идеи очень давно был реализован алгос закраски фигур. Точнее так не корректно называть, это выделение всех целых частей(контуров) в пределах рассматриваемого региона.
Здравствуйте, Indy, Вы писали:
I>Посмотрите это решение, оно отрицает классическую геометрию(угла не существует, есть изменение направления).
I>http://files.rsdn.org/125374/sg.png
Уточните в каком именно месте оно отрицает классическую геометрию?
Да и на википедии прямо написано как за линейное время это считается.
