Polygon Inside Another Polygon

Question

I took that idea and I am trying to detect if an entire polygon is inside the other polygon. Here is my code that I came up with adding an additional check for X because sometimes it will equal zero and cause a issue.

Public Shared Function ContainsOutsidePoints(ByVal ToBeChecked As Polygon, ByVal CheckAgainst As Polygon) As Boolean
    For Each pt As Point In ToBeChecked.Coordinates
        If CheckAgainst.Inside(pt) = False Then
            Return True
        End If
    Next
    Return False
End Function

 Public Function Inside(ByVal Value As Point) As Boolean
    Dim j As Integer = Lines.Count - 1
    Dim pxi As Double
    Dim pxj As Double
    Dim pyi As Double
    Dim pyj As Double
    Inside = False
    For i As Integer = 0 To Lines.Count - 1
        pxi = Lines.Item(i).EndPointA.X
        pxj = Lines.Item(j).EndPointA.X
        pyi = Lines.Item(i).EndPointA.Y
        pyj = Lines.Item(j).EndPointA.Y
        If (pyi < Value.Y AndAlso pyj >= Value.Y OrElse _
                pyj < Value.Y AndAlso pyi >= Value.Y) And _
                pxi <= Value.X OrElse pxj <= Value.X AndAlso _
                pxi <> pxj Then
                If (pxi + (Value.Y - pyi) / (pyj - pyi) * (pxj - pxi) < Value.X) Then
                    Inside = Not Inside
                End If
        End If
        j = i
     Next
     Return Inside
 End Function

When I run it it will sometimes say polygons that I can see are not inside the other when it clearly is and sometimes it will return is inside when not all points are inside the other polygon. Is this caused by adding the additional check of the X since even less statements match the if statement requirements.

@the_lotus If you don't think it will work because of pxi <> pxj then how would you deal with 75 / 0 if (pyj - pyi) * (pxj - pxi) = 0? — DotNet Programmer, Dec 22 '15 at 16:18
You could look at [this here](http://stackoverflow.com/questions/14818567/point-in-polygon-algorithm-giving-wrong-results-sometimes/18190354#18190354), it's similar to yours. — the_lotus, Dec 22 '15 at 16:19
I haven't done this in a while, the way I did it was to loop clockwise and if a point is on the left side of a line then that point wasn't in the polygon. If the two vector of the line had the same X then I would look at the Y only and use the formula only when both x and y were different. — the_lotus, Dec 22 '15 at 16:24
You shouldn't expect to post here a not-bad-but-not-straightforward-either code not working an expect someone to plainly fix it for you. The idea of SO is you coming with clearly-defined problems which might be answered more or less easily by people having the required knowledge and which might be helpful to others. Debugging a very specific (and not clear) algorithm doesn't belong to this group. On the other hand, if you are looking just for more or less abstract answers helping you to face the problem properly, it might be OK. — varocarbas, Dec 22 '15 at 16:36
I would personally do an iterative approach on the lines of what the_lotus is suggesting. I think that I would focus on setting up lines and checking intersections. For example: line of point1 to point2 doesn't intersect with any line of the container (I might be pre-analysing these lines and check only the relevant ones); then check point1 and point2 are inside the boundaries (distance/perpendicular line from point1/2 to closest boundary); line of point2 to point3 does intersect, etc. This would be my first approach which would keep improving (like to build algorithms in this multi-step way). — varocarbas, Dec 22 '15 at 16:43
My **cheap and dirty** trick: draw the polygon and **fill it** with a color (different from the "base" one). Then check the point color. EASY! **No math**!! :) — Phantômaxx, Dec 23 '15 at 09:28
@FrankN.Stein could you show an example of how you would write that code? That interests me to see how that approach would look. — DotNet Programmer, Dec 23 '15 at 15:33
https://msdn.microsoft.com/en-us/library/system.drawing.bitmap.getpixel%28v=vs.110%29.aspx?cs-save-lang=1&cs-lang=vb#code-snippet-1 — Phantômaxx, Dec 23 '15 at 15:37
@FrankN.Stein is that a new library and it doesn't really explain what you would use it for. — DotNet Programmer, Dec 23 '15 at 15:45
In the same page, you can switch the framework version you are interested in. — Phantômaxx, Dec 23 '15 at 15:47

score 3 · Accepted Answer · answered Dec 22 '15 at 16:33

The intersection of an horizontal line with the interior of a polygon is a set of 1D intervals.

If P is inside Q, all 1D intervals of P will be wholly inside a corresponding interval of Q.

It suffices to check that this property holds for all horizontals though all vertices of both polygons.

You can do that by considering every vertex in turn, finding the intersections with the horizontals and sorting them left-to-right before checking for inclusion.

You can save operations by using the sweepline paradigm, i.e. scanning the vertices top-to-bottom and maintaining a list of the edges that straddle the current horizontal. This way you know exactly which edge will intersect; the update of the straddling list from vertex to vertex is straightforward.

Polygon Inside Another Polygon

1 Answers1