Solved

Math-Related Question

Posted on 2004-04-14
20
698 Views
Last Modified: 2011-04-14
[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!


0
Comment
Question by:bryker
  • 7
  • 7
  • 3
  • +2
20 Comments
 
LVL 41

Expert Comment

by:graye
ID: 10824179
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
 
LVL 22

Expert Comment

by:_TAD_
ID: 10824334
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
 
LVL 85

Accepted Solution

by:
Mike Tomlinson earned 325 total points
ID: 10825043
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.AddLines(pts)
        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
 
LVL 22

Expert Comment

by:_TAD_
ID: 10825121


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 Comment

by:bryker
ID: 10825797
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 Comment

by:bryker
ID: 10825829
Tad:

>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
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 10825841
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
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 10825926
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
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 10826086
Sorry about the typos...

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 Comment

by:bryker
ID: 10826226
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
Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

 

Author Comment

by:bryker
ID: 10826319
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
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 10826550
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 Comment

by:bryker
ID: 10827002

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 .AddLines(oPointFs)
            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
 
LVL 12

Expert Comment

by:farsight
ID: 10827695
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

---
Given your initial spec,
   [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
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 10827728
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
 
LVL 22

Expert Comment

by:_TAD_
ID: 10827911


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
 
LVL 12

Expert Comment

by:farsight
ID: 10827959
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 Comment

by:bryker
ID: 10828111
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
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 10828129
Glad you got it working!

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 Comment

by:bryker
ID: 10828170

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

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Many of us here at EE write code. Many of us write exceptional code; just as many of us write exception-prone code. As we all should know, exceptions are a mechanism for handling errors which are typically out of our control. From database errors, t…
For those of you who don't follow the news, or just happen to live under rocks, Microsoft Research released a beta SDK (http://www.microsoft.com/en-us/download/details.aspx?id=27876) for the Xbox 360 Kinect. If you don't know what a Kinect is (http:…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now