# Calculate Point in Area

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 04-05-2005
ilmarculin
Calculate Point in Area
Is there an algoritm to calculate the sum of the point in a figure on a plain?
Look the example:

http://img197.exs.cx/my.php?loc=img1...ntitled0zx.jpg

I have the 4 initial points...how can i calculate it?

Or if i have more than 4 pints...like this one

http://img197.exs.cx/my.php?loc=img197&image=bit4ab.jpg
• 04-05-2005
Jaken Veina
If you mean you want to calculate the area of those points, you would simply find the distance between each pair of points and add those results

To calculate distance, use the formula:

Code:

`distance = the square root of (((x of point 1) - (x of point 2))^2 + ((y of point 1) - (y of point 2))^2)`
• 04-05-2005
pianorain
Quote:

Originally Posted by Jaken Veina
If you mean you want to calculate the area of those points, you would simply find the distance between each pair of points and add those results

Actually, that would be known as the perimeter, not the area.

Basically, you're looking for the set of integer solutions to a system of inequalities. I'm still thinking about this one; it's a good thought problem.
• 04-05-2005
ilmarculin
Quote:

Originally Posted by Jaken Veina
If you mean you want to calculate the area of those points, you would simply find the distance between each pair of points and add those results

To calculate distance, use the formula:

Code:

`distance = the square root of (((x of point 1) - (x of point 2))^2 + ((y of point 1) - (y of point 2))^2)`

No is not that :)

For example...in the first figure there are 14 points....in the seconds 103 points
• 04-05-2005
pianorain
I did this in a pretty brute-force way. You enter all the inequalities, the x-range, and the y-range. The code checks every inequality for every (x,y) in the two ranges. If an (x,y) passes all the checks, it is added to the list of successful hits. Unfortunately, my code will do you no good since it's C++. However, the basic idea should be the same.
Code:

```Step 1: Enter all the inequalities     - if you're clever, you can probably figure out how to just enter the       endpoints of the lines and let the program take care of creating the       inequality Step 2: Enter the x-range and the y-range. Step 3: For each (x,y)           if (x,y) passes each inequality               update a counter or add it to a list```
• 04-05-2005
treenef
Wouldn't the inequalities for the lines be a system of n-simultaneous
equations. Whereby the system called be solved using numerical
methods such as 'Guassian elimination' etc?
Code:

```    i.e solve for 'x'  whereby y>=1/2 +3, y<=4-2x, y>=5     etc... etc```
• 04-05-2005
Jaken Veina
Well, he never said area in his post (except for the title which didn't really say he was looking for the area either).

But, yeah that would work. Keep in mind, though, that you'd only want to test intergers for x and y. Really, it's just four basic algebra equations with either less than and equal, or greater than and equal. Just write the equation for the line of each side (or have the computer do it for you) and test the variable against each equation. If it doesn't go with one of them, it's not in the figure.

EDIT: After seeing your previous post, yeah you got it.
• 04-06-2005
ilmarculin
What kind of structure can i use for the points?
I think a graph is the better
don't you?
• 04-06-2005
VirtualAce
Quote:

If it doesn't go with one of them, it's not in the figure.
This completely falls apart with concave polygons. The easiest way to test geometrically if a point lies inside of a polygon in 2D is to use the scanline test.

Create a vector from the left side of the screen through the point to the right side of the screen. Count how many times the vector crosses a polygon line. If the number is odd, the point is inside of the polygon. Otherwise it is not.
• 04-06-2005
VirtualAce
And for the second case:
• 04-06-2005
ilmarculin
I'm sorry Bubba but i didn't say that i don't want to have concave poligons :)

I've only convex poligons
• 04-06-2005
ilmarculin
tree is better than a graph?
• 04-06-2005
quzah
No. One can grow fruit and such, or provide shade at the right time of the year. The other doesn't.

However, Bubba's method for solving if a point is in a polygon is probably the best method. Go Google for the topic, and you'll find it's the method suggested.

Really though, if all you want to do is count how many points are in a poly, you can use a grid. Here's how:

Find the four cardinal coordinates:
1) North most.
2) East most.
3) South most.
4) West most.

South - North = number of rows.
East - West = number of columns.

Now map all of your coordinates.
Now draw lines between all of them, "filling" the line's cell with some value representing a line.
Now use Bubba's method for counting how many points in each row are within the polygon.

Sounds good on paper anyway. ;)

Quzah.
• 04-06-2005
Bajanine
I like Bubba's method although I know it as 'ray testing'. I realize ilmarculin said no concave polygons but just in case someone else is looking into this don't forget about cases like test point 2 in this example which intersects four times and is still included in the polygon:
• 04-06-2005
quzah
Intersecting an actual point should count as 2 intersections, not one. Which means that it intersects 7 times and not 4.

Quzah.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last