×
INTELLIGENT WORK FORUMS
FOR ENGINEERING PROFESSIONALS

Log In

Come Join Us!

Are you an
Engineering professional?
Join Eng-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!
  • Students Click Here

*Eng-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Jobs

excel-counting points in a given area

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?

RE: excel-counting points in a given area

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.

RE: excel-counting points in a given area

of course I meant "vectors", not lines.

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

RE: excel-counting points in a given area

(OP)
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.

RE: excel-counting points in a given area

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.

RE: excel-counting points in a given area

(OP)
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)

RE: excel-counting points in a given area

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

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

(OP)
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.

RE: excel-counting points in a given area

"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

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

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.

RE: excel-counting points in a given area

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.

RE: excel-counting points in a given area

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.

RE: excel-counting points in a given area

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

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

(OP)
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.

RE: excel-counting points in a given area

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.

RE: excel-counting points in a given area

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.

RE: excel-counting points in a given area

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

RE: excel-counting points in a given area

(OP)
thanks, i'll take a look.

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

Quote:

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


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

Doug produced a vba routine "inside".  
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

A few comments on how the Inside UDF works.

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
 

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Eng-Tips Forums free from inappropriate posts.
The Eng-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Eng-Tips forums is a member-only feature.

Click Here to join Eng-Tips and talk with other members!


Resources