excel-counting points in a given area

[msucog]

anyone happen to know a good way to count the number of points within a given area? let's say you have a map of the u.s. and there are 10 areas identified with some overlap. there's say 100 points spread out through all the areas and i want to count how many points fall in each area. you're given the lat and lon of each point and know the lat and lon of the intersection of each line that create each area. the areas are oddball shapes (not simple squares) with up to 8 or 10 sides.

the only way i can think of is to have several if statements to evaluate if each point lies below the upper line, left of the right side, above the bottom line, etc. then count if all cells return "true" or "yes" or whatever the output is for each if statement. the problem i see is that due to the oddball shapes, the point may not be left of a particular line on the right side since it's technically below it. for example the "." are inside the area, the "X" is the point, and the other is the right side of the area.

............../
............./
............/
.........../
...........\
............\
.............\
............X.\
__________\

any suggestions?

 

[GregLocock]

Great question

http://mathforum.org/library/drmath/view/69518.html

might give you some ideas



Cheers

Greg Locock

SIGlease see FAQ731-376 for tips on how to make the best use of Eng-Tips.

 

[electricpete]

Are the polygon's convex (i.e. concave not allowed)?

If so, there is a fairly simple way.

First assign number order to your Vertices in a given polygojn, traversing in a fixed direction - let's say CCW.

Then for each point Vertex Vk, compute the cross product of two lines:
Line1: Vk to Vk+1
Line2: Vk to P
(where P is this other point that you want to find out if it's in the interior of the polygon)

If the point is within the convex polygon defined by all those vertices, then all those cross products will be positive. If the point is not within that polygon, some will be + and some -




=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[electricpete]

of course I meant "vectors", not lines.

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[msucog]

not restraint on the shape. i may spend less brain cells just biting the bullet and writing a bunch of if statements using the equation of the lines.

 

[electricpete]

I'm not sure what the distinction of left/right vs above/below is when you have lines neither n/s nor e/w. But I think you intend to choose on or the other.

You could choose all up/down comparisons if you have no vertical lines. Or all left/right comparisions if you have no horizontal lines.

In the event you have both H and V lines, I would still suggest the vector approach. Define each line as an ordered pair. Then when looking from begin point to end point (in the direction of the vector), the target area is either on left or right half of the plane. Points on left which looking along the line vector will have cross product of Vertex1->Vertex 2 Cross Vertex1->Point as a positive value. Points on left as a negative.

I detest the idea of nested if statements personally. Would try to spread the logic out accross a spreadsheet a little more. But it certainly can be done by testing each point on the correct side of each line of corresponding shape.

Yet another approach would be to break the non-convex areas into convex areas and proceed as I described above. Every polygon can be brokwn into sum of a group of convex polygons.




=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[msucog]

i think the vector idea will work well enough to save me a little headache. thanks. (and i'm still open to any other ideas if some genious has an easy solution)

 

[GregLocock]

Just to be annoying I'll point out that both Windows and Excel have this capability built in. A flood fill in a graphics program is doing the same thing.

http://en.wikipedia.org/wiki/Point_in_polygon

suggests a couple of approaches.

Things you need to consider - is a point on the exact boundary included or not?

Can a point be in more than one region?



Cheers

Greg Locock

SIGlease see FAQ731-376 for tips on how to make the best use of Eng-Tips.

 

[msucog]

can you expand on your last post a little (and let me explain what i'm looking at)? i have a map of the u.s. and i have lat/lon of many thousand points. i also have ~10 areas confined in portions of the country so the points are concentrated and some even on top of each other. the only way that i've found to count them is to add data labels then move each individual labels to an open space then count the labels. at least if i could set up a range of cells to determine if the points are within each area, i could them slap a count statement in the spreadsheet.

can you provide a command or word that a help search might find? i can't find anything to help either in the help file or in the excel manual i have.

and yes, some of the regions overlap therefore the points fall in multiple areas. i don't mind summing areas to get the gross area i need. and i doubt any points fall on an exact boundary.

 

[GregLocock]

"Just to be annoying I'll point out that both Windows and Excel have this capability built in. A flood fill in a graphics program is doing the same thing."

What I meant is that deep down this is a very common graphics command.

Of the two approaches in the wiki I had greatest success with the winding angle. But I have not sorted it out yet.

Cheers

Greg Locock

SIGlease see FAQ731-376 for tips on how to make the best use of Eng-Tips.

 

[electricpete]

To revisit / correct my comments.

We were talking about setting up a table of begin/end points for each segment of each polygon, along with a definition of which side of the segment is in and which side is out. Then check each point against each segment using the cross product. If a point is on the correct side of all the segments in a polygon, then it is in the polygon IF THE POLYGON IS A CONVEX POLYGON. This won't work for concave polygons - you've got to split up your polygons into convex sub-polygons.

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[davidbeach]

If you have only convex polygons, you can quit checking for each polygon as soon as you find one side for which the point is on the wrong side of a side. No need to look at all of the sides.

 

[HgTX]

If it's a map of the U.S., it's not convex.

Hg

Eng-Tips policies: faq731-376

 

[electricpete]

Any polygon can be broken up into convex polygons. If nothing else, break it up into triangles.

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[GregLocock]

OK, here's the guts of a spreadsheet that looks at whether a given point is inside, outside, or at a vertex of, an irregular polygon that does not overlap itself. It can be concave or convex. It uses the winding angle approach, and complex numbers because excel is better at looking after the arguments than I am.

I have tried about 50 different points and it seems to work.

It is not elegant, and I think that it would work fine without generating the unit vectors.

So now you just need a VBA shell with the following pseudocode

For each state
score=0
load polygon into worksheet
for each point
if point is inside polygon then score=score+1
next point
write score to output sheet
next state
play_fanfare_tada




Cheers

Greg Locock

SIGlease see FAQ731-376 for tips on how to make the best use of Eng-Tips.

 

[msucog]

wow...i sure have forgotten how to do those calculations...i wasn't exactly great at them back in college. your spreadsheet seems to work well though. i'll have to decipher the calcs tomorrow. thanks.

 

[electricpete]

Another alternative:

http://home.comcast.net/~electricpete/eng-tips/PolyAnalysis.xls

The book-keeping for counting is done. All you have to do is break up your polygons into convex pieces. Enter the coordinates of each polygon in CCW order. Enter the coordinates of each point. Push the button. Results will appear.

My feelings won't be hurt if you choose another approach. It's good to have choices.

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[electricpete]

I left out a check for the segment connecting the last point in a polygon to the first point in the polygon. I'll fix that and repost.

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[electricpete]

Here is corrected version:

http://home.comcast.net/~electricpete/eng-tips/PolyAnalysisRev1.xls

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

 

[msucog]

i'll try them both out. thanks for the help.