excel-counting points in a given area
excel-counting points in a given area
(OP)
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?
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?





RE: excel-counting points in a given area
h
might give you some ideas
Cheers
Greg Locock
SIG:Please see FAQ731-376: Eng-Tips.com Forum Policies for tips on how to make the best use of Eng-Tips.
RE: excel-counting points in a given area
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.
RE: excel-counting points in a given area
=====================================
Eng-tips forums: The best place on the web for engineering discussions.
RE: excel-counting points in a given area
RE: excel-counting points in a given area
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.
RE: excel-counting points in a given area
RE: excel-counting points in a given area
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
SIG:Please see FAQ731-376: Eng-Tips.com Forum Policies for tips on how to make the best use of Eng-Tips.
RE: excel-counting points in a given area
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.
RE: excel-counting points in a given area
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
SIG:Please see FAQ731-376: Eng-Tips.com Forum Policies for tips on how to make the best use of Eng-Tips.
RE: excel-counting points in a given area
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.
RE: excel-counting points in a given area
RE: excel-counting points in a given area
Hg
Eng-Tips policies: FAQ731-376: Eng-Tips.com Forum Policies
RE: excel-counting points in a given area
=====================================
Eng-tips forums: The best place on the web for engineering discussions.
RE: excel-counting points in a given area
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
SIG:Please see FAQ731-376: Eng-Tips.com Forum Policies for tips on how to make the best use of Eng-Tips.
RE: excel-counting points in a given area
RE: excel-counting points in a given area
htt
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.
RE: excel-counting points in a given area
=====================================
Eng-tips forums: The best place on the web for engineering discussions.
RE: excel-counting points in a given area
http://
=====================================
Eng-tips forums: The best place on the web for engineering discussions.
RE: excel-counting points in a given area
RE: excel-counting points in a given area
h
includes an INSIDE() function that will check if a point is inside or outside a specified closed shape.
Doug Jenkins
Interactive Design Services
www.interactiveds.com.au
RE: excel-counting points in a given area
the other methods worked well too depending on the way one likes to do it. i'm not too comfortable in vba so the cell equations do better for my simple self. i've just got to get all the equations down to a one cell equation.
RE: excel-counting points in a given area
Once you have picked up the basics, writing a UDF is actually much easier than writing a hyper-complicated one cell equation. It really is worth the effort to learn.
Just a suggestion :)
Doug Jenkins
Interactive Design Services
www.interactiveds.com.au
RE: excel-counting points in a given area
Inputs: range containing polygone coordinates, range containing point coordinates
Output: 1 if point is inside, 0 if not.
I used Doug's routine in a spreadsheet (attached) to tabulate results for several points and several polygons. The pointn coordinates are vertical down the left side of the table, and the range containing the polygone coordinates are listed horizontally accross the top of the table. Each entry in the table grabs the corresponding point coordinates for it's row and the range of the polygon coordinates for it's column and gets a 1 or 0.
Should be self-explanatory to expand for your data. You shouldn't have to enter any ranges manually, just copy the formulas.
I tried to use all excel (except for Doug's vba). Got a little bogged down developing the range argument as you can see (although it works). I did have to resort to 1 more vba user-defined function evaluatexl to do what evaluate does in vba. One of the formula's works a little different differently in cell D5 than in the other cells to the right of it (returns the worksheet name along with the address)... I had to tweak the formula in D5 to compensate. I have no idea why that is. (any suggestions?)
=====================================
Eng-tips forums: The best place on the web for engineering discussions.
RE: excel-counting points in a given area
I fixed that in attached rev2.
=====================================
Eng-tips forums: The best place on the web for engineering discussions.
RE: excel-counting points in a given area
=====================================
Eng-tips forums: The best place on the web for engineering discussions.
RE: excel-counting points in a given area
The basics are quite simple, it counts the number of times a line drawn from the point, parallel to the x axis in increasing x direction, intersects the polygon. An odd number indicates the point is inside, an even number or zero indicates outside.
The problems are when the point is on or very close to a polygon edge (is it just inside or just outside?), and when the line exactly intersects a vertex (is that one crossing or two?)
The way I ended up going was to check if the point was within a small distance (1e-14) of the line, and if it was to treat it as being on the line, and therefore "inside".
On reflection this might not work well if the coordinates have a high value (such as typical grid coordinates). The "mindiff" constant could be changed to a greater value (say 0.0001, if working in metres), or possibly a better approach would be to divide the offset by the greater coordinate value, and treat anything less than 1e-14 as being zero.
For the case of the line intersecting a vertex I checked if both lines of the polygon were on the same side of the line (in which case the intersection was ignored), or if they were on opposite sides (in which case it was 1 intersection).
Interesting how complicated a simple problem gets when you have to program it into a dumb computer.
Doug Jenkins
Interactive Design Services
www.interactiveds.com.au