 Algorithmically finding whether a point lies within a freeform shape? (Page 1) ● SmileBASIC Source Forums

• #1 ✎ 275 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies During my research, I was surprised that the answer to the title query was very simple: Draw a horizontal (or vertical) ray from a point. If the ray intersects any boundary of the organic shape an odd number of times, it lies within the shape. If not, it lies outside. To test a function using this method, I wrote some code that graphically filled a free-form shape. The algorithm went a little like this: receive an organic shape and let it be approximated as a polygon of n sides; find the boundaries of the polygon (min/max values of x/y components); loop through the range of the 2d boundary (min.y to max.y, min.x to max.x) and increment a counter if a ray extending from each instance of x and y to ∞ and y (positive horizontal ray) crosses any of the line segments of the polygon; if the value of the counter is odd numbered, then place a pixel, else nothing; reset the counter and continue the loop to its conclusion. This works just fine (disregarding a few conditionals when the ray lies on a vertex). A filled shape is drawn. The problem is that while the shape is in the process of filling, I have time to do some toilet things. "But hey, it works, yeah?" Eh. I know GPAINT is a thing. My purposes with the algorithm are meant to extend beyond graphical uses. It has uses in manipulating data as well, among other things I'm sure. My question here is basically this: how can I speed this thing up? What could I alter about my current method? What could I do differently? Are there any cheats in SB that could help me here? (ARYOP maybe? Idk, couldn't figure it out.) For every single data point in the range, the algorithm checks for an intersection with every segment of the polygon. For a polygon of 100 sides occupying a rectangular range of 100 by 100, this amounts to 1,000,000 operations. Now, I have attempted to speed things up by measuring the vertical range of each line segment in the polygon and determining whether or not the point falls within the range (performing an intersection check only if TRUE), but that seems to only increase the speed by a small factor, perhaps a fifth or something. I'm convinced the real culprit is the line intersection algorithm which is called upon routinely throughout. I don't think the line intersection algorithm I'm using can be sped up either, unless I am wrong and more wrong. Posted Edited by MZ952
• #2 ✎ 1785 12Me21 Syntax Highlighter Received for creating the code syntax highlighter on SBS Night Person I like the quiet night and sleep late. Express Yourself Here's a potentially better algorithm, as well as a faster implementation of the one you're using: http://geomalgorithms.com/a03-_inclusion.html I think the optimization is that they check for intersection between a horizontal line and a line segment, which is a LOT faster than checking whether two segments intersect. EDIT: I ported the code to SB, it's not optimal but should be pretty good ```OPTION DEFINT 'crossing number DEF CN_PNPOLY(PX,PY,VX[],VY[]) VAR CN,I FOR I=0 TO LEN(VX)-2 IF (VY[I]<=PY && VY[I+1]>PY) || (VY[I]>PY && VY[I+1]<=PY) THEN VAR VT#=(PY-VY[I])/(VY[I+1]-VY[I]) IF PX<VX[I]+VT#*(VX[I+1]-VX[I]) THEN INC CN ENDIF NEXT RETURN CN AND 1 END 'winding number DEF WN_PNPOLY(PX,PY,VX[],VY[]) VAR WN,I FOR I=0 TO LEN(VX)-2 IF VY[I]<=PY THEN IF VY[I+1]>PY && ISLEFT(VX[I],VY[I],VX[I+1],VY[I+1],PX,PY)>0 THEN INC WN ELSEIF VY[I+1]<=PY && ISLEFT(VX[I],VY[I],VX[I+1],VY[I+1],PX,PY)<0 THEN DEC WN ENDIF NEXT RETURN WN END DEF ISLEFT(X0,Y0,X1,Y1,X2,Y2) RETURN (X1-X0)*(Y2-Y0)-(X2-X0)*(Y1-Y0) END ``` Remember that the first point needs to be repeated at the end (so the array for a triangle will actually have a length of 4) The winding number test seems to be slightly faster (as expected) but I only did a few tests. But if you're trying to fill a polygon, there are much more efficient ways than checking whether every single point is inside the shape. Here's one: http://alienryderflex.com/polygon_fill/ Posted Edited by 12Me21
• #3 ✎ 275 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies Wow, this method is wicked fast. The winding number idea is efficient, and it might actually serve me outside this problem here, totally wasn't expecting that. It's not lightning fast, but neither is the 3ds, so... Now the ankle chain seems to be the repeated wn checks which, despite being as simple as they are, pile up the clock. Just a thought, but if a point is found to be in a polygon, it's likely that surrounding points may also be within. I'm thinking of a game of snake where there is a "snake" which snakes around inside the polygon, ricochetting off line segments at 90 degrees, tracing out rectangles which can be filled given the way wn works with non-simple polygons. Posted
• #4 ✎ 1785 12Me21 Syntax Highlighter Received for creating the code syntax highlighter on SBS Night Person I like the quiet night and sleep late. Express Yourself ```DEF DRAWPOLY VX[],VY[] DIM NODEX[LEN(VX)] VAR Y FOR Y=0 TO 240-1 VAR NODES=0 VAR J=LEN(VX)-1 'PREVIOUS VERTEX VAR I FOR I=0 TO LEN(VX)-1 IF VY[I]<Y && VY[J]>=Y || VY[J]<Y && VY[I]>=Y THEN NODEX[NODES]=VX[I]+(Y-VY[I])/(VY[J]-VY[I])*(VX[J]-VX[I]) INC NODES ENDIF J=I NEXT SORT 0,NODES,NODEX FOR I=0 TO NODES-1 STEP 2 GLINE NODEX[I],Y,NODEX[I+1]-1,Y NEXT NEXT END```Here's a fast polygon filling algorithm unlike the others, you don't need to repeat the first vertex here Posted Edited by 12Me21