# Calculate if an x,y value falls in to the area on an polygon shape

Hi All

I have a polygon, min 3 vertices, max 999. Each vertice has an xy of it position and it also stores the forward and backward vertices that it is connected to.

I need to know how to calculate if a give x,y falls in the area of the polygon.

Example
Polygon values are :

vertice
---------
0=20,10
1=15,15
2=10,20
3=10,30
4=30,30
5=30,20
6=25,20
7=25,15
8=30,15
9=35,15
10=40,15
11=40,20
12=45,20
13=45,10

Hits
-----
a=38,20 - not in polygon area
b15,25   - in polygon area

All help is greatly appreciated
LVL 1
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
0
Commented:
0
Author Commented:
Hi Infinity08

any chance of a conversion please ?

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))

c = !c;
}
return c;
}
0
Commented:
>> any chance of a conversion please ?

A conversion ? You mean to VB ? I don't know VB very well, so I'll probably not be of a lot of help there. But you can read the algorithm (in text), and implement it yourself.
0
ProgrammerCommented:
Hi JMu5667,

it's not hard to undrastand what the code does!

from each point x,y you must check that the number of lines that intersect with y horizontal line.
if the number of intersect lines will be odd the point is an interior and else it is exterior.
0
RetiredCommented:
I think this uses a similar algorithm.

``````Option Explicit

Private Sub Command1_Click()
Dim VertexX(13) As Single
Dim VertexY(13) As Single

VertexX(0) = 20
VertexX(1) = 15
VertexX(2) = 10
VertexX(3) = 10
VertexX(4) = 30
VertexX(5) = 30
VertexX(6) = 25
VertexX(7) = 25
VertexX(8) = 30
VertexX(9) = 35
VertexX(10) = 40
VertexX(11) = 40
VertexX(12) = 45
VertexX(13) = 45
VertexY(0) = 10
VertexY(1) = 15
VertexY(2) = 20
VertexY(3) = 30
VertexY(4) = 30
VertexY(5) = 20
VertexY(6) = 25
VertexY(7) = 15
VertexY(8) = 15
VertexY(9) = 15
VertexY(10) = 15
VertexY(11) = 20
VertexY(12) = 20
VertexY(13) = 10
Dim ax As Single
Dim ay As Single
Dim bx As Single
Dim by As Single

ax = 38: ay = 20
bx = 15: by = 25
Debug.Print IsInside(14, VertexX(), VertexY(), ax, ay)
Debug.Print IsInside(14, VertexX(), VertexY(), bx, by)
End Sub

Function IsInside(iSideCount As Integer, sPointsX() As Single, sPointsY() As Single, x As Single, y As Single) As Boolean
Dim i As Integer
Dim bOddVertex As Boolean
Dim j As Integer
j = iSideCount - 1
For i = 0 To iSideCount - 1
If (sPointsY(i) < y And sPointsY(j) >= y Or sPointsY(j) < y And sPointsY(i) >= y) Then
If (sPointsX(i) + (y - sPointsY(i)) / (sPointsY(j) - sPointsY(i)) * (sPointsX(j) - sPointsX(i)) < x) Then
bOddVertex = Not bOddVertex
End If
End If
j = i
Next i
IsInside = bOddVertex
End Function
``````
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Middle School Assistant TeacherCommented:
You can use GDI APIs to help out...

The CreatePolygonRgn() API stores the point data and then the PtInRegion() API tells you if a point is inside that polygon.

See: http://www.experts-exchange.com/Programming/Languages/Visual_Basic/Q_20799010.html#9780085

0
Commented:
Here's a cool solution:
Add up the angles between the point in question and adjacent points on the polygon taken in order. If the total of all the angles is 2 * PI or -2 * PI, then the point is inside the polygon. If the total is zero, the point is outside.
http://www.vb-helper.com/howto_point_in_polygon.html
0
Commented:
is a lot of unnecessary evaluations of trig function
All you need to add up is whether the sum is positive or negative or zero,
which for the non-zero winding number definition of "inside", (which can differs from odd winding number or odd jordan curve crossings in cases when the polygon can intersect itself)
You can check that by keeping track of the sign of the intersects with y horizontal line instead of just the number
0
Middle School Assistant TeacherCommented:
Here is a bare bones example of using your sample data with the APIs I mentioned above:
``````Option Base 0
Option Explicit

Private Const ALTERNATE = 1

Private Type POINT
x As Long
y As Long
End Type

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
Private Declare Function PtInRegion Lib "gdi32" (ByVal hRgn As Long, ByVal x As Long, ByVal y As Long) As Long

Private points() As POINT
Private polygonRegion As Long

ReDim points(13)

Dim pt As POINT

pt.x = 20
pt.y = 10
points(0) = pt

pt.x = 15
pt.y = 15
points(1) = pt

pt.x = 10
pt.y = 20
points(2) = pt

pt.x = 10
pt.y = 30
points(3) = pt

pt.x = 30
pt.y = 30
points(4) = pt

pt.x = 30
pt.y = 20
points(5) = pt

pt.x = 0
pt.y = 0
points(6) = pt

pt.x = 25
pt.y = 15
points(7) = pt

pt.x = 30
pt.y = 15
points(8) = pt

pt.x = 35
pt.y = 15
points(9) = pt

pt.x = 40
pt.y = 15
points(10) = pt

pt.x = 40
pt.y = 20
points(11) = pt

pt.x = 45
pt.y = 20
points(12) = pt

pt.x = 45
pt.y = 10
points(13) = pt

polygonRegion = CreatePolygonRgn(points(0), UBound(points) + 1, ALTERNATE)
End Sub

If polygonRegion <> 0 Then
DeleteObject polygonRegion
End If
End Sub

Public Function PointInRegion(ByVal rgn As Long, ByVal x As Long, ByVal y As Long) As Boolean
If rgn = 0 Then
PointInRegion = False
Else
PointInRegion = PtInRegion(rgn, x, y)
End If
End Function

Private Sub Command1_Click()
Dim i As Integer

Debug.Print "Polygon Points:"
For i = LBound(points) To UBound(points)
Debug.Print points(i).x, points(i).y
Next

Debug.Print "Hit Testing:"
Dim ptA As POINT
ptA.x = 38
ptA.y = 20
Debug.Print ptA.x, ptA.y, PointInRegion(polygonRegion, ptA.x, ptA.y)

Dim ptB As POINT
ptB.x = 15
ptB.y = 25
Debug.Print ptB.x, ptB.y, PointInRegion(polygonRegion, ptB.x, ptB.y)
End Sub
``````
0
Author Commented:
Hi Guys, in the spirit of good will I have split the points as I feel there was a joint effort. Thanks to all how contributed.
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Visual Basic Classic

From novice to tech pro — start learning today.