LoginLogin

Algorithmically finding whether a point lies within a freeform shape?

Root / Programming Questions / [.]

MZ952Created:
MZ952#1
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.
12Me21#2
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/
MZ952#3
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.
12Me21#4
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