Ray Casting Algorithm: How to determine with VBA if a point is inside a polyline in AutoCAD®

Someone recently asked about determining if a point resides within a polyline using VBA. There are a few ways to achieve this, some being more complex than others, each with their own advantages. However, there is one way that is particularly simple within the AutoCAD® environment, as we are able to use built in features such as the IntersectWith method.

The concept for finding out if a point is within a polyline is this - if we were to draw a line from the point in any direction to infinity, the number of intersections the line would have with the polyline would be an odd number. Think about it - if it was a square, it would cross the polyline once. For irregular shapes where the line crosses it many times, it firstly has to exit the shape - any re-entry to the shape must have a corresponding exit - so if the point is within the polyline, any line eminating from it to infinity must cross the boundary an odd number of times. And for the same reason, any point outside the boundary must cross the boundary an even number of times.

So, armed with this knowledge, we need a way to actually achieve this in AutoCAD®. And what better way of doing so is there than to simply draw a Ray in any direction, and find out how many intersections with the boundary there are? Well, that's exactly what this code does:

Option Explicit

Sub main()
    Dim selPolyline As AcadLWPolyline
    Dim selPoint As AcadPoint
    Dim pnt As Variant
    Randomize 'Initialise random number generator
    ThisDrawing.Utility.GetEntity selPolyline, pnt, "Pick polyline"
    ThisDrawing.Utility.GetEntity selPoint, pnt, "Pick point"
    If isPointInPolyline(selPolyline, selPoint) Then
        ThisDrawing.Utility.Prompt "The point resides within the polyline"

    Else
        ThisDrawing.Utility.Prompt "The point resides outside the polyline"
    End If
End Sub

Function isPointInPolyline(pl As AcadLWPolyline, pnt As AcadPoint) As Boolean
    Dim p1 As Variant
    Dim p2 As Variant
    Dim ray As AcadRay
    Dim arr As Variant
    Dim upperbound As Long
    Dim IntersectionCount As Long
    p1 = pnt.Coordinates
    p2 = p1
    ' edit on 03/12/2010 for increased reliability
    ' horizontal ray exchanged for a ray with a random direction
    p2(0) = p2(0) + 1 - Rnd * 2 'offset x coordinate for secondary point in Ray by random amount
    p2(1) = p2(1) + 1 - Rnd * 2 'offset y coordinate for secondary point in Ray by random amount
    ' end of edit
    Set ray = thisSpace.AddRay(p1, p2)
    arr = ray.IntersectWith(pl, acExtendNone)
    upperbound = UBound(arr)
    If upperbound = -1 Then
    ' No intersections - the point must not be inside the polyline
    ' Assumes no elevation
        isPointInPolyline = False
    Else
        IntersectionCount = (upperbound + 1) / 3
        'number of elements in array is equal to the upperbound + 1 because of element zero
        'we divide by 3 to find the number of individual intersections because each has
        '3 coordinates - X, Y and Z

        If IntersectionCount Mod 2 = 0 Then
        'There are an even number of intersections - it cannot be inside the polyline
            isPointInPolyline = False
        Else
        'There are an odd number of intersections - it must be inside the polyline
            isPointInPolyline = True
        End If

    End If
    ray.Delete
End Function

Function thisSpace() As AcadBlock
    If ThisDrawing.ActiveSpace = acModelSpace Then
        Set thisSpace = ThisDrawing.ModelSpace
    Else
        Set thisSpace = ThisDrawing.PaperSpace
    End If
End Function

Do consider subscribing to my blog - I'll always be posting code snippets like this, and always with a decent explanation. Please also feel free to leave comments.

Will

Comments

Anegl Valtierra
2010-12-02 16:36:41

Hello there...

Your example is amazing, but i dont know how to do it in .NET cause your did it with ActiveX... dont you have a example in .NET???

Thanks!!! :D

Will
2010-12-02 19:16:18

I'm afraid not at this time - I can absolutely have a bash at it for you if you want, but it would probably be a better learning experience for you if you tried to get it going yourself. I do have a tutorial which should point you in the right direction with .NET, and it should contain everything you need to port over VBA code to .NET. Have a look on this site for my Introduction to VB.NET.

If you still need help, please don't hesitate to ask. I am always willing to provide help on a 1 on 1 basis.

Stephan
2010-12-03 09:52:36

Hello Will, This is a nice little program. HOWEVER, it is true that in some cases this approach will fail on PLs with irregular shapes, i.e. if the ray crosses once and then just "touches" one point on the outside, forming something like a "tangent". Or what if the PL crosses itself and the ray crosses exactly through such a crossing point. Or if the ray crosses a section of a PL where two lines of the this same PL are drawn exactly on top of each other. In these 3 examples your program returns the wrong result and I am not sure if I found all the exeptions. Besides, it allowes to select PLs and points that are not on the same planar surface. In such a case your program says that the point is outside and it could be correctly considered to be outside of the PL, only it looks to the user as if it was inside. (I would have posted a sample drawing but did not find a way how to do it.) Kind regards, Stephan

Will
2010-12-03 10:24:35

Hi Stephan, thanks for your reply.

You are quite right - there are some exceptions this rule. The main purpose of the post was to deliver and demonstrate the initial concept of the ray casting algorithm and I didn't want to complicate the problem too much by including exceptions.

As a simple fix it might be a good idea to introduce an element of randomness to the direction of the ray - in fact, I will add this after I've finished writing this reply. This is a very simple tweak, and drastically reduces the chances of an exception when compared with a horizontal line. I think that in most cases this would be reliable enough - as long as it's not going to be used constantly, the likelyhood of an exception would be so remote you'd probably never have a problem.

ivo
2011-12-29 08:13:32

Hi,

I've tried the function and came to the conclusion that it did work for me for 70 %, I also wanted the other 30% :), what i've done is not 1 ray, but 4 ray's,
ay one with an angle of 45 degrees ray 2 135 degrees ray 3 225 degrees and ray 4 315 degrees, if al these rays have (mod 1) intersections with that polyline it must be inside. this function works for me 99.5 percent of the time. thanks.

CodeBug
2013-06-06 10:43:46

Hi WILL, It was me who asked for this! Thanks a lot for getting this working. Like ivo suggested I ended up using 4 rays, ended up using his logic for a better approach. Thanks to both you guys!