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

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)

---

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.

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

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

---

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

---

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.

What kind of structure can i use for the points?
I think a graph is the better
don't you?

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.

And for the second case:

I'm sorry Bubba but i didn't say that i don't want to have concave poligons :)

I've only convex poligons

tree is better than a graph?

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.

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:

Intersecting an actual point should count as 2 intersections, not one. Which means that it intersects 7 times and not 4.

Quzah.

I guess that depends on how you look at it. An actual points only intersects the polygon once, but it intersects two of the bounding lines of the polygon.

A point counts as 2 intersections because in any closed figure or polygon a point represent a location where two lines meet each other. A line intersection test performed on the lines that share the point would reveal that the ray does indeed cross both lines since lines are infinite in length.

So it's 7.