?
Solved

PointInPolygon() Function (Reprise)

Posted on 2005-02-25
10
Medium Priority
?
1,145 Views
Last Modified: 2008-06-12
I've asked this question, over here:  http://www.experts-exchange.com/Programming/Programming_Languages/Dot_Net/Q_20953778.html

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].

Now, the VB.NET solution I was provided previously *does work*, except for a few drawbacks.

What I'd really like, though, is a procedure that isn't quite so expensive.  That VB.NET solution relies on the GDI+ namespace's GraphicsPath object.  These objects are expensive when your app is having to create hundreds or thousands of them.  Plus, there are some cludges that were necessary to make them work with longitude/latitude coordinates.

I'm looking for a purely math-oriented solution out there.  There are lots of PointInPolygon *algorithms* online, and I have no problem finding them.  But I need some help in finding one that really lends itself to a C# app that I don't want to spend forever coding.

Anyone got anything?  Thanks!
0
Comment
Question by:bryker
  • 5
  • 4
9 Comments
 
LVL 2

Accepted Solution

by:
fromeroj earned 1000 total points
ID: 13405086
Well.... if you do a puerly math solution, it will not be "part of C#"... and likewise.. the very specialized ways as using GDI will be very expecnsive... so i suggest you to use a PointInPoligon algorithm by the book...
i like a lot the cross number test since is quite simple.

i did a C# one...

using System;

namespace PointInPolygon
{
      public struct Point
      {
            public float x;
            public float y;
            public Point(float x,float y)
            {
                  this.x=x;
                  this.y=y;
            }
      }

      class Class1
      {
            static bool InPoligon(Point p,Point[] poly)
            {
                  int    cn = 0;    // the crossing number counter
                  // loop through all edges of the polygon
                  for (int i=0; i<poly.Length; i++)
                  {    // edge from V[i] to V[i+1]
                        if (((poly[i].y <= p.y) && (poly[(i+1)%poly.Length].y > p.y))    // an upward crossing
                              || ((poly[i].y > p.y) && (poly[(i+1)%poly.Length].y <= p.y)))
                        { // a downward crossing
                              // compute the actual edge-ray intersect x-coordinate
                              float vt = (float)(p.y - poly[i].y) / (poly[(i+1)%poly.Length].y - poly[i].y);
                              if (p.x < poly[i].x + vt * (poly[(i+1)%poly.Length].x - poly[i].x)) // P.x < intersect
                                    ++cn;   // a valid crossing of y=P.y right of P.x
                        }
                  }
                  return (cn%2==1);    // 0 if even (out), and 1 if odd (in)
            }
            
            static void Main(string[] args)
            {
                  Point p=new Point(0,0);
                  Point[] poly=new Point[4];
                  poly[0]=new Point(1,1);
                  poly[1]=new Point(1,-1);
                  poly[2]=new Point(-1,1);
                  poly[3]=new Point(-1,-1);
                  Console.WriteLine(InPoligon(p,poly));
                  Console.ReadLine();
            }
      }
}

remember that a point in the boundary is not consider inside the poligon..

-Regards
0
 

Author Comment

by:bryker
ID: 13405510
fromeroj:

Thanks!  Hey, if you wouldn't mind, would you please kind of "go over" the code you provided, as far as the premise of it?

I'd love to understand these 2 lines better--or really, at all.

   float vt = (float)(p.y - poly[i].y) / (poly[(i+1)%poly.Length].y - poly[i].y);

   if (p.x < poly[i].x + vt * (poly[(i+1)%poly.Length].x - poly[i].x)) // P.x < intersect

Thanks again.
0
 
LVL 2

Expert Comment

by:fromeroj
ID: 13405772
Well, to understand this method, i can describe briefly its objective...

Based on a know topology theorem, it said a point is "inside a curve" if a ray starting in that point cross a odd number of times the curve... in this case polygon is a particular case of curve.

then we use (i+1)%poly.Length because the poligon is ciclyc.. that is the point n+1=point 1 so.

Analitic Geometry Considerations:
the ray we chose is the ray with slope 0...
every point in the segment joining two point is a lineas combination of those...

Then we iterate on every segment...
then we see if the ray crosss the segment at any point.
that is quite easy and is the:

 if (((poly[i].y <= p.y) && (poly[(i+1)%poly.Length].y > p.y))    // an upward crossing
                         || ((poly[i].y > p.y) && (poly[(i+1)%poly.Length].y <= p.y)))
...

then if it crosses at any point, we only need to know if is at the right or left of the point
(we consider only the part in the right since is the ray we choose).

so those two linwes are the equation of the 2 lines (the segment in consideration and the ray)
and we calculate the x coordinate of the intersection, and see if it is at right or left of the inicial point.
 
   float vt = (float)(p.y - poly[i].y) / (poly[(i+1)%poly.Length].y - poly[i].y);
   if (p.x < poly[i].x + vt * (poly[(i+1)%poly.Length].x - poly[i].x)) // P.x < intersect

-Regards
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:bryker
ID: 13406104
Okay.  I'll chew on that and start testing with it.

Say, when you do this:

(poly[(i+1)%poly.Length].y - poly[i].y);

Why do you always modulus the length of the array?  I can't get my mind around this, for some reason.  Wouldn't it be the same result if you used:

(poly[(i+1)].y - poly[i].y);

0
 
LVL 2

Expert Comment

by:fromeroj
ID: 13406126
in almost all cases yes..  expcept when i reaches poly.Length..
0
 

Author Comment

by:bryker
ID: 13406619
But it can't can it?  Your for loop is structured like so:

   for (int i=0; i<poly.Length; i++)

0
 
LVL 2

Expert Comment

by:fromeroj
ID: 13406970
when i=poly.Length
i+1 is out of border...
0
 

Author Comment

by:bryker
ID: 13407186
Oh, I see...that gets you the "wrap-around" of comparing the Node.Last ->Node.First segment.

0
 

Author Comment

by:bryker
ID: 13592880
Sorry!  I didn't mean to abandon it.  It's a winner of a solution, as far as I've been able to tell.

Sorry, fromeroj.
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

We all know that functional code is the leg that any good program stands on when it comes right down to it, however, if your program lacks a good user interface your product may not have the appeal needed to keep your customers happy. This issue can…
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
Integration Management Part 2
With just a little bit of  SQL and VBA, many doors open to cool things like synchronize a list box to display data relevant to other information on a form.  If you have never written code or looked at an SQL statement before, no problem! ...  give i…
Suggested Courses
Course of the Month8 days, 15 hours left to enroll

621 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