Create complex polygon - determine if coords intersect

Legacy 98055 · Dec 4, 2007

I am creating an automatic, mobile logging system utilizing a GPS. The US Census Bureau provides approximate coordinates for each US zipcode. An example of "45252", which is my home zipcode is below...

-84.6298613426565 39.2773019382716
-84.6303470000000 39.3120560000000
-84.6294240000000 39.3104500000000
-84.6333240000000 39.3090500000000
-84.6342240000000 39.3091500000000
-84.6372480000000 39.3062570000000
-84.6277480000000 39.3043570000000
-84.6211470000000 39.3024570000000
-84.6183470000000 39.3001570000000
-84.6110470000000 39.2924570000000
-84.6072470000000 39.2895570000000
-84.6056470000000 39.2865570000000
-84.6040470000000 39.2811570000000
-84.6025470000000 39.2700570000000
-84.6041470000000 39.2638570000000
-84.6038470000000 39.2622570000000
-84.6004460000000 39.2563570000000
-84.6026460000000 39.2550570000000
-84.6215470000000 39.2401570000000
-84.6260470000000 39.2376570000000
-84.6298470000000 39.2327580000000
-84.6298470000000 39.2327580000000
-84.6370470000000 39.2348570000000
-84.6438470000000 39.2396570000000
-84.6472470000000 39.2409570000000
-84.6524470000000 39.2471570000000
-84.6584380000000 39.2508330000000
-84.6617480000000 39.2566570000000
-84.6630550000000 39.2601090000000
-84.6629480000000 39.2615570000000
-84.6625740000000 39.2617050000000
-84.6625740000000 39.2617050000000
-84.6597600000000 39.2616000000000
-84.6554380000000 39.2644080000000
-84.6547220000000 39.2665350000000
-84.6584480000000 39.2715570000000
-84.6549030000000 39.2806030000000
-84.6529480000000 39.2872570000000
-84.6534480000000 39.2892570000000
-84.6602480000000 39.2885570000000
-84.6645480000000 39.2920570000000
-84.6643480000000 39.2962570000000
-84.6606510000000 39.2989360000000
-84.6571170000000 39.2998400000000
-84.6506930000000 39.2990440000000
-84.6465830000000 39.3003130000000
-84.6424770000000 39.3030640000000
-84.6377060000000 39.3098200000000
-84.6304060000000 39.3120460000000
-84.6304060000000 39.3120460000000
-84.6303470000000 39.3120560000000

These sets of Longitute and Latitude coords define a boundary for my zip code. What I need to do is create a complex polygon with the above coords and then, feeding a function a Longitute and Latitude, determine if that given global position falls within my polygon (zip code boundary).

For example:

Longitude: -84.6197
Latitude: 39.2947

Will fall within the above polygon and my function would return true.

Any help on this one??? Please!

Damon Ostrander · Dec 4, 2007

Hi Right_Click,

There is a fairly simple (conceptually) algorithm for determining whether a given point falls inside or outside of a polygon, no matter how complex the polygon (it can contain keyholes, etc.). I have never implemented it in VBA, but am sure it is not difficult. The essence of the algorithm is this:

1. polygon vertices numbered 1 to n, start by computing the angle subtended at the test point between vertices 1 and 2.

2. Do the same for each pair, 2 and 3, 3 and 4, etc., each time computing If the angle and summing with all previously calculated angles. When the angle between vertices i and i+1 is clockwise, add the angle, when counterclockwise, subtract it.

3. When you have summed over all vertices from 1 to n, also close the polygon by including the angle between n and 1.

4. The total angle will now be either 360 degrees, -360 degrees, or 0, depending whether the test point is inside or outside the polygon, and whether the vertices encircle the point in a clockwise or counterclockwise manner. If the value is 0, the test point is outside the polygon.

Of course, because of round-off errors, numerical errors, etc, the sum computed may not be exactly 360, -360, or 0, but should be very close. You should therefore test whether it is within some tolerance of zero with a test like

If ABS(SumAngle) < 1.0 Then MsgBox "Test Point is outside polygon"

If you need the algorithm to work properly if the polygon or test point is near one of the poles it would be best to convert the latitude and longitude values into cartesian coordinates on the sphere. This would be essential if the polygon were to include the pole. It is probably also essential if you need extremely high accuracy, such as when the test point is within just a few meters of a polygon side or if the sides of the polygon are very long such that it becomes important that they be represented as great circles on the sphere. But otherwise, at 40 degrees latitude (your example) and modest-sized polygons (a few miles) you should have no problem just using latitude and longitude in degrees as if they were equal-spaced coordinates in a flat plane.

It should be fairly straightforward to create a user-defined function (UDF) to do these calculations.

I hope you find this helpful.

Keep Excelling.

Damon

Legacy 98055 · Dec 5, 2007

Thanks Damon. After I run out of fingers and toes, math becomes Greek too me. Even so, I did learn a few things and your reply helped me narrow down my search for information. I found this and it seems to work thus far...

In a module:
<table width="100%" border="1" bgcolor="White" style="filter

rogid:DXImageTransform.Microsoft.Gradient(endColorstr='#C0CFE2', startColorstr='#FFFFFF', gradientType='0');"><tr><TD> Option Explicit

 Public Const PI = 3.14159265

 Public Type POINTAPI
 x As Double
 y As Double
 End Type

 Public m_NumPoints As Double
 Public m_Points() As POINTAPI

 ' Copy of points used for triangulation.
 Public m_NumCopyPoints As Double
 Public m_CopyPoints() As POINTAPI

 ' Triangles.
 Public Type Triangle
 Points(1 To 3) As POINTAPI
 End Type
 Public m_NumTriangles As Double
 Public m_Triangles() As Triangle

 ' Find the polygon's centroid.
 Public Sub FindCentroid(ByRef x As Single, ByRef y As Single)
 Dim pt As Double
 Dim second_factor As Single
 Dim polygon_area As Single

 ' Add the first point at the end of the array.
 ReDim Preserve m_Points(1 To m_NumPoints + 1)
 m_Points(m_NumPoints + 1) = m_Points(1)

 ' Find the centroid.
 x = 0
 y = 0
 For pt = 1 To m_NumPoints
 second_factor = _
 m_Points(pt).x * m_Points(pt + 1).y - _
 m_Points(pt + 1).x * m_Points(pt).y
 x = x + (m_Points(pt).x + m_Points(pt + 1).x) * _
 second_factor
 y = y + (m_Points(pt).y + m_Points(pt + 1).y) * _
 second_factor
 Next pt

 ' Divide by 6 times the polygon's area.
 polygon_area = PolygonArea
 x = x / 6 / polygon_area
 y = y / 6 / polygon_area

 ' If the values are negative, the polygon is
 ' oriented counterclockwise. Reverse the signs.
 If x < 0 Then
 x = -x
 y = -y
 End If
 End Sub

 ' Find the indexes of three points that form an ear.
 Private Sub FindEar(ByRef A As Double, ByRef B As Double, ByRef C As Double)
 For A = 1 To m_NumCopyPoints
 If FormsEar(A, A + 1, A + 2) Then
 B = A + 1
 If B > m_NumCopyPoints Then B = 1
 C = B + 1
 If C > m_NumCopyPoints Then C = 1
 Exit Sub
 End If
 Next A

 ' We should never get here because there should
 ' always be at least two ears.
 Stop
 End Sub
 ' Return True if the three points form an ear.
 Private Function FormsEar(ByVal A As Double, ByVal B As Double, ByVal C As Double) As Boolean
 Dim pt As Double
 Dim test_points(1 To 3) As POINTAPI

 ' Assume the points form an ear.
 FormsEar = True

 ' See if the angle ABC is concave.
 If GetAngle( _
 m_CopyPoints(A).x, m_CopyPoints(A).y, _
 m_CopyPoints(B).x, m_CopyPoints(B).y, _
 m_CopyPoints(C).x, m_CopyPoints(C).y) > 0 _
 Then
 ' This is a concave corner so the triangle
 ' cannot be an ear.
 FormsEar = False
 Exit Function
 End If

 ' Make the triangle A, B, C.
 test_points(1) = m_CopyPoints(A)
 test_points(2) = m_CopyPoints(B)
 test_points(3) = m_CopyPoints(C)

 ' Check the other points to see if they lie in the
 ' triangle A, B, C.
 For pt = 1 To m_NumCopyPoints
 If pt <> A And pt <> B And pt <> C Then
 With m_CopyPoints(pt)
 If PointInPolygon(.x, .y, 3, test_points) Then
 ' This point is in the triangle so
 ' this is not an ear.
 FormsEar = False
 Exit For
 End If
 End With
 End If
 Next pt
 End Function
 ' If the polygon is oriented counterclockwise,
 ' reverse the order of its points.
 Private Sub OrientPolygonClockwise(ByVal num_polygon_points As Double, polygon_points() As POINTAPI)
 Dim pt As Double
 Dim temp_point As POINTAPI

 If Not PolygonIsOrientedClockwise() Then
 For pt = 1 To num_polygon_points \ 2
 temp_point = polygon_points(pt)
 polygon_points(pt) = polygon_points(num_polygon_points - pt + 1)
 polygon_points(num_polygon_points - pt + 1) = temp_point
 Next pt
 End If
 End Sub

 ' Return True if the point is in the polygon.
 Public Function PointInPolygon(ByVal x As Double, ByVal y _
 As Double, ByVal num_polygon_points As Double, _
 polygon_points() As POINTAPI) As Boolean
 Dim pt As Double
 Dim total_angle As Single

 ' Get the angle between the point and the
 ' first and last vertices.
 total_angle = GetAngle( _
 polygon_points(num_polygon_points).x, _
 polygon_points(num_polygon_points).y, _
 x, y, _
 polygon_points(1).x, polygon_points(1).y)

 ' Add the angles from the point to each other
 ' pair of vertices.
 For pt = 1 To num_polygon_points - 1
 total_angle = total_angle + GetAngle( _
 polygon_points(pt).x, polygon_points(pt).y, _
 x, y, _
 polygon_points(pt + 1).x, polygon_points(pt + _
 1).y)
 Next pt

 ' The total angle should be 2 * PI or -2 * PI if
 ' the point is in the polygon and close to zero
 ' if the point is outside the polygon.
 PointInPolygon = (Abs(total_angle) > PI)
 End Function
 ' Return True if the polygon is oriented clockwise.
 Public Function PolygonIsOrientedClockwise() As Boolean
 PolygonIsOrientedClockwise = SignedPolygonArea() < 0
 End Function

 ' Return the polygon's area in "square" pixels.
 ' Add the areas of the trapezoids defined by the
 ' polygon's edges dropped to the X-axis. When the
 ' program considers a bottom edge of a polygon, the
 ' calculation gives a negative area so the space
 ' between the polygon and the axis is subtracted,
 ' leaving the polygon's area. This method gives odd
 ' results for non-simple polygons.
 Public Function PolygonArea() As Single
 ' Return the absolute value of the signed area.
 ' The signed area is negative if the polyogn is
 ' oriented clockwise.
 PolygonArea = Abs(SignedPolygonArea())
 End Function

 ' Return True if the polygon is convex.
 Public Function PolygonIsConvex() As Boolean
 Dim pt As Double
 Dim cross_product As Single
 Dim got_negative As Boolean
 Dim got_positive As Boolean

 ' For each set of three adjacent points A, B, C,
 ' find the dot product AB · BC. If the sign of
 ' all the dot products is the same, the angles
 ' are all positive or negative (depending on the
 ' order in which we visit them) so the polygon
 ' is convex.

 ' Assume the polygon is non-convex.
 PolygonIsConvex = False

 ' Look at the first set of points.
 cross_product = CrossProductLength( _
 m_Points(m_NumPoints - 1).x, m_Points(m_NumPoints - 1).y, _
 m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
 m_Points(1).x, m_Points(1).y)
 If cross_product < 0 Then
 got_negative = True
 ElseIf cross_product > 0 Then
 got_positive = True
 End If

 ' Look at the second set of points.
 cross_product = CrossProductLength( _
 m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
 m_Points(1).x, m_Points(1).y, _
 m_Points(2).x, m_Points(2).y)
 If cross_product < 0 Then
 got_negative = True
 ElseIf cross_product > 0 Then
 got_positive = True
 End If
 If got_negative And got_positive Then Exit Function

 ' Look at the remaining triples of points.
 For pt = 1 To m_NumPoints - 2
 cross_product = CrossProductLength( _
 m_Points(pt).x, m_Points(pt).y, _
 m_Points(pt + 1).x, m_Points(pt + 1).y, _
 m_Points(pt + 2).x, m_Points(pt + 2).y)
 If cross_product < 0 Then
 got_negative = True
 ElseIf cross_product > 0 Then
 got_positive = True
 End If
 If got_negative And got_positive Then Exit Function
 Next pt

 ' If we got this far, the polygon is convex.
 PolygonIsConvex = True
 End Function

 ' Return the angle with tangent opp/hyp. The returned
 ' value is between PI and -PI.
 Public Function ATan2(ByVal opp As Single, ByVal adj As Single) As Single
 Dim angle As Single

 ' Get the basic angle.
 If Abs(adj) < 0.0001 Then
 angle = PI / 2
 Else
 angle = Abs(Atn(opp / adj))
 End If

 ' See if we are in quadrant 2 or 3.
 If adj < 0 Then
 ' angle > PI/2 or angle < -PI/2.
 angle = PI - angle
 End If

 ' See if we are in quadrant 3 or 4.
 If opp < 0 Then
 angle = -angle
 End If

 ' Return the result.
 ATan2 = angle
 End Function
 ' Return the cross product AB x BC.
 ' The cross product is a vector perpendicular to AB
 ' and BC having length |AB| * |BC| * Sin(theta) and
 ' with direction given by the right-hand rule.
 ' For two vectors in the X-Y plane, the result is a
 ' vector with X and Y components 0 so the Z component
 ' gives the vector's length and direction.
 Public Function CrossProductLength( _
 ByVal Ax As Single, ByVal Ay As Single, _
 ByVal Bx As Single, ByVal By As Single, _
 ByVal Cx As Single, ByVal Cy As Single _
 ) As Single
 Dim BAx As Single
 Dim BAy As Single
 Dim BCx As Single
 Dim BCy As Single

 ' Get the vectors' coordinates.
 BAx = Ax - Bx
 BAy = Ay - By
 BCx = Cx - Bx
 BCy = Cy - By

 ' Calculate the Z coordinate of the cross product.
 CrossProductLength = BAx * BCy - BAy * BCx
 End Function
 ' Return the dot product AB · BC.
 ' Note that AB · BC = |AB| * |BC| * Cos(theta).
 Private Function DotProduct( _
 ByVal Ax As Single, ByVal Ay As Single, _
 ByVal Bx As Single, ByVal By As Single, _
 ByVal Cx As Single, ByVal Cy As Single _
 ) As Single
 Dim BAx As Single
 Dim BAy As Single
 Dim BCx As Single
 Dim BCy As Single

 ' Get the vectors' coordinates.
 BAx = Ax - Bx
 BAy = Ay - By
 BCx = Cx - Bx
 BCy = Cy - By

 ' Calculate the dot product.
 DotProduct = BAx * BCx + BAy * BCy
 End Function

 ' Return the angle ABC.
 ' Return a value between PI and -PI.
 ' Note that the value is the opposite of what you might
 ' expect because Y coordinates increase downward.
 Public Function GetAngle(ByVal Ax As Single, ByVal Ay As Single, ByVal Bx As Single, ByVal By As Single, ByVal Cx As Single, ByVal Cy As Single) As Single
 Dim dot_product As Single
 Dim cross_product As Single

 ' Get the dot product and cross product.
 dot_product = DotProduct(Ax, Ay, Bx, By, Cx, Cy)
 cross_product = CrossProductLength(Ax, Ay, Bx, By, Cx, Cy)

 ' Calculate the angle.
 GetAngle = ATan2(cross_product, dot_product)
 End Function

 ' Remove an ear from the polygon.
 Private Sub RemoveEar()
 Dim A As Double
 Dim B As Double
 Dim C As Double
 Dim old_point As Double
 Dim new_point As Double

 ' Find an ear.
 FindEar A, B, C

 ' Create a new triangle for the ear.
 m_NumTriangles = m_NumTriangles + 1
 With m_Triangles(m_NumTriangles)
 .Points(1) = m_CopyPoints(A)
 .Points(2) = m_CopyPoints(B)
 .Points(3) = m_CopyPoints(C)
 End With

 ' Remove the ear from the polygon.
 new_point = 0
 For old_point = 1 To m_NumCopyPoints
 If old_point <> B Then
 new_point = new_point + 1
 m_CopyPoints(new_point) = m_CopyPoints(old_point)
 End If
 Next old_point
 m_NumCopyPoints = m_NumCopyPoints - 1

 ' Repeat the first two points.
 m_CopyPoints(m_NumCopyPoints + 1) = m_CopyPoints(1)
 m_CopyPoints(m_NumCopyPoints + 2) = m_CopyPoints(2)
 End Sub
 ' Return the polygon's area in "square" pixels.
 ' Add the areas of the trapezoids defined by the
 ' polygon's edges dropped to the X-axis. When the
 ' program considers a bottom edge of a polygon, the
 ' calculation gives a negative area so the space
 ' between the polygon and the axis is subtracted,
 ' leaving the polygon's area. This method gives odd
 ' results for non-simple polygons.
 '
 ' The value will be negative if the polyogn is
 ' oriented clockwise.
 Private Function SignedPolygonArea() As Single
 Dim pt As Double
 Dim area As Single

 ' Add the first point to the end.
 ReDim Preserve m_Points(1 To m_NumPoints + 1)
 m_Points(m_NumPoints + 1) = m_Points(1)

 ' Get the areas.
 For pt = 1 To m_NumPoints
 area = area + _
 (m_Points(pt + 1).x - m_Points(pt).x) * _
 (m_Points(pt + 1).y + m_Points(pt).y) / 2
 Next pt

 ' Return the result.
 SignedPolygonArea = area
 End Function

 ' Traingulate the polygon.
 '
 ' For a nice, detailed explanation of this method,
 ' see Ian Garton's Web page:
 ' http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html
 Public Sub Triangulate()
 Dim pt As Double

 ' Copy the points into a new array.
 m_NumCopyPoints = m_NumPoints
 ReDim m_CopyPoints(1 To m_NumCopyPoints + 2)
 For pt = 1 To m_NumPoints
 m_CopyPoints(pt) = m_Points(pt)
 Next pt

 ' Orient the polygon.
 OrientPolygonClockwise m_NumCopyPoints, m_CopyPoints

 ' Repeat the first two points.
 m_CopyPoints(m_NumCopyPoints + 1) = m_Points(1)
 m_CopyPoints(m_NumCopyPoints + 2) = m_Points(2)

 ''@
 'For pt = 1 To m_NumCopyPoints
 ' With m_CopyPoints(pt)
 ' EditorForm.CurrentX = .x
 ' EditorForm.CurrentY = .y
 ' EditorForm.Print pt
 ' End With
 'Next pt
 ''@

 ' Make room for the triangles.
 m_NumTriangles = 0
 ReDim m_Triangles(1 To m_NumPoints - 2)

 ' While the copy of the polygon has more than
 ' three points, remove an ear.
 Do While m_NumCopyPoints > 3
 ' Remove an ear from the polygon.
 RemoveEar
 Loop

 ' Copy the last three points into their own triangle.
 m_NumTriangles = m_NumTriangles + 1
 With m_Triangles(m_NumTriangles)
 For pt = 1 To 3
 .Points(pt) = m_CopyPoints(pt)
 Next pt
 End With
 End Sub
</td></tr></table><button onclick='document.all("125200783837368").value=document.all("125200783837368").value.replace(/ \s\s/g,"");document.all("125200783837368").value=document.all("125200783837368").value.replace(/ /g,"");window.clipboardData.setData("Text",document.all("125200783837368").value);'>Copy to Clipboard</BUTTON><textarea style="position:absolute;visibility:hidden" name="125200783837368" wrap="virtual">
Option Explicit

Public Const PI = 3.14159265

Public Type POINTAPI
x As Double
y As Double
End Type

Public m_NumPoints As Double
Public m_Points() As POINTAPI

' Copy of points used for triangulation.
Public m_NumCopyPoints As Double
Public m_CopyPoints() As POINTAPI

' Triangles.
Public Type Triangle
Points(1 To 3) As POINTAPI
End Type
Public m_NumTriangles As Double
Public m_Triangles() As Triangle

' Find the polygon's centroid.
Public Sub FindCentroid(ByRef x As Single, ByRef y As Single)
Dim pt As Double
Dim second_factor As Single
Dim polygon_area As Single

' Add the first point at the end of the array.
ReDim Preserve m_Points(1 To m_NumPoints + 1)
m_Points(m_NumPoints + 1) = m_Points(1)

' Find the centroid.
x = 0
y = 0
For pt = 1 To m_NumPoints
second_factor = _
m_Points(pt).x * m_Points(pt + 1).y - _
m_Points(pt + 1).x * m_Points(pt).y
x = x + (m_Points(pt).x + m_Points(pt + 1).x) * _
second_factor
y = y + (m_Points(pt).y + m_Points(pt + 1).y) * _
second_factor
Next pt

' Divide by 6 times the polygon's area.
polygon_area = PolygonArea
x = x / 6 / polygon_area
y = y / 6 / polygon_area

' If the values are negative, the polygon is
' oriented counterclockwise. Reverse the signs.
If x < 0 Then
x = -x
y = -y
End If
End Sub

' Find the indexes of three points that form an ear.
Private Sub FindEar(ByRef A As Double, ByRef B As Double, ByRef C As Double)
For A = 1 To m_NumCopyPoints
If FormsEar(A, A + 1, A + 2) Then
B = A + 1
If B > m_NumCopyPoints Then B = 1
C = B + 1
If C > m_NumCopyPoints Then C = 1
Exit Sub
End If
Next A

' We should never get here because there should
' always be at least two ears.
Stop
End Sub
' Return True if the three points form an ear.
Private Function FormsEar(ByVal A As Double, ByVal B As Double, ByVal C As Double) As Boolean
Dim pt As Double
Dim test_points(1 To 3) As POINTAPI

' Assume the points form an ear.
FormsEar = True

' See if the angle ABC is concave.
If GetAngle( _
m_CopyPoints(A).x, m_CopyPoints(A).y, _
m_CopyPoints(B).x, m_CopyPoints(B).y, _
m_CopyPoints(C).x, m_CopyPoints(C).y) > 0 _
Then
' This is a concave corner so the triangle
' cannot be an ear.
FormsEar = False
Exit Function
End If

' Make the triangle A, B, C.
test_points(1) = m_CopyPoints(A)
test_points(2) = m_CopyPoints(B)
test_points(3) = m_CopyPoints(C)

' Check the other points to see if they lie in the
' triangle A, B, C.
For pt = 1 To m_NumCopyPoints
If pt <> A And pt <> B And pt <> C Then
With m_CopyPoints(pt)
If PointInPolygon(.x, .y, 3, test_points) Then
' This point is in the triangle so
' this is not an ear.
FormsEar = False
Exit For
End If
End With
End If
Next pt
End Function
' If the polygon is oriented counterclockwise,
' reverse the order of its points.
Private Sub OrientPolygonClockwise(ByVal num_polygon_points As Double, polygon_points() As POINTAPI)
Dim pt As Double
Dim temp_point As POINTAPI

If Not PolygonIsOrientedClockwise() Then
For pt = 1 To num_polygon_points \ 2
temp_point = polygon_points(pt)
polygon_points(pt) = polygon_points(num_polygon_points - pt + 1)
polygon_points(num_polygon_points - pt + 1) = temp_point
Next pt
End If
End Sub

' Return True if the point is in the polygon.
Public Function PointInPolygon(ByVal x As Double, ByVal y _
As Double, ByVal num_polygon_points As Double, _
polygon_points() As POINTAPI) As Boolean
Dim pt As Double
Dim total_angle As Single

' Get the angle between the point and the
' first and last vertices.
total_angle = GetAngle( _
polygon_points(num_polygon_points).x, _
polygon_points(num_polygon_points).y, _
x, y, _
polygon_points(1).x, polygon_points(1).y)

' Add the angles from the point to each other
' pair of vertices.
For pt = 1 To num_polygon_points - 1
total_angle = total_angle + GetAngle( _
polygon_points(pt).x, polygon_points(pt).y, _
x, y, _
polygon_points(pt + 1).x, polygon_points(pt + _
1).y)
Next pt

' The total angle should be 2 * PI or -2 * PI if
' the point is in the polygon and close to zero
' if the point is outside the polygon.
PointInPolygon = (Abs(total_angle) > PI)
End Function
' Return True if the polygon is oriented clockwise.
Public Function PolygonIsOrientedClockwise() As Boolean
PolygonIsOrientedClockwise = SignedPolygonArea() < 0
End Function

' Return the polygon's area in "square" pixels.
' Add the areas of the trapezoids defined by the
' polygon's edges dropped to the X-axis. When the
' program considers a bottom edge of a polygon, the
' calculation gives a negative area so the space
' between the polygon and the axis is subtracted,
' leaving the polygon's area. This method gives odd
' results for non-simple polygons.
Public Function PolygonArea() As Single
' Return the absolute value of the signed area.
' The signed area is negative if the polyogn is
' oriented clockwise.
PolygonArea = Abs(SignedPolygonArea())
End Function

' Return True if the polygon is convex.
Public Function PolygonIsConvex() As Boolean
Dim pt As Double
Dim cross_product As Single
Dim got_negative As Boolean
Dim got_positive As Boolean

' For each set of three adjacent points A, B, C,
' find the dot product AB · BC. If the sign of
' all the dot products is the same, the angles
' are all positive or negative (depending on the
' order in which we visit them) so the polygon
' is convex.

' Assume the polygon is non-convex.
PolygonIsConvex = False

' Look at the first set of points.
cross_product = CrossProductLength( _
m_Points(m_NumPoints - 1).x, m_Points(m_NumPoints - 1).y, _
m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
m_Points(1).x, m_Points(1).y)
If cross_product < 0 Then
got_negative = True
ElseIf cross_product > 0 Then
got_positive = True
End If

' Look at the second set of points.
cross_product = CrossProductLength( _
m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
m_Points(1).x, m_Points(1).y, _
m_Points(2).x, m_Points(2).y)
If cross_product < 0 Then
got_negative = True
ElseIf cross_product > 0 Then
got_positive = True
End If
If got_negative And got_positive Then Exit Function

' Look at the remaining triples of points.
For pt = 1 To m_NumPoints - 2
cross_product = CrossProductLength( _
m_Points(pt).x, m_Points(pt).y, _
m_Points(pt + 1).x, m_Points(pt + 1).y, _
m_Points(pt + 2).x, m_Points(pt + 2).y)
If cross_product < 0 Then
got_negative = True
ElseIf cross_product > 0 Then
got_positive = True
End If
If got_negative And got_positive Then Exit Function
Next pt

' If we got this far, the polygon is convex.
PolygonIsConvex = True
End Function

' Return the angle with tangent opp/hyp. The returned
' value is between PI and -PI.
Public Function ATan2(ByVal opp As Single, ByVal adj As Single) As Single
Dim angle As Single

' Get the basic angle.
If Abs(adj) < 0.0001 Then
angle = PI / 2
Else
angle = Abs(Atn(opp / adj))
End If

' See if we are in quadrant 2 or 3.
If adj < 0 Then
' angle > PI/2 or angle < -PI/2.
angle = PI - angle
End If

' See if we are in quadrant 3 or 4.
If opp < 0 Then
angle = -angle
End If

' Return the result.
ATan2 = angle
End Function
' Return the cross product AB x BC.
' The cross product is a vector perpendicular to AB
' and BC having length |AB| * |BC| * Sin(theta) and
' with direction given by the right-hand rule.
' For two vectors in the X-Y plane, the result is a
' vector with X and Y components 0 so the Z component
' gives the vector's length and direction.
Public Function CrossProductLength( _
ByVal Ax As Single, ByVal Ay As Single, _
ByVal Bx As Single, ByVal By As Single, _
ByVal Cx As Single, ByVal Cy As Single _
) As Single
Dim BAx As Single
Dim BAy As Single
Dim BCx As Single
Dim BCy As Single

' Get the vectors' coordinates.
BAx = Ax - Bx
BAy = Ay - By
BCx = Cx - Bx
BCy = Cy - By

' Calculate the Z coordinate of the cross product.
CrossProductLength = BAx * BCy - BAy * BCx
End Function
' Return the dot product AB · BC.
' Note that AB · BC = |AB| * |BC| * Cos(theta).
Private Function DotProduct( _
ByVal Ax As Single, ByVal Ay As Single, _
ByVal Bx As Single, ByVal By As Single, _
ByVal Cx As Single, ByVal Cy As Single _
) As Single
Dim BAx As Single
Dim BAy As Single
Dim BCx As Single
Dim BCy As Single

' Get the vectors' coordinates.
BAx = Ax - Bx
BAy = Ay - By
BCx = Cx - Bx
BCy = Cy - By

' Calculate the dot product.
DotProduct = BAx * BCx + BAy * BCy
End Function

' Return the angle ABC.
' Return a value between PI and -PI.
' Note that the value is the opposite of what you might
' expect because Y coordinates increase downward.
Public Function GetAngle(ByVal Ax As Single, ByVal Ay As Single, ByVal Bx As Single, ByVal By As Single, ByVal Cx As Single, ByVal Cy As Single) As Single
Dim dot_product As Single
Dim cross_product As Single

' Get the dot product and cross product.
dot_product = DotProduct(Ax, Ay, Bx, By, Cx, Cy)
cross_product = CrossProductLength(Ax, Ay, Bx, By, Cx, Cy)

' Calculate the angle.
GetAngle = ATan2(cross_product, dot_product)
End Function

' Remove an ear from the polygon.
Private Sub RemoveEar()
Dim A As Double
Dim B As Double
Dim C As Double
Dim old_point As Double
Dim new_point As Double

' Find an ear.
FindEar A, B, C

' Create a new triangle for the ear.
m_NumTriangles = m_NumTriangles + 1
With m_Triangles(m_NumTriangles)
.Points(1) = m_CopyPoints(A)
.Points(2) = m_CopyPoints(B)
.Points(3) = m_CopyPoints(C)
End With

' Remove the ear from the polygon.
new_point = 0
For old_point = 1 To m_NumCopyPoints
If old_point <> B Then
new_point = new_point + 1
m_CopyPoints(new_point) = m_CopyPoints(old_point)
End If
Next old_point
m_NumCopyPoints = m_NumCopyPoints - 1

' Repeat the first two points.
m_CopyPoints(m_NumCopyPoints + 1) = m_CopyPoints(1)
m_CopyPoints(m_NumCopyPoints + 2) = m_CopyPoints(2)
End Sub
' Return the polygon's area in "square" pixels.
' Add the areas of the trapezoids defined by the
' polygon's edges dropped to the X-axis. When the
' program considers a bottom edge of a polygon, the
' calculation gives a negative area so the space
' between the polygon and the axis is subtracted,
' leaving the polygon's area. This method gives odd
' results for non-simple polygons.
'
' The value will be negative if the polyogn is
' oriented clockwise.
Private Function SignedPolygonArea() As Single
Dim pt As Double
Dim area As Single

' Add the first point to the end.
ReDim Preserve m_Points(1 To m_NumPoints + 1)
m_Points(m_NumPoints + 1) = m_Points(1)

' Get the areas.
For pt = 1 To m_NumPoints
area = area + _
(m_Points(pt + 1).x - m_Points(pt).x) * _
(m_Points(pt + 1).y + m_Points(pt).y) / 2
Next pt

' Return the result.
SignedPolygonArea = area
End Function

' Traingulate the polygon.
'
' For a nice, detailed explanation of this method,
' see Ian Garton's Web page:
' http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html
Public Sub Triangulate()
Dim pt As Double

' Copy the points into a new array.
m_NumCopyPoints = m_NumPoints
ReDim m_CopyPoints(1 To m_NumCopyPoints + 2)
For pt = 1 To m_NumPoints
m_CopyPoints(pt) = m_Points(pt)
Next pt

' Orient the polygon.
OrientPolygonClockwise m_NumCopyPoints, m_CopyPoints

' Repeat the first two points.
m_CopyPoints(m_NumCopyPoints + 1) = m_Points(1)
m_CopyPoints(m_NumCopyPoints + 2) = m_Points(2)

''@
'For pt = 1 To m_NumCopyPoints
' With m_CopyPoints(pt)
' EditorForm.CurrentX = .x
' EditorForm.CurrentY = .y
' EditorForm.Print pt
' End With
'Next pt
''@

' Make room for the triangles.
m_NumTriangles = 0
ReDim m_Triangles(1 To m_NumPoints - 2)

' While the copy of the polygon has more than
' three points, remove an ear.
Do While m_NumCopyPoints > 3
' Remove an ear from the polygon.
RemoveEar
Loop

' Copy the last three points into their own triangle.
m_NumTriangles = m_NumTriangles + 1
With m_Triangles(m_NumTriangles)
For pt = 1 To 3
.Points(pt) = m_CopyPoints(pt)
Next pt
End With
End Sub</textarea>

Usage:
<table width="100%" border="1" bgcolor="White" style="filter

rogid:DXImageTransform.Microsoft.Gradient(endColorstr='#C0CFE2', startColorstr='#FFFFFF', gradientType='0');"><tr><TD> Sub Example()
 Dim r As Range, PolyPoints() As POINTAPI, x As Long, y As Long, hRgn As Long

 On Error Resume Next
 ReDim PolyPoints(1 To Range("A1:B51").Rows.Count)
 For Each r In Range("A1:B51").Rows
 x = x + 1
 PolyPoints(x).x = r.Cells(1).Value
 PolyPoints(x).y = r.Cells(2).Value
 Next

 MsgBox PointInPolygon(-84.6197, 39.2947, UBound(PolyPoints), PolyPoints)
 End Sub
</td></tr></table><button onclick='document.all("12520078397347").value=document.all("12520078397347").value.replace(/ \s\s/g,"");document.all("12520078397347").value=document.all("12520078397347").value.replace(/ /g,"");window.clipboardData.setData("Text",document.all("12520078397347").value);'>Copy to Clipboard</BUTTON><textarea style="position:absolute;visibility:hidden" name="12520078397347" wrap="virtual">
Sub Example()
Dim r As Range, PolyPoints() As POINTAPI, x As Long, y As Long, hRgn As Long

On Error Resume Next
ReDim PolyPoints(1 To Range("A1:B51").Rows.Count)
For Each r In Range("A1:B51").Rows
x = x + 1
PolyPoints(x).x = r.Cells(1).Value
PolyPoints(x).y = r.Cells(2).Value
Next

MsgBox PointInPolygon(-84.6197, 39.2947, UBound(PolyPoints), PolyPoints)
End Sub</textarea>

I imagine that this could be whittled down by using some native function but it performs well enough as a UDF.

Please see my next post on this topic...

Legacy 98055 · Dec 5, 2007

Credit to the above from this site:
http://www.vb-helper.com/howto_point_in_polygon.html

This example if for the above post.

UDF Pt In Polygon.zip

This example is for this post.

PtInRegionAPI.zip

I tried another method using several API functions but could not get it to work. Please examine my logic and tell me if I am missing something. Note that the API functions take longs as opposed to doubles. This being the case, I multiplied all of my doubles by 10,000,000. It did not work. Why not? A region was created but the function returned false or zero everytime...

My assumption is that I am losing too much accuracy with a narrowing conversion. The best I can do with this double to long is:
-84.6298613426565 to -846298613

<table width="100%" border="1" bgcolor="White" style="filter

rogid:DXImageTransform.Microsoft.Gradient(endColorstr='#C0CFE2', startColorstr='#FFFFFF', gradientType='0');"><tr><TD> Option Explicit

 Private Type LongPoints
 x As Long
 y As Long
 End Type

 Private Declare Function PtInRegion Lib "gdi32" (ByVal hRgn As Long, ByVal x As Long, ByVal y As Long) As Long
 Private Declare Function CreatePolygonRgn Lib "gdi32" (lpPoint As Any, ByVal nCount As Long, ByVal nPolyFillMode As Long) As Long
 Private Declare Function DeleteObject Lib "gdi32" (ByVal hObject As Long) As Long

 Sub Example()
 Dim r As Range, PolyPoints() As LongPoints, x As Long, y As Long, hRgn As Long

 On Error Resume Next
 ReDim PolyPoints(1 To Range("A1:B51").Rows.Count)
 For Each r In Range("A1:B51").Rows
 x = x + 1
 PolyPoints(x).x = CLng(r.Cells(1).Value * 10000000)
 PolyPoints(x).y = CLng(r.Cells(2).Value * 10000000)
 Next

 hRgn = CreatePolygonRgn(PolyPoints(1), UBound(PolyPoints), 1)
 If CBool(PtInRegion(hRgn, CLng(-84.6197 * 10000000), CLng(39.2947 * 10000000)) <> 0) Then
 MsgBox "Pt in"
 Else
 MsgBox "Pt not in"
 End If

 DeleteObject hRgn
 End Sub
</td></tr></table><button onclick='document.all("125200785216901").value=document.all("125200785216901").value.replace(/ \s\s/g,"");document.all("125200785216901").value=document.all("125200785216901").value.replace(/ /g,"");window.clipboardData.setData("Text",document.all("125200785216901").value);'>Copy to Clipboard</BUTTON><textarea style="position:absolute;visibility:hidden" name="125200785216901" wrap="virtual">
Option Explicit

Private Type LongPoints
x As Long
y As Long
End Type

Private Declare Function PtInRegion Lib "gdi32" (ByVal hRgn As Long, ByVal x As Long, ByVal y As Long) As Long
Private Declare Function CreatePolygonRgn Lib "gdi32" (lpPoint As Any, ByVal nCount As Long, ByVal nPolyFillMode As Long) As Long
Private Declare Function DeleteObject Lib "gdi32" (ByVal hObject As Long) As Long

Sub Example()
Dim r As Range, PolyPoints() As LongPoints, x As Long, y As Long, hRgn As Long

On Error Resume Next
ReDim PolyPoints(1 To Range("A1:B51").Rows.Count)
For Each r In Range("A1:B51").Rows
x = x + 1
PolyPoints(x).x = CLng(r.Cells(1).Value * 10000000)
PolyPoints(x).y = CLng(r.Cells(2).Value * 10000000)
Next

hRgn = CreatePolygonRgn(PolyPoints(1), UBound(PolyPoints), 1)
If CBool(PtInRegion(hRgn, CLng(-84.6197 * 10000000), CLng(39.2947 * 10000000)) <> 0) Then
MsgBox "Pt in"
Else
MsgBox "Pt not in"
End If

DeleteObject hRgn
End Sub</textarea>

Thanks for your reply. I appreciate it.

Damon Ostrander · Dec 5, 2007

Hi again right_click,

Yes, I would have done the Double-to-Long thing as the quickest workaround, and don't see any reason why it shouldn't work. It looks to me that the algorithm you found was designed to work with pixel coordinates, but that shouldn't matter (as you also surmised).

It also appears that the algorithm used is the one I outlined, although I saw something to indicate that there is also code there to calculate the polygon area--which you don't need and is a bit more complicated a problem, even though the algorithm is almost the same. I didn' mention using the cross product to define the normal to the plane and to determine whether two adjacent vertices represent a clockwise versus counterclockwise rotation, but this is the method I have used in the past.

In looking at the implementation of the algorithm you posted, it appears to be unnecessarily complicated. The programming appears to fail to recognize that keyholes and ears are automatically handled by following the simple rules of the general method, and so treats these as special cases. Also, if you just need to know whether the test point is interior to the polygon, it doesn't matter whether the vertices are given in CW or CCW order, which that algorithm wastes effort testing for. I really think it should take less than half that amount of code to implement the algorithm to do what you want.

I'm sorry that I don't have time to debug the algorithm with your test case. Hopefully someone with more time can jump in here. My approach would be to use some of the helper functions provided (ATAN2, cross and dot products, etc.), and implement it myself.

I hope this helps.

Damon

pgc01 · Dec 6, 2007

Hi Tom, Damon

I implemented Damon's algorithm directly in vba, just calculate the angles, take the difference between consecutive points and add.
I tried with several points and it worked OK.

Code:

Option Explicit
Const dPi = 3.14159265358979

Function PointInside(rPoint As Range, rTable As Range) As Boolean
Dim vAngles, iPoints As Integer, i As Integer
Dim dAngle As Double, dTotal As Double

'Calculates the angles 0 - 2*Pi
iPoints = rTable.Rows.Count
ReDim vAngles(1 To iPoints)
For i = 1 To iPoints
    If (rTable(i, 1) = rPoint(1)) Then
        dAngle = IIf(rTable(i, 2) >= 0, 1, -1) * dPi
    Else
        dAngle = Atn((rTable(i, 2) - rPoint(2)) / (rTable(i, 1) - rPoint(1))) + IIf(rTable(i, 1) - rPoint(1) < 0, dPi, 0)
        dAngle = dAngle + IIf(dAngle < 0, 2 * dPi, 0)
    End If
    vAngles(i) = dAngle
Next i

' Adds the differences
For i = 1 To iPoints - 1
    dAngle = vAngles(i + 1) - vAngles(i) + IIf(vAngles(i + 1) < vAngles(i), 2 * dPi, 0)
    dTotal = dTotal + dAngle - IIf(dAngle > dPi, 2 * dPi, 0)
Next i
PointInside = Abs(dTotal) > dPi
End Function

I tested it with these layout. The table is the one you posted, in A2:B51 (I only show some rows but I use it all). I display some test points in E:F.

It's easy to check it by drawing a scatter chart with the base table as the first series and the test points as the second. I labelled the points to be easier to check the result.

If you want to test it I'd like to know the results and possible points that don't work.

<table><tr><td><table border="1" cellpadding="1" style="background:#FFF; border-collapse:collapse;border-width:2px;border-color:#CCCCCC;font-family:Arial,Arial; font-size:10pt" ><tr><th style="border-width:1px;border-color:#888888;background:#9CF " > </th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" >A</th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" >B</th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" width=30 >C</th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" width=30 >D</th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" >E</th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" >F</th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" width=30 >G</th><th style="border-width:1px;border-color:#888888;background:#9CF; text-align:center" width=30 >H</th></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >1</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >2</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6303</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3121</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >3</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6294</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3105</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">A</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6197</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2947</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >4</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6333</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3091</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">B</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6197</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3124</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >5</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6342</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3092</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">C</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6300</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2300</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >6</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6372</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3063</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">D</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6300</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2400</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >7</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6277</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3044</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">E</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6350</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3000</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >8</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6211</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3025</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">F</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6350</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3060</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >9</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6183</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3002</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">G</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6350</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3100</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >10</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6110</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2925</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">H</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6350</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3150</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >11</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6072</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2896</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">I</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6600</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2400</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >12</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6056</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2866</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">J</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6600</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2600</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >13</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6040</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2812</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">K</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6600</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2700</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >14</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6025</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2701</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">L</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6600</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2900</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >15</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6041</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2639</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">M</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6600</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.3000</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >16</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6038</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2623</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">N</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6030</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2500</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >17</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6004</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2564</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">O</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6030</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2600</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >18</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6026</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2551</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">P</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6030</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2650</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">OUT</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >19</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6215</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2402</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">Q</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6030</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2700</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >20</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6260</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2377</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:left;border-width: 1px;border-color:#888888; ">R</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6617</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2567</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; ">IN</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >21</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6298</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2328</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center;border-width: 1px;border-color:#888888; "> </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; text-align:center; " >22</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">-84.6298</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; ">39.2328</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:right;border-width: 1px;border-color:#888888; "> </td></tr><tr><td colspan=9 style="background:#9CF; padding-left:1em" > [Point Inside.xls]Sheet3</td></tr></table>

</td>
<td style="padding-left:5em;" >
<table border="1" cellpadding="1" style="background:#FFF; border-collapse:collapse;border-width:2px;border-color:#CCCCCC;font-family:Arial,Arial; font-size:10pt" ><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; " >Addr</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; " >Formula</td></tr><tr><td colspan=2 style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;background:#9CF; " >[Point Inside.xls]Sheet3</td></tr><tr><td rowspan=2 style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;text-align:center; " >G3</td><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em; " > =IF(pointinside(E3:F3,$A$2:$B$51),"IN","OUT") </td></tr><tr><td style="border-width:1px;border-color:#000000; padding-left:0.5em; padding-top:0.4em; padding-right:0.5em; padding-bottom:0.25em;; " > Copy down</td></tr></table>
</td></tr></table>

Damon Ostrander · Dec 6, 2007

Great job PGC! And thanks for jumping in.

Looks like great coding. One caution however: I'm not sure doing it with Atn() will properly handle a case where the angle between two vertices is larger than 90 degrees. I haven't had time to check it, and perhaps you cleverly handle this situation in the code in a way that isn't obvious to me.

Damon

pgc01 · Dec 6, 2007

I'm not sure doing it with Atn() will properly handle a case where the angle between two vertices is larger than 90 degrees.

Hi Damon

I agree that we have to be careful with the angles. In fact for each value of a tangent you have an infinity of solutions and for each contiguous range of 360 degrees you have 2. I've chosen the range [0,2Pi] as the range of reference for all angles.

The way I've dealt with it was in 4 steps:

Given the point (x0, y0) and the table of consecutive vertices in the polygon, for each vertice:

1 - apply a translaction with the vector (-x0, -y0) to make the point the center of the coordinate system
2 - calculate the arc-tangent of the angle using the vba atn(). This gives one possible solution between -Pi/2 and Pi/2
3 - the smallest solution bigger than atn() is atn() + Pi. To choose the correct one between the two I use a simple criterion:
. if the x-coordinate of the point is less than the x-coordinate of the vertice of the polygon it means the vertice of the polygon is to the right of the point and I take atn()
. if the x-coordinate of the point is greater than the x-coordinate of the vertice of the polygon it means the vertice of the polygon is to the left of the point and I take atn() + Pi

This gives me the measure of the angle in the interval [-Pi/2, 3Pi/2].

4 - I then normalise it to [0,2Pi] with the statement "dAngle = dAngle + IIf(dAngle < 0, 2 * dPi, 0)".
As a result I have the angle between the point and the vertice of the polygon in the interval [0,2Pi].

Pedro

Legacy 98055 · Dec 6, 2007

I did expect some input but this is fantastic help gentlemen. I wish I was more math literate but have only learned what I needed on a need to know basis which is not very much with the kind of coding I have played around with for the past several years. In order to thoroughly test your algorithm, I am going to need to get to the next step in my project which may be several days or so which leads me to another somewhat related question.

The boundary files available for free from the Census Bureau are broken down into several categories. I chose "State", "3 code ZIP", and "5 code ZIP". Looping through every five digit zip code in the US for each GPS location check would be too much So I decided to first check for an intersection by state, then the first three digits of the zip, and then the five digit zips.

Damon is from the US so he would understand our ZIP system. Pedro, your location is not know too me and in case you do not know, the first three digits represent a region such as a large metropolitan region. Within this region, the last two digits of the zip code are subdivisions. For example, my home "Main" post office code is 452. This represents the greater Cincinnati, OH area within Ohio. I actually live in 45252.

So my code would check my coordinates agains the "State" polygons and resolve to "Ohio". Then loop through and resolve the region of the three digit zips in Ohio. Then loop through the individual codes within the region. I would actually like to break the entire lower 48 US states into at least four goups of polygon regions. This is fine tuning and I'll get into this after I get it working.

My question is... "Is the above logic sound or should I procede diferently?"

After I determine how to actually structure the above, I can test every zipcode in the US against your function...

Thanks again...
Thanks...

pgc01 · Dec 7, 2007

Hi Tom

2 things first:

- I don't know if you noticed but I didn't use the first row in the table you posted. It's not part of the polygon, it's a point inside the polygon. So, in your other tables if they also have a first point like this one be sure to exclude them from the tables.

- I'd like to know if you tested the solution I posted and if it went well.

Now a comment to your last post.

I think the method you propose would work, it would be exact but very computation intensive.

I would do it in another way. I would do it in 2 steps

Step 1

A rough estimation of the location, using, instead of the polygons, circumscripted rectangles.

For example I looked up the long lat of (approximate values)

Connecticut - Longitude 71 W to 74 W - Latitude 40 N to 42 N
Illinois - Longitude 87 W to 92 W - Latitude 36 N to 43 N
Ohio - Longitude 80 W to 85 W - Latitude 38 N to 42 N

Your point is Longitude: -84.6197 Latitude: 39.2947

You don't need any polygons to rule out Connecticut and Illinois. The Latitude range rules out Connecticut and the Longitude range rules out Illinois. Ohio would be a candidate.

Since this method is very simple and quick to execute I wouldn't even do the Zoom In.

I would build a single table with all the zip codes with (at least) 5 columns.
Zip code, Minimum Longitude, Maximum Longitude, Minimum Latitude, Maximum Latitude.

In Excel then use the point coordinates to build 4 autofilter custom criteria: for the second column "Less than or equal to -84.6197" and the equivalent for the other numerical columns.

If it's a big table you could also have it in Access and do a query.

This first step will execute very quickly and would narrow down the zip codes to very few. I believe that in many cases it will give you directly just 1 zip code. Anyway I don't think you'll get more than 3 or 4 zip codes.

Step 2

Now that there are only a few zip codes to look into, use their polygons and execute the code to determine exactly the zip code you're after.

Overall, I think this allows you to locate the zip code very quickly. Since the polygon tables are available the only thing that would involve some work would be building the big table with all the zip codes and the maximums and minimums.

This is of course just a suggestion. There may be other better or easier solutions. Please comment.

Create complex polygon - determine if coords intersect

Legacy 98055

Guest

Excel Facts

Damon Ostrander

MrExcel MVP

Legacy 98055

Guest

Legacy 98055

Guest

Damon Ostrander

MrExcel MVP

pgc01

MrExcel MVP

Damon Ostrander

MrExcel MVP

pgc01

MrExcel MVP

Legacy 98055

Guest

pgc01

MrExcel MVP

Similar threads

Forum statistics

Share this page

Create complex polygon - determine if coords intersect

Legacy 98055

Guest

Excel Facts

Damon Ostrander

MrExcel MVP

Legacy 98055

Guest

Legacy 98055

Guest

Damon Ostrander

MrExcel MVP

pgc01

MrExcel MVP

Damon Ostrander

MrExcel MVP

pgc01

MrExcel MVP

Legacy 98055

Guest

pgc01

MrExcel MVP

Similar threads

Forum statistics

Share this page

We've detected that you are using an adblocker.

Which adblocker are you using?

Disable AdBlock

Disable AdBlock Plus

Disable uBlock Origin

Disable uBlock