?
Solved

PointInPolygon() Function (Reprise)

Posted on 2005-02-25
10
Medium Priority
?
1,085 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
10 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
Industry Leaders: 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

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!

Question has a verified solution.

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

Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
Michael from AdRem Software explains how to view the most utilized and worst performing nodes in your network, by accessing the Top Charts view in NetCrunch network monitor (https://www.adremsoft.com/). Top Charts is a view in which you can set seve…
Monitoring a network: how to monitor network services and why? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the philosophy behind service monitoring and why a handshake validation is critical in network monitoring. Software utilized …

770 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