asked on

PointInPolygon() Function (Reprise)

I've asked this question, over here: https://www.experts-exchange.com/questions/20953778/Math-Related-Question.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!

ASKER CERTIFIED SOLUTION

fromeroj

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

bryker

ASKER

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.

fromeroj

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

bryker

ASKER

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);

fromeroj

in almost all cases yes.. expcept when i reaches poly.Length..

bryker

ASKER

But it can't can it? Your for loop is structured like so:

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

fromeroj

when i=poly.Length
i+1 is out of border...

bryker

ASKER

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

bryker

ASKER

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.