StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
18739791
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
9
CommunityOwnedDate
CreationDate
2013-09-11T11:22:14.987
FavoriteCount
0
LastActivityDate
2016-11-13T09:03:28.753
LastEditDate
2016-11-13T09:03:28.753
LastEditorUserId
2521214
OwnerUserId
2521214
ParentId
18512815
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
text
Body
[original answer] I am not C# user, but this should speeds things up a little. <ul> <li>less heap trashing</li> <li>do not compute the same thing twice</li> <li>avoid all sub calls if you can (get functions removed)</li> </ul> code: <pre><code>public bool intersectsLine(const Line2D &comparedLine) { if ((X2==comparedLine.X1)&&(Y2==comparedLine.Y1)) return false; if ((X1==comparedLine.X2)&&(Y1==comparedLine.Y2)) return false; double dx1,dy1,dx2,dy2; dx1 = X2 - X1; dy1 = Y2 - Y1; dx2 = comparedLine.X2 - comparedLine.X1; dy2 = comparedLine.Y2 - comparedLine.Y1; double s,t,ax,ay,b; ax=X1-comparedLine.X1; ay=Y1-comparedLine.Y1; b=1.0/(-(dx2*dy1)+(dx1*dy2)); s = (-(dy1*ax)+(dx1*ay))*b; t = ( (dx2*ay)-(dy2*ax))*b; if ((s>=0)&&(s<=1)&&(t>=0)&&(t<=1)) return true; return false; // No collision } </code></pre> for the rest of your code, add time measurements to find what exactly slow things down. My guess is on List management ... unnecessary reallocations can slow things considerably. [edit1] After some research on random line data I concluded this: <ol> <li>if too many lines are across the entire area than no optimizations are valid</li> <li>if there are more small lines than there is more speedup for any optimizations</li> <li>brute force is <code>T((N*N-N)/2)</code> which is still <code>O(N*N)</code> estimate around 35 hours for 700K lines to be processed (unusable)</li> <li>optimized brute force with area subdivision is <code>T((((N/M)^2)-N)/2)</code> - optimizations <code>~O((N/M)^2)</code> where <ul> <li><code>N</code> is max of area lines number</li> <li><code>M</code> is number of area divisions per any axis idea is to check only lines crossing some region (divide dataset area to <code>M*M</code> squares/rectangles). For 700K lines is best subdivision to <code>16x16</code> areas. Measured times: 0.540s per 32K lines 1.950s per 64K lines 7.000s per 128K lines 27.514s per 256K lines</li> </ul> estimated run time is 3.7 min per 700K lines (for lines at max ~10% length of whole area). I think this is better than yours 19 minutes.</li> <li>another speed up is possible with use of multi CPU/core algorithm is fully parallel-isable and for 4 CPU/Cores <code>3.7min/4 -> 56s</code> or you can port it to GPU ...</li> </ol> My optimized brute force algorithm with area subdivision O((((N/M)^2)-N)/2) - optimizations <ol> <li>get the used area size <code>(xmin,xmax,ymin,ymax)</code> <code>O(N)</code></li> <li>select subdivision <code>M</code> the best I try for my random datasets <code>32K-256K</code> lines was <code>M=16</code></li> <li>cycle through all subdivision area (evenly divided dataset area) create list of lines crossing actual subdivision area and check intersection for all lines in that list. If do not want duplicate intersections then discard all intersection outside current area</li> </ol> my code (I am using BDS2006 C++ and my own lists so you need to port it to be compatible with your code) <pre><code>void Twin_GLView2D::main_intersect(int M=16) { int ia,ib,i,j,N; double zero=1e-6; glview2D::_lin *l; glview2D::_pnt p; struct _line { double bx0,by0,bx1,by1; // bounding rectangle double x0,y0,dx,dy; // precomputed params } *lin,*a,*b; struct _siz { double bx0,bx1,by0,by1; // zone bounding rectangle } sz,bz; List<_line*> zone; // load and precompute lines N=view.lin.num; lin=new _line[N]; if (lin==NULL) return; for (a=lin,l=view.lin.dat,ia=0;ia<N;ia++,a++,l++) { // line ... if (l->p0.p[0]<=l->p1.p[0]) { a->bx0=l->p0.p[0]; a->bx1=l->p1.p[0]; } else { a->bx0=l->p1.p[0]; a->bx1=l->p0.p[0]; } if (l->p0.p[1]<=l->p1.p[1]) { a->by0=l->p0.p[1]; a->by1=l->p1.p[1]; } else { a->by0=l->p1.p[1]; a->by1=l->p0.p[1]; } a->x0=l->p0.p[0]; a->dx=l->p1.p[0]-l->p0.p[0]; a->y0=l->p0.p[1]; a->dy=l->p1.p[1]-l->p0.p[1]; // global image size for zone subdivision if (!ia) { sz.bx0=l->p0.p[0]; sz.by0=l->p0.p[1]; sz.bx1=sz.bx0; sz.by1=sz.by0; } if (sz.bx0>l->p0.p[0]) sz.bx0=l->p0.p[0]; if (sz.bx1<l->p0.p[0]) sz.bx1=l->p0.p[0]; if (sz.by0>l->p0.p[1]) sz.by0=l->p0.p[1]; if (sz.by1<l->p0.p[1]) sz.by1=l->p0.p[1]; if (sz.bx0>l->p1.p[0]) sz.bx0=l->p1.p[0]; if (sz.bx1<l->p1.p[0]) sz.bx1=l->p1.p[0]; if (sz.by0>l->p1.p[1]) sz.by0=l->p1.p[1]; if (sz.by1<l->p1.p[1]) sz.by1=l->p1.p[1]; } // process lines by zonal subdivision zone.allocate(N); view.pnt.num=0; view.pnt.allocate(view.lin.num); sz.bx1-=sz.bx0; sz.bx1/=double(M); sz.by1-=sz.by0; sz.by1/=double(M); for (bz.by0=sz.by0,bz.by1=sz.by0+sz.by1,i=0;i<M;i++,bz.by0+=sz.by1,bz.by1+=sz.by1) for (bz.bx0=sz.bx0,bz.bx1=sz.bx0+sz.bx1,j=0;j<M;j++,bz.bx0+=sz.bx1,bz.bx1+=sz.bx1) { // create list of lines for actual zone only zone.num=0; // clear zone list for (a=lin,ia= 0;ia<N;ia++,a++) if ((a->bx0<=bz.bx1)&&(a->bx1>=bz.bx0)) if ((a->by0<=bz.by1)&&(a->by1>=bz.by0)) zone.add(a); // add line to zone list // check for intersection within zone only // O((((N/M)^2)-N)/2) - optimizations for (ia= 0,a=zone.dat[ia];ia<zone.num;ia++,a=zone.dat[ia]) for (ib=ia+1,b=zone.dat[ib];ib<zone.num;ib++,b=zone.dat[ib]) { // discart lines with non intersecting bound rectangles if (a->bx1<b->bx0) continue; if (a->bx0>b->bx1) continue; if (a->by1<b->by0) continue; if (a->by0>b->by1) continue; // 2D lines a,b intersect ? double x0,y0,x1,y1,t0,t1; // compute intersection t1=divide(a->dx*(a->y0-b->y0)+a->dy*(b->x0-a->x0),(a->dx*b->dy)-(b->dx*a->dy)); x1=b->x0+(b->dx*t1); y1=b->y0+(b->dy*t1); if (fabs(a->dx)>=fabs(a->dy)) t0=divide(b->x0-a->x0+(b->dx*t1),a->dx); else t0=divide(b->y0-a->y0+(b->dy*t1),a->dy); x0=a->x0+(a->dx*t0); y0=a->y0+(a->dy*t0); // check if intersection exists if (fabs(x1-x0)>zero) continue; if (fabs(y1-y0)>zero) continue; if ((t0<0.0)||(t0>1.0)) continue; if ((t1<0.0)||(t1>1.0)) continue; // if yes add point p.p[0]=x0; p.p[1]=y0; p.p[2]=0.0; // do not add points out of zone (allmost all duplicit points removal) if (x0<bz.bx0) continue; if (x0>bz.bx1) continue; if (y0<bz.by0) continue; if (y0>bz.by1) continue; view.pnt.add(p); } } view.redraw=true; delete lin; } </code></pre> Notes: <ol> <li><code>List<T> x;</code> is the same as <code>T x[]</code> with 'unlimited' size <ul> <li><code>x.num;</code> is actual size of <code>x[]</code> in Ts not Bytes !!! <code>index = <0,x.num-1></code></li> <li><code>x.add(q);</code> adds <code>q</code> to the list at the end</li> <li><code>x.num=0;</code> clears the list</li> <li><code>x.allocate(N);</code> allocate space for <code>N</code> items in list to avoid relocations</li> </ul></li> <li>input <code>List<></code> is <code>view.lin</code> ... contains points <code>p0,p1</code> each have <code>double p[2]</code> ... <code>x,y</code></li> <li>output <code>List<></code> is <code>view.pnt</code> ... contains <code>double p[2]</code> ... <code>x,y</code></li> </ol> [Edit2] In addition I found out that the best performance of above algorithm is when <code>M=12+(N>>15)</code> <ul> <li><code>M</code> is subdivision areas count per axis</li> <li><code>N</code> is number of lines to check</li> </ul>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POImplementing Hoey Shamos algorithm with C#
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USSpektre
UserOwnerUserId
1. USSpektre
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.