Поиск отверстий в 2d точечных множествах?

У меня есть набор из 2d points . Они представляют собой X,Y coordinates на стандартной картезированной сетке (в этом случае UTM zone ). Мне нужно найти отверстия в этой точке, установленные предпочтительно с некоторой способностью задавать чувствительность алгоритма, который находит эти отверстия. Обычно эти наборы точек очень плотные, но некоторые из них могут быть гораздо менее плотными.

То, что они есть, если это помогает, – это точки, в которых почва в поле отбиралась для различных свойств, которые люди в сельском хозяйстве, по-видимому, находят полезными. Иногда в этих точечных образцах есть гигантские скалы или болотистые места или полные на маленьких озерах и прудах.

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

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

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

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

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

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

Язык, на котором он будет реализован, будет C #, но примеры из чего-либо из пакетов Mathematica в MATLAB or ASM, C, C++, Python, Java or MathCAD и т. Д. MATLAB or ASM, C, C++, Python, Java or MathCAD бы прекрасны, пока в этом примере нет некоторых вызовов, перейдите к таким вещам, как FindTheHole и т. д. Где FindTheHole не определен или не является собственностью внедряющего программного обеспечения, например, примеры MathCAD обычно имеют много всего.

Ниже приведены два примера фактических наборов точек, один плотный и один разреженный, а также области, в которых мне нужно найти: Пример примерных точекПример плотных точек

как насчет некоторого растрового + векторного подхода:

  1. получить ограничивающий прямоугольник с облачной областью

    Сделайте это, если он еще не известен. Это должен быть простой цикл O(N) через все точки.

  2. создать map[N][N] области

    Это «bitmap» области для удобного вычисления плотности данных. Просто создайте проекцию из area(x,y) -> map[i][j] например, с помощью простого масштаба. Размер сетки N также является точностью вывода и должен быть больше среднего расстояния точки !!! поэтому каждая ячейка внутри map[][] охватывает область с по меньшей мере одной точкой (если не в области отверстия).

  3. вычислить плотность данных для каждой ячейки map[][]

    Легко, как pie, просто очистить map[][].cnt (счетчик точек) до zero и вычислить простым циклом O(N) где map[i][j].cnt++ для всех points(x,y)

  4. создать список неиспользуемой области (map[][].cnt==0) или (map[][].cnt<=treshold)

    Я делаю это по горизонтали и вертикали для простоты

  5. сегментированный вывод

    Просто групповые линии одного и того же отверстия вместе (пересекающиеся ... векторный подход), а также можно сделать в пуле # 4 путем заливки заливки (растровый подход)

  6. вывод полигонизировать

    Возьмите все граничные точки линий H, V одного и того же отверстия / группы и создайте многоугольник (сортируйте их, чтобы их соединение не пересекалось ни с чем). В этом есть много библиотек, алгоритмов и исходного кода.

Мой исходный код для этого подхода:

 void main_compute(int N) { // cell storage for density computation struct _cell { double x0,x1,y0,y1; // bounding area of points inside cell int cnt; // points inside cell _cell(){}; _cell(_cell& a){ *this=a; }; ~_cell(){}; _cell* operator = (const _cell *a) { *this=*a; return this; }; /*_cell* operator = (const _cell &a) { ...copy... return this; };*/ }; // line storage for hole area struct _line { double x0,y0,x1,y1; // line edge points int id; // id of hole for segmentation/polygonize int i0,i1,j0,j1; // index in map[][] _line(){}; _line(_line& a){ *this=a; }; ~_line(){}; _line* operator = (const _line *a) { *this=*a; return this; }; /*_line* operator = (const _line &a) { ...copy... return this; };*/ }; int i,j,k,M=N*N; // M = max N^2 but usualy is much much less so dynamic list will be better double mx,my; // scale to map _cell *m; // cell ptr glview2D::_pnt *p; // point ptr double x0,x1,y0,y1; // used area (bounding box) _cell **map=NULL; // cell grid _line *lin=NULL; // temp line list for hole segmentation int lins=0; // actual usage/size of lin[M] // scan point cloud for bounding box (if it is known then skip it) p=&view.pnt[0]; x0=p->p[0]; x1=x0; y0=p->p[1]; y1=y0; for (i=0;ip->p[0]) x0=p->p[0]; if (x1p[0]) x1=p->p[0]; if (y0>p->p[1]) y0=p->p[1]; if (y1p[1]) y1=p->p[1]; } // compute scale for coordinate to map index conversion mx=double(N)/(x1-x0); // add avoidance of division by zero if empty point cloud !!! my=double(N)/(y1-y0); // dynamic allocation of map[N][N],lin[M] lin=new _line[M]; map=new _cell*[N]; for (i=0;ip[0]-x0)*mx); if (i<0) i=0; if (i>=N) i=N-1; j=double((p->p[1]-y0)*my); if (j<0) j=0; if (j>=N) j=N-1; m=&map[i][j]; if (!m->cnt) { m->x0=p->p[0]; m->x1=p->p[0]; m->y0=p->p[1]; m->y1=p->p[1]; } if (m->cnt<0x7FFFFFFF) m->cnt++; // avoid overflow if (m->x0>p->p[0]) m->x0=p->p[0]; if (m->x1p[0]) m->x1=p->p[0]; if (m->y0>p->p[1]) m->y0=p->p[1]; if (m->y1p[1]) m->y1=p->p[1]; } // find holes (map[i][j].cnt==0) or (map[i][j].cnt<=treshold) // and create lin[] list of H,V lines covering holes for (j=0;j=N) continue; if (map[i0][j].cnt==0) continue; if (map[i1][j].cnt==0) continue; _line l; l.i0=i0; l.x0=map[i0][j].x1; l.i1=i1; l.x1=map[i1][j].x0; l.j0=j ; l.y0=0.25*(map[i0][j].y0+map[i0][j].y1+map[i1][j].y0+map[i1][j].y1); l.j1=j ; l.y1=l.y0; lin[lins]=l; lins++; } } for (i=0;i=N) continue; if (map[i][j0].cnt==0) continue; if (map[i][j1].cnt==0) continue; _line l; l.i0=i ; l.y0=map[i][j0].y1; l.i1=i ; l.y1=map[i][j1].y0; l.j0=j0; l.x0=0.25*(map[i][j0].x0+map[i][j0].x1+map[i][j1].x0+map[i][j1].x1); l.j1=j1; l.x1=l.x0; lin[lins]=l; lins++; } } // segmentate lin[] ... group lines of the same hole together by lin[].id // segmentation based on vector lines data // you can also segmentate the map[][] directly as bitmap during hole detection for (i=0;iid!=b->id) { // do 2D lines a,b intersect ? double xx0,yy0,xx1,yy1; double kx0,ky0,dx0,dy0,t0; double kx1,ky1,dx1,dy1,t1; double x0=a->x0,y0=a->y0; double x1=a->x1,y1=a->y1; double x2=b->x0,y2=b->y0; double x3=b->x1,y3=b->y1; // discart lines with non intersecting bound rectangles double a0,a1,b0,b1; if (x0b1) continue; if (y0b1) continue; // compute intersection kx0=x0; ky0=y0; dx0=x1-x0; dy0=y1-y0; kx1=x2; ky1=y2; dx1=x3-x2; dy1=y3-y2; t1=divide(dx0*(ky0-ky1)+dy0*(kx1-kx0),(dx0*dy1)-(dx1*dy0)); xx1=kx1+(dx1*t1); yy1=ky1+(dy1*t1); if (fabs(dx0)>=fabs(dy0)) t0=divide(kx1-kx0+(dx1*t1),dx0); else t0=divide(ky1-ky0+(dy1*t1),dy0); xx0=kx0+(dx0*t0); yy0=ky0+(dy0*t0); // check if intersection exists if (fabs(xx1-xx0)>1e-6) continue; if (fabs(yy1-yy0)>1e-6) continue; if ((t0<0.0)||(t0>1.0)) continue; if ((t1<0.0)||(t1>1.0)) continue; // if yes ... intersection point = xx0,yy0 e=1; break; } if (e) break; // join found ... stop searching } if (!e) break; // no join found ... stop segmentation i0=a->id; // joid ids ... rename i1 to i0 i1=b->id; for (a=lin,i=0;iid==i1) a->id=i0; } // visualize lin[] for (i=0;i 

Просто игнорируйте мой материал glview2D (это мой gfx-рендеринг для геометрии)

  • view.pnt[] - это динамический список ваших точек (сгенерированный случайным образом)
  • view.lin[] - это динамический список H, V только для визуализации
  • lin[] - ваш вывод линии

Это выводится:

Предварительный просмотр отверстий

Я слишком ленив, чтобы добавить многоугольник, теперь вы можете видеть, что сегментирование работает (раскраски). Если вам нужна помощь в polygonize, тогда комментируйте меня, но я думаю, что это не должно быть проблемой.

Оценка сложности зависит от общего охвата скважины

но для большей части кода это O(N) и для поиска / сегментации дырок ~O((M^2)+(U^2)) где:

  • N - количество точек
  • M - размер сетки карты
  • U - H, количество линий V зависит от отверстий ...
  • M << N, U << M*M

как вы можете видеть для 3783 точек сетки 30x30 на изображении выше, это заняло почти 9 9ms в моей настройке

[Edit1] играет с векторным полигонированием немного

граничные отверстия

для простых отверстий отлично, но для более сложных есть еще некоторые подтяжки

[Edit2], наконец, получил немного времени для этого, вот и вот:

Это простой class для поиска дыр / полигонов в более приятной / управляемой форме:

 //--------------------------------------------------------------------------- class holes { public: int xs,ys,n; // cell grid x,y - size and points count int **map; // points density map[xs][ys] // i=(x-x0)*g2l; x=x0+(i*l2g); // j=(y-y0)*g2l; y=y0+(j*l2g); double mg2l,ml2g; // scale to/from global/map space (x,y) <-> map[i][j] double x0,x1,y0,y1; // used area (bounding box) struct _line { int id; // id of hole for segmentation/polygonize int i0,i1,j0,j1; // index in map[][] _line(){}; _line(_line& a){ *this=a; }; ~_line(){}; _line* operator = (const _line *a) { *this=*a; return this; }; /*_line* operator = (const _line &a) { ...copy... return this; };*/ }; List<_line> lin; int lin_i0; // start index for perimeter lines (smaller indexes are the H,V lines inside hole) struct _point { int i,j; // index in map[][] int p0,p1; // previous next point int used; _point(){}; _point(_point& a){ *this=a; }; ~_point(){}; _point* operator = (const _point *a) { *this=*a; return this; }; /*_point* operator = (const _point &a) { ...copy... return this; };*/ }; List<_point> pnt; // class init and internal stuff holes() { xs=0; ys=0; n=0; map=NULL; mg2l=1.0; ml2g=1.0; x0=0.0; y0=0.0; x1=0.0; y1=0.0; lin_i0=0; }; holes(holes& a){ *this=a; }; ~holes() { _free(); }; holes* operator = (const holes *a) { *this=*a; return this; }; holes* operator = (const holes &a) { xs=0; ys=0; n=an; map=NULL; mg2l=a.mg2l; x0=a.x0; x1=a.x1; ml2g=a.ml2g; y0=a.y0; y1=a.y1; _alloc(a.xs,a.ys); for (int i=0;ix) x0=x; if (x1y) y0=y; if (y1=0)&&(i=0)&&(j ix; // hole lines start/stop indexes for speed up the polygonization _line *a,*b,l; _point *aa,*bb,p; lin.num=0; lin_i0=0;// clear lines ix.num=0; // clear indexes // find holes (map[i][j].cnt==0) or (map[i][j].cnt<=treshold) // and create lin[] list of H,V lines covering holes for (j=0;j=xs) continue; if (map[i0][j]==0) continue; if (map[i1][j]==0) continue; l.i0=i0; l.i1=i1; l.j0=j ; l.j1=j ; l.id=-1; lin.add(l); } for (i=0;i=ys) continue; if (map[i][j0]==0) continue; if (map[i][j1]==0) continue; l.i0=i ; l.i1=i ; l.j0=j0; l.j1=j1; l.id=-1; lin.add(l); } // segmentate lin[] ... group lines of the same hole together by lin[].id // segmentation based on vector lines data // you can also segmentate the map[][] directly as bitmap during hole detection for (i=0;iid!=b->id) { // if a,b not intersecting or neighbouring if (a->i0>b->i1) continue; if (b->i0>a->i1) continue; if (a->j0>b->j1) continue; if (b->j0>a->j1) continue; // if they do mark e for join groups e=1; break; } if (e) break; // join found ... stop searching } if (!e) break; // no join found ... stop segmentation i0=a->id; // joid ids ... rename i1 to i0 i1=b->id; for (a=lin.dat,i=0;iid==i1) a->id=i0; } // sort lin[] by id for (e=1;e;) for (e=0,a=&lin[0],b=&lin[1],i=1;iid>b->id) { l=*a; *a=*b; *b=l; e=1; } // re id lin[] and prepare start/stop indexes for (i0=-1,i1=-1,a=&lin[0],i=0;iid==i1) a->id=i0; else { i0++; i1=a->id; a->id=i0; ix.add(i); } ix.add(lin.num); // polygonize lin_i0=lin.num; for (j=1;ji0; pj=a->j0; map[pi][pj]=0; for (aa=&pnt[0],e=0;ei==pi)&&(aa->j==pj)) { e=-1; break; } if (e>=0) pnt.add(p); pi=a->i1; pj=a->j1; map[pi][pj]=0; for (aa=&pnt[0],e=0;ei==pi)&&(aa->j==pj)) { e=-1; break; } if (e>=0) pnt.add(p); } // mark not border points for (aa=&pnt[0],i=0;iused) // ignore marked points if ((aa->i>0)&&(aa->ij>0)&&(aa->ji-1][aa->j-1]>0) continue; if (map[aa->i-1][aa->j ]>0) continue; if (map[aa->i-1][aa->j+1]>0) continue; if (map[aa->i ][aa->j-1]>0) continue; if (map[aa->i ][aa->j+1]>0) continue; if (map[aa->i+1][aa->j-1]>0) continue; if (map[aa->i+1][aa->j ]>0) continue; if (map[aa->i+1][aa->j+1]>0) continue; aa->used=1; } // delete marked points for (aa=&pnt[0],e=0,i=0;iused) { pnt[e]=*aa; e++; } pnt.num=e; // connect neighbouring points distance=1 for (i0= 0,aa=&pnt[i0];i0used<2) for (i1=i0+1,bb=&pnt[i1];i1used<2) { i=aa->i-bb->i; if (i<0) i=-i; e =i; i=aa->j-bb->j; if (i<0) i=-i; e+=i; if (e!=1) continue; aa->used++; if (aa->p0<0) aa->p0=i1; else aa->p1=i1; bb->used++; if (bb->p0<0) bb->p0=i0; else bb->p1=i0; } // try to connect neighbouring points distance=sqrt(2) for (i0= 0,aa=&pnt[i0];i0used<2) for (i1=i0+1,bb=&pnt[i1];i1used<2) if ((aa->p0!=i1)&&(aa->p1!=i1)) if ((bb->p0!=i0)&&(bb->p1!=i0)) { if ((aa->used)&&(aa->p0==bb->p0)) continue; // avoid small closed loops i=aa->i-bb->i; if (i<0) i=-i; e =i*i; i=aa->j-bb->j; if (i<0) i=-i; e+=i*i; if (e!=2) continue; aa->used++; if (aa->p0<0) aa->p0=i1; else aa->p1=i1; bb->used++; if (bb->p0<0) bb->p0=i0; else bb->p1=i0; } // try to connect to closest point int ii,dd; for (i0= 0,aa=&pnt[i0];i0used<2) { for (ii=-1,i1=i0+1,bb=&pnt[i1];i1used<2) if ((aa->p0!=i1)&&(aa->p1!=i1)) if ((bb->p0!=i0)&&(bb->p1!=i0)) { i=aa->i-bb->i; if (i<0) i=-i; e =i*i; i=aa->j-bb->j; if (i<0) i=-i; e+=i*i; if ((ii<0)||(eused++; if (aa->p0<0) aa->p0=i1; else aa->p1=i1; bb->used++; if (bb->p0<0) bb->p0=i0; else bb->p1=i0; } // add connected points to lin[] ... this is hole perimeter !!! // lines are 2 x duplicated so some additional code for sort the order of line swill be good idea l.id=lin[ix[j-1]].id; for (i0=0,aa=&pnt[i0];i0i; l.j0=aa->j; // [edit3] this avoid duplicating lines if (aa->p0>i0) { bb=&pnt[aa->p0]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } if (aa->p1>i0) { bb=&pnt[aa->p1]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } //if (aa->p0>=0) { bb=&pnt[aa->p0]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } //if (aa->p1>=0) { bb=&pnt[aa->p1]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } } } } //--------------------------------------------------------------------------- 

Вам просто нужно заменить шаблон List на std::list или что угодно (этот шаблон я не могу предоставить). Это динамический 1D массив T ...

  • List x; совпадает с int x[];
  • x.add(); добавить пустой элемент в x
  • x.add(a); добавить элемент в x
  • x.reset() очищает массив
  • x.allocate(size) prealocate space, чтобы избежать перераспределения в прогоне, который медленный
  • x.num - количество элементов в x [] ... используемый размер в элементах

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

Теперь как его использовать:

 h.scann_beg(); for (i=0;i 

где view.pnt[] - список входных точек и внутри него: view.pnt[i].p0.p[ 2 ]= { x,y }

Вывод находится в h.lin[] и lin_i0 где:

  • h.lin[i] i= < 0,lin_i0 ) - внутренние линии H, V
  • h.lin[i] i= < lin_i0,h.lin.num ) - это периметр

Строки периметра не упорядочены и дублируются дважды, поэтому просто закажите их и удалите дубликаты (слишком ленив для этого). Внутри lin[] находятся id .. id отверстия 0,1,2,3,... которому принадлежит линия, а i,j координаты внутри карты. поэтому для правильного вывода в ваши координаты мира сделайте что-то вроде этого:

 int i,j; holes h; // holes class double *p; // input point list ptr h.scann_beg(); for (i=0;ii0,b->j0); h.l2g(a.p1.p[0],a.p1.p[1],b->i1,b->j1); if (iid) .. gray [edit3] was <= which is wrong and miss-color first perimeter line { a.col=0x00808080; } else{ // hole(b->id) perimeter lines ... each hole different collor if ((b->id>=0)&&(b->id<14)) a.col=coltab[b->id]; if (b->id==-1) a.col=0x00FFFFFF; // special debug lines if (b->id==-2) a.col=0x00AA8040; // special debug lines } view.lin.add(a); // here draw your line or add it to your polygon instead } 
  • my view.lin[] имеет членов: p0,p1, которые являются точками как view.pnt[] и col которые являются цветными

Я видел только одну проблему с этим, когда отверстия слишком маленькие (diameter < 3 cells) противном случае это нормально

[edit4] переупорядочивающие линии периметра

для этого просто вместо этого:

  /* add connected points to lin[] ... this is hole perimeter !!! // lines are 2 x duplicated so some additional code for sort the order of line swill be good idea l.id=lin[ix[j-1]].id; for (i0=0,aa=&pnt[i0];i0i; l.j0=aa->j; // [edit3] this avoid duplicating lines if (aa->p0>i0) { bb=&pnt[aa->p0]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } if (aa->p1>i0) { bb=&pnt[aa->p1]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } //if (aa->p0>=0) { bb=&pnt[aa->p0]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } //if (aa->p1>=0) { bb=&pnt[aa->p1]; l.i1=bb->i; l.j1=bb->j; lin.add(l); } } */ 

сделай это:

  // add connected points to lin[] ... this is hole perimeter !!! l.id=lin[ix[j-1]].id; // add index of points instead points int lin_i1=lin.num; for (i0=0,aa=&pnt[i0];i0p0>i0) { l.i1=aa->p0; lin.add(l); } if (aa->p1>i0) { l.i1=aa->p1; lin.add(l); } } // reorder perimeter lines for (i0=lin_i1,a=&lin[i0];i0i1==b->i0) { a++; l=*a; *a=*b; *b=l; a--; break; } if (a->i1==b->i1) { a++; l=*a; *a=*b; *b=l; i=a->i0; a->i0=a->i1; a->i1=i; a--; break; } } // convert point indexes to points for (i0=lin_i1,a=&lin[i0];i0i0]; a->i0=bb->i; a->j0=bb->j; bb=&pnt[a->i1]; a->i1=bb->i; a->j1=bb->j; } 

[Edit5] Как полигонизировать внутренние holes::holes_end works

В качестве входных данных для этого вам нужен список всех линий H, V lin[] сегментированных / сгруппированных / отсортированных по отверстию и карты map[][] плотности map[][] .

  1. петля через все отверстия

    1. петля через все линии H, V обработанного отверстия

      Создайте список всех уникальных конечных точек строки pnt[] (без дубликатов). Поэтому возьмите 2 конечных точки для каждой строки и посмотрите, есть ли каждая точка в списке. Если не добавить его, то игнорировать его.

    2. удалить все неграничные точки из списка

      Поэтому удалите все точки, которые не имеют контакта с областью без отверстий, просмотрев 4 соседей на map[][] плотности map[][]

    3. анализ подключенных компонентов по точкам

      1. set used=0; p0=-1; p1=-1; used=0; p0=-1; p1=-1; для всех точек в списке pnt[]
      2. подключить точки с distance=1

        петля через все точки pnt[] с used<2 что означает, что они еще не полностью используются и для каждого такого поиска точки pnt[] снова для другой такой точки, которая также имеет distance = 1 к ней. Это означает, что это его 4-соседи и должны быть подключены, поэтому добавьте информацию о соединении в их стенд (используйте индекс p0 или p1 который никогда не используется (-1) ), и увеличивайте использование обеих точек.

      3. попробуйте подключить точки с distance=sqrt(2)

        почти совпадает с №2, за исключением расстояния, которое теперь выбирает диагонали 8-соседних. На этот раз также избегайте замкнутых циклов, поэтому не подключайте точку, которая уже подключена к ней.

      4. попробуйте подключить самые близкие точки

        снова почти совпадает с # 2, # 3, но вместо этого выбирайте ближайшую точку, а также избегайте замкнутых контуров.

      5. многоугольник формы из pnt[]

        поэтому выберите первую точку в списке и добавьте ее в многоугольник. затем добавьте к нему подключенную точку (неважно, на каком пути вы начинаете p0 или p1 ). Затем добавьте свою связанную точку (отличную от предыдущей добавленной точки к многоугольнику, чтобы избежать контуров обратной и прямой). Добавьте столько очков, сколько у вас есть точек в pnt[] .

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

Это мое неохотное решение для энтузиастов:

1 – Сканировать всю 2D-область с минимальным предопределенным шагом (dx, dy). Для каждого шага координируйте поиск большего круга, который может поместиться без какой-либо точки внутри. Отбросьте все круги с радиусом меньше предопределенного размера.

введите описание изображения здесь

2 – Теперь найдите все группы сталкивающихся кругов, простую проверку расстояния и радиуса, сохраните и группируйте в отдельные списки. (Спросите, хотите ли вы получить более подробную информацию о том, как их группировать, очень просто)

введите описание изображения здесь

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

введите описание изображения здесь

Заметки

Советы по оптимизации: до шага 1 вы можете хранить все точки в матрице сетки, поэтому расчет расстояний упрощается и ограничивается квадратами сетки заданного радиуса окружности.

Прецизионность: вы получаете больше точности для меньших значений шага сканирования и допустимого радиуса минимального круга.

Не проверял сам, но, я уверен, это работает. Удачи!

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

Также будет более эффективно изменять отсортированный по углу график, который вы можете следовать по пути от A до B, и посмотреть, что будет дальше либо по часовой стрелке, либо против часовой стрелки (от сортировки по углу). Может быть полезен диктатор словарей, который определен как «график [A] [B] = (по часовой стрелке, против часовой стрелки)». Подходит примерный алгоритм (python) с использованием словаря словарей.

 pre_graph = gabriel_graph(point) graph = {} for a in pre_graph: graph[a] = {} angle_sorted = sort(pre_graph[a], key=calc_angle_from(a)) for i,b in enumerate(angle_sorted): clockwise = angle_sorted[(i - 1) % len(angle_sorted)] counterclockwise = angle_sorted[(i + 1) % len(angle_sorted)] graph[a][b] = (clockwise, counterclockwise) polygons = [] for A in points: for B in graph[A]: for direction in [0,1]: polygon = [A] next_point = B: while next != A: polygon.append(next) next_point = graph[A][B][direction] if polygon[0] == min(polygon): # This should avoid duplicates polygons.add(polygon) 

Также может быть полезно комбинировать с предложением Анте.

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

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

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

Я не знаю, как хорошо это работает, но, надеюсь, это даст вам какое-то направление.

Вот мысль:

  • For each point x find the distance d(x,y) (where y is the closest neighbor to x ). Define f(x)=d(x,y) as above.
  • Find the mean and variance of f(x) .
  • Find the ‘outliers’ – the points that their f values are very far from the mean, far by at least \alpha standard deviations. (\alpha is a parameter for the algorithm).
  • This will detect the ‘holes’ – all you have to do now is set the outlier of each hole.

It seems that you can address this by means of (binary) mathematical morphology on images.

Create a white image and plot all your points. Then “inflate” them into rectangles which are larger than the normal horizontal and vertical spacing. You do it by means of a so called erosion operation with a rectangular structuring element.

Doing this you will fill the plane, except at places where the points are too sparse.

The unfilled areas that you detect this way are smaller than the actual voids. You will restore to the full size by applying a dilation, using the same structuring element.

Both transforms combined are called an opening.

http://en.wikipedia.org/wiki/Mathematical_morphology

  • Найдите, находится ли точка внутри выпуклой оболочки для набора точек без вычисления самого корпуса
  • Как рассчитать угол из трех точек?
  • Алгоритм раздувания / дефляции (смещения, буферизации) полигонов
  • Как определить, находится ли точка внутри двумерного выпуклого многоугольника?
  • Определение пересечения двух сегментов линии?
  • Алгоритм поиска наименьших прямоугольников для покрытия набора прямоугольников без перекрытия
  • Как вы вычисляете среднее значение набора данных в круге?
  • Давайте будем гением компьютера.