Algorithmically finding whether a point lies within a freeform shape?
#1✎ 277MZ952Intermediate ProgrammerI can make programs, but I still have trouble here and there. Programming StrengthDrawingI like to draw!HobbiesReadingI like to read books!HobbiesDuring 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✎ 179112Me21Syntax HighlighterReceived for creating the code syntax highlighter on SBSNight PersonI like the quiet night and sleep late.Express YourselfHere'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✎ 277MZ952Intermediate ProgrammerI can make programs, but I still have trouble here and there. Programming StrengthDrawingI like to draw!HobbiesReadingI like to read books!HobbiesWow, 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✎ 179112Me21Syntax HighlighterReceived for creating the code syntax highlighter on SBSNight PersonI like the quiet night and sleep late.Express YourselfDEF 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
ENDHere's a fast polygon filling algorithm
unlike the others, you don't need to repeat the first vertex here
Posted
Edited
by 12Me21