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

Носик, ротик, оборотик,
Палка, палка, огуречик —
Вот и вышел

	человечек

Обкатывал разные возможные случаи для проверки своего алгоритма, после каждой модификации исходного контура вылезали косяки. Но вроде всё поборол. Но возможно не всё. Буду рад идеям, как поломать мой алгоритм

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

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

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

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

Автор: Stanislav V. Zudin
Дата: 23.12.14

, новых пока нет.

Ясно. Если что будет, пиши, может пригожусь
Кстати, такой же вопрос к Альфе

Ты мне как-то с углами, помню, неплохо помог:

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 Почему я в этой теме ищу работу? Потому, что в "о работе" кадровики и прочие рекрутеры, а тут мой "человечек" просто показал, что мне интересно и что я умею

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


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

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

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

Протупил/недораспарсил, у меня просто были произвольные полигоны из дуг и отрезков, я что-то предположил, что грани могут быть заданы и сплайнами или еще как-то, а вырожденный случай забыл

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

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

Я про то, что неважно как устроен внутри Vatti и что он там требует — это не родственный алгоритм. Непонятно зачем его приплетать к задаче определения лежит-ли точка внутри контура.

SVZ>Насколько я понимаю, сперва придется вычислить winding с каждой стороны ребра (т.е. уже получается дополнительная процедура), а затем, перебирая ребра, определять, в какую область попадаем.
Не надо ничего выдумывать — это не нужно.
Делай как в википедии написано или как уже в соседней ветке сказали: выпускай из точки луч в любом направлении и считай число его пересечений с контуром, учитывая направление контура (т.е. +1 или -1 для направлений против и по часовой стрелке, соответственно). Это число и даст ответ о принадлежности точки полигону.

SVZ>Просчитай, что вернет проверка, если точка находится за пределами контура:
SVZ>Если луч запускается, как рядом предложено, из (-inf,py) в (px,py), то проверка вернет попадание внутрь контура.
s = 0 — и значит точка находится вне контура в любой интерпретации из вышеуказанных (odd, nonzero и т.д.).

Здравствуйте, 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... на картинке ).
Да, такой способ выглядит устойчивее, чем чет/нечет.

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

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

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

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

	если это
	_>> _>>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
Дата: 16.11.16

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

В чем проблема?

#include <stdio.h>

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;
}

int main(int argc,char** argv) {
    int i,j;
    enum { N=8 }; 
    double X[]={ 2, 2, 14,14, 4, 4,16,16 };
    double Y[]={10, 2,  2,12,12, 6, 6,10 };
    for(j=0;j<18;j++) {
        for(i=0;i<30;i++) {
            printf("%d", inside(i,j,N,X,Y));
        }
        printf("\n");
    }
    return 0;
}

$ gcc polygon.c && ./a.out
000000000000000000000000000000
000000000000000000000000000000
001111111111111000000000000000
001111111111111000000000000000
001111111111111000000000000000
001111111111111000000000000000
001100000000000110000000000000
001100000000000110000000000000
001100000000000110000000000000
001100000000000110000000000000
001100000000000110000000000000
000011111111111000000000000000
000011111111111000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000

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

SVZ>Сбило с толку упоминание winding'ов. Я думал, что учитывается глубина вложенность контура (0,1,2... на картинке ).
Э... так глубина на самом деле и учитывается.
Выдал алгоритм значение s = 0 — значит точка не принадлежит полигону. Выдал значение s = 1 — значит принадлежит. Выдал значение s = 2 — значит не принадлежит по правилу ODD, но принадлежит по правилу POSITIVE. И так далее.
Собственно, алгоритм только и делает, что рассчитывает глубину вложенности. Что тут может сбивать с толку?

Посмотрите это решение, оно отрицает классическую геометрию(угла не существует, есть изменение направления).

http://files.rsdn.org/125374/sg.png

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

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

I>Посмотрите это решение, оно отрицает классическую геометрию(угла не существует, есть изменение направления).

I>http://files.rsdn.org/125374/sg.png

1. Сколько вершин требуется для описания такого полигона?
2. Как выполняется поиск точек на поверхности, по которым определяется принадлежность точки полигону?

Здравствуйте, 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

Уточните в каком именно месте оно отрицает классическую геометрию?