# Math-Related Question

[VB.NET]

Given:

[1]  One (x,y) coordinate pair (Double values)

and

[2]  One array of (x,y) coordinate pairs (structs containing 2 Doubles) that together define a closed polygon that does NOT intersect itself

I need to determine whether [1] falls within the area defined by [2].

Is there anything out there I can use for this?  I need something free.  Sample code or good pseudo code, please.

Thanks very much!

###### Who is Participating?

Middle School Assistant TeacherCommented:
You guys are making this way to difficult...   =)

Create a new project and add a Label.  As you move the mouse around the form, the label will show your current position and whether or not the point is contained within the polygon.

Regards,

Idle_Mind

Public Class Form1
Inherits System.Windows.Forms.Form

' Holds the vertices of our polygon
Dim pts() As Point

' GraphicsPath object to hold our polygon
Dim shape As New System.Drawing.Drawing2D.GraphicsPath

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
' Setup a polygon points
ReDim pts(5)
pts(0) = New Point(100, 50)
pts(1) = New Point(125, 60)
pts(2) = New Point(115, 80)
pts(3) = New Point(105, 70)
pts(4) = New Point(90, 55)
pts(5) = New Point(95, 50)

' Create and close the polygon
shape.CloseFigure()
End Sub

Private Sub Form1_Paint(ByVal sender As Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles MyBase.Paint
' Draw our polygon on the form
Dim p As New Pen(Color.Black)
e.Graphics.DrawPath(p, shape)
p.Dispose()
End Sub

Private Sub Form1_MouseMove(ByVal sender As Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles MyBase.MouseMove
Dim status As String

' Determine if the current mouse position is within our polygon
If shape.IsVisible(e.X, e.Y) Then
status = "INSIDE"
Else
status = "OUTSIDE"
End If

' Update our label
Label1.Text = "(" & e.X & ", " & e.Y & ") is " & status & " the polygon"
End Sub

End Class
0

Commented:
This is a typical Geographic Information System (GIS) function.... determine if a point is within a polygon.   So, you'll find better examples from that community.

The simplest technique is to first determine the artifical centroid of polygon (based upon average x and y values).  It may not be the true centroid, since it might fall outside the polygon.  Then work two areas calculations simulaneously, one set of calculations is the sum of the area of a set of triangles based upon your reference point and 2 points along the polygon.  The other set is based upon the artificial centroid.  As you work around the perimeter of the polygon (2 points at a time), you're summing the areas of the triangles.  This will essentially give you two different calculations for area of the polgyon.

If the reference point's calculated sum is less than or equal to that of the centroid, then it's within the polygon.

A more involved approach takes complex shapes into account and allows for "inversion" of the shape.  The technique is the same, it's just how you deal with inversions while summing the intermediate values.

Sorry I don't have any reference material with me
0

Commented:
I am assuming that you are going to maximize the area of the polygon.

For instance, let's suppose whe have the following points (bear with me, graphics don't exactly work here)

2     2   2

1   2       2

2     2   2

Depending on how I draw my line (to connect the 2's) I can either include or exclude the number 1.

take the x and subtract each of the array x's, then take the y and subtract each of the array y's.  Square each resultant, and sum the x's any y's together and take the square root (this will give you distance A^2 + B^2 = C^2).

Now find the slow of each line that is created.  Mulitply the distance by the slope to give you the weight of each line.  Sum them all together to determine if the end result is positive or negative.  if it's positive then the point lies outside the polygon.  if the result is negative, than the point is inside the polygon.  If you are feeling really ambitious you can find the slope of each line and determine the angle of assention and then take the cotangent to find out exactly how far away a point is from the nearest line.  but that's another story.

Here is an example:

[1]  - [4,5]
[2]  - [1,1], [3,7], [6,1], [6,7]

x's                      y's
4-1=3                 5-1=4
4-3=1                 5-7=-2
4-6=-2                5-1=4
4-6=-2                5-7=-2

slopes:                            Distances:
4/3                          sqrt(3*3 + 4*4) =  5
-2                            sqrt(1*1 + -2*-2) = 2.23
-2                            sqrt(-2*-2 + 4*4) = 4.47
1                              sqrt(-2*-2 + -2*-2) = 2.82

5*4/3 = 6.66
2.23*-2 = -4.46
4.47*-2 = -8.94
2.82*1 = 2.82

add them all up and you get a negative number.  Now remove the last point in the array (go from a rectangle to a triangle) and then run the process again, you will get a positive number (it lies outside the polygon).  finally... if the result is zero, then the point lies on a line.

0

Commented:

One thing you should note, if you get an "undefined" slope for more than one line, then your point also lies on a line between two points of the polygon.

That is, the only way to get a slope of undefined is if the [1] has the same verticle axis of [2a] and [2b]

If this is a square in 2 dimentional space and point [1] lies somewhere between two points, then you are directly on the line.

2a                  2c

1

2b                   2d

You will be directly on the line if one of these two conditions exist.

1) you get a slope of "undefined" for more than one point
2) you get a slop of 0 for the two closest points (smallest distance)
0

Author Commented:
Idle_Mind:

You're assuming that I'm using WinForms, and not ASP.NET, and that I'm even providing an interface at all.

In fact, I'm trying to create a web service--no GUI at all--to which other apps can submit parameters for me to test whether the point lies inside or outside a polygon.

0

Author Commented:

>I am assuming that you are going to maximize the area of the polygon.

I can't assume that the polygon's area is maximized.  In my case, the polygon is exactly determined by lines connecting the provided coordinates in sequential order.  The polygons may very well have a high degree of concavity.

0

Middle School Assistant TeacherCommented:
Ok.

The GraphicsPath class doesn't need an interface to work.  Can you use it in ASP.NET?  (Showing my ignorance here with ASP)

Idle_Mind
0

Middle School Assistant TeacherCommented:
From the Help File:

"ASP.NET is a compiled, .NET-based environment; you can author applications in any .NET compatible language, including Visual Basic .NET, C#, and JScript .NET. Additionally, the entire .NET Framework is available to any ASP.NET application. Developers can easily access the benefits of these technologies, which include the managed common language runtime environment, type safety, inheritance, and so on."

So you should be able to create an instane of the GraphicsPath class in ASP.NET, just as I have and use the IsVisible() function to determine if a point is withing the path (polyong).  A GraphicsPath object does not have a visual interface.

Idle_Mind
0

Middle School Assistant TeacherCommented:

So you should be able to create an instance of the GraphicsPath class in ASP.NET, just as I have and use the IsVisible() function to determine if a point is within the path (polygon).  A GraphicsPath object does not have a visual interface.

Idle_Mind
0

Author Commented:
Idle:

But your example is using pixel coordinates, which don't have any use to what I'm trying to do.

I need to stew on this a bit, but I'm warming to the idea.  My first questions (at least to myself) are:

(1) how do I go about transforming earth coordinates (-180<=x<=+180, -90<=y<=90) to something that the Graphics namespace is not going to explode on;

and

(2) once I've transformed those coordinates--remember, these are Floats, not Integers, and those handy-dandy Point structs you're using have X and Y properties of *Integer*--am I going to overflow the Integer type?  What I mean is, -179.123456 will have to (a) become positive, and (b) lose its decimal precision.  At first glance, it seems that I could (a) add 180 to it, and then (b) multiply it by 1,000,000.  That should not overflow a (4-byte) Integer.

But like I say, I need to stew on this.  I can't just take your code as it is and expect it to work, for the reasons above.

0

Author Commented:
Idle:

Upon re-reading, my above comment didn't sound appreciative enough.  I really am grateful, and am getting more hopeful all the time that I could use this.  I'm just thinking out loud.

My colleague (who's going to investiage this) points out that the PointF class can take single-precision values.  So my tranformation stuff above may be for naught.

Anyway, thanks, and I'll get back to you.
0

Middle School Assistant TeacherCommented:
I declared pts as an array of Point but you could also use PointF in it's place with no problems.

I have no experience with earth coordinates however so I can't help you there.  =)

I was not offended in any way.  I would just hate to see someone waste tons of time writing algorithms when the Framework appears to already have that capability.

Hope you can utilize the GraphicsPath class in your application.

Idle_Mind
0

Author Commented:

Idle:

I'm really having a time trying to get something to work that uses your concept.  Here's my procedure, which *always* returns False (not visible).

Do you see anything?  This is just my latest cut at it--I've also tried adding 180 and 90 to my x and y values, respectively, to remove all negative coordinates, to no avail.

'***********************************************************************
'*   PROCEDURE:  PointInPolygon()
'***********************************************************************
Public Function PointInPolygon( _
ByVal dblPointX As Double, _
ByVal dblPointY As Double, _
ByVal dblPolygonX() As Double, _
ByVal dblPolygonY() As Double, _
ByRef nReturnCode As Short _
) _
As Boolean

nReturnCode = 0

Try
'** Sanity checks
If ( _
dblPointX = 0.0 OrElse dblPointY = 0.0 _
OrElse _
dblPolygonX Is Nothing OrElse dblPolygonY Is Nothing _
OrElse _
dblPolygonX.Length <= 2 OrElse dblPolygonY.Length <= 2 _
OrElse _
dblPolygonX.Length <> dblPolygonY.Length _
) Then
nReturnCode = CShort(-2)
Return False
End If

Dim nCounter As Integer
Dim oPointFs() As System.Drawing.PointF
Dim oGraphicsPath As System.Drawing.Drawing2D.GraphicsPath

'dblPointX += 180.0
'dblPointY += 90.0

oGraphicsPath = New System.Drawing.Drawing2D.GraphicsPath()

If ( _
(dblPolygonX(dblPolygonX.Length - 1) <> dblPolygonX(0)) _
OrElse _
(dblPolygonY(dblPolygonY.Length - 1) <> dblPolygonY(0)) _
) Then
'** Dimension one longer for the "closing" point
ReDim oPointFs(dblPolygonX.Length)
'** Set the closing point's coordinates to those of the starting point.
With oPointFs(dblPolygonX.Length)
.X = CSng(dblPolygonX(0))
.Y = CSng(dblPolygonY(0))
End With
Else
ReDim oPointFs(dblPolygonX.Length - 1)
End If

For nCounter = 0 To dblPolygonX.Length - 1

'dblPolygonX(nCounter) += 180.0
'dblPolygonY(nCounter) += 90.0

oPointFs(nCounter) = New System.Drawing.PointF()

With oPointFs(nCounter)
.X = CSng(dblPolygonX(nCounter))
.Y = CSng(dblPolygonY(nCounter))
End With

Next nCounter

With oGraphicsPath
Call .CloseFigure()
'.FillMode = Drawing.Drawing2D.FillMode.Alternate
End With

If (oGraphicsPath.IsVisible(CSng(dblPointX), CSng(dblPointY))) Then
Return True
Else
Return False
End If

Catch oException As System.Exception

nReturnCode = CShort(-999)
Return False
End Try

End Function

0

Commented:
I like the .IsVisible approach in some ways, if you can get it working.  Unfortunately, a LOT of extra work is done by that approach.  (sanity checks, creating numerous objects, ensuring the polygon is closed)  It's probably a really slow algorithm.

If you're checking point-in-polygon many times, you'll want to find the most efficient algorithm you can.  It would be nice to know how you intend to use this routine, to help us determine what kind(s) of optimization are needed.

Here (near the bottom) are implementations of 4 different algorithms for Point-in-Polygon, along with a test harness.
Some algorithms work only for convex polygons, not the concave polygons you need.  So verify that you're using an appropriate algorithm.
[language C]
http://www.acm.org/tog/resources/RTNews/html/rtnv5n3.html

---
[1]  One (x,y) coordinate pair (Double values)
and
[2]  One array of (x,y) coordinate pairs (structs containing 2 Doubles) that together define a closed polygon that does NOT intersect itself

I was surprised that PointInPolygon wasn't defined more like this (where DoublePoint is a structure/class you've defined):
Public Function PointInPolygon( _
ByVal dblPoint As DoublePoint, _
ByVal dblPolygon() As DoublePoint, _
) _
As Boolean
(a) Furthermore, your initial spec states that we're getting a closed polygon, so why all the extra checks?
(b) Is is really important to get the nReturnCode?  I mean, if it fails, it fails, right?  Why not just let the caller catch the exception?  (c) What's wrong with a point at (0,0)?  In most cases, (0,0) is a perfectly useful point.  Don't add a special case unless it's really a special case.
[ I'm not criticizing.  Just wondering why all that's inside this little routine.  They seem more application-related, therefore I would expect the application to make sure that's it's data is OK well before getting to this routine. ]
---
As I understand it, CloseFigure will automatically add the closing line segment, so I don't think you need to do that separately.  (Verify it yourself, though.)
0

Middle School Assistant TeacherCommented:
Well, the last point doesn't actually have to be equal to the first point.  The CloseFigure() call will actually take care of that for you so I think you can safely get rid of that logic block.  =)

Other than that, I can't spot anything glaringly wrong with the code.  You could see if there is an exception being thrown by changing your catch block to this:

Catch oException As System.Exception
MsgBox(oException.Message)
nReturnCode = CShort(-999)
Return False
End Try

Silly question I'm sure...but have you tried testing the sub with a simple shape like a rectangle and a point within?

Idle_Mind

0

Commented:

Idle_Mind> you've got some really great suggestions, but I can't help but think that there must be an easier method.

What about finding the largest distance between a given point and one of the points in the polygon.  Then, using that distance+1 create 360 lines extending outward from the point (mathematically speaking of course), one for each degree.  And then run a simply parity test to see if there are any non-intersecting rectangles.  Each line radiating outward would be a rectangle and then each of the lines between specified points would form a rectangle.  Then you could simply test each line to the polygon rectangles in turn until you get an intersection.  If no intersection is detected after 360 trials, then there is obviously an opening.

Granted, it's not very efficient (you'll have to do 360 searches, or more if you want less potential error)
0

Commented:
Here's another site that has a reasonably straightforward explanation of a couple of algorithms.  It presents lots of diagrams and pseudo-code and C++ code.  (I don't see any "++" features though.  Looks like C to me.)
The algorithms and their implementations are brief.
http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm

Another nice thing about using these algorithms, instead of using .IsVisible, is that you can just stick with double types.  No worries about conversions to single.
0

Author Commented:
Idle:

It's working!  I couldn't get PointF objects to work, so I'm using Point objects now.

I'm testing it using a MapPoint (web service) app and various polygon shapes.  Looks good.

I'll grade this question today or tomorrow.

Thanks!
0

Middle School Assistant TeacherCommented:

I was just about to post that I tested your function in my app and it seemed to work fine to me....

Idle_Mind
0

Author Commented:

Farsight:

>I was surprised that PointInPolygon wasn't defined more like this (where DoublePoint is a structure/class you've defined):

I'm going to expose this function as a web service method.

>Furthermore, your initial spec states that we're getting a closed polygon, so why all the extra checks?

Just in case.

>Is is really important to get the nReturnCode?

I don't know if it's "really important".  Is it really important to omit it?

>In most cases, (0,0) is a perfectly useful point.

Not in this case.  Not many gasoline stations adrift in the Atlantic.

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.