Thread: Calculate Point in Area

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    16

    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
    Last edited by ilmarculin; 04-05-2005 at 08:54 AM.

  2. #2
    Work in Progress..... Jaken Veina's Avatar
    Join Date
    Mar 2005
    Location
    Missouri. Go Imos Pizza!
    Posts
    256
    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)

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Registered User
    Join Date
    Feb 2005
    Posts
    16
    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

  5. #5
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  6. #6
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    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

  7. #7
    Work in Progress..... Jaken Veina's Avatar
    Join Date
    Mar 2005
    Location
    Missouri. Go Imos Pizza!
    Posts
    256
    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.

  8. #8
    Registered User
    Join Date
    Feb 2005
    Posts
    16
    What kind of structure can i use for the points?
    I think a graph is the better
    don't you?

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    And for the second case:

  11. #11
    Registered User
    Join Date
    Feb 2005
    Posts
    16
    I'm sorry Bubba but i didn't say that i don't want to have concave poligons

    I've only convex poligons

  12. #12
    Registered User
    Join Date
    Feb 2005
    Posts
    16
    tree is better than a graph?

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  14. #14
    Registered User Bajanine's Avatar
    Join Date
    Dec 2001
    Location
    The most peaks over 10,000 feet!
    Posts
    396
    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:
    Favorite Quote:

    >For that reason someone invented C++.
    BLASPHEMY! Begone from my C board, you foul lover of objects, before the gods of C cast you into the void as punishment for your weakness! There is no penance for saying such things in my presence. You are henceforth excommunicated. Never return to this house, filthy heretic!



  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Intersecting an actual point should count as 2 intersections, not one. Which means that it intersects 7 times and not 4.

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. rotating around object (looat)
    By jabka in forum Game Programming
    Replies: 13
    Last Post: 06-18-2008, 05:02 PM
  2. Area of irregular shape
    By Brian in forum Game Programming
    Replies: 4
    Last Post: 06-23-2004, 10:54 AM
  3. Array of pointers to point objects
    By totalfreeloader in forum C++ Programming
    Replies: 6
    Last Post: 11-27-2003, 09:26 AM
  4. observing whether a point is in a triangle???
    By hebele in forum C++ Programming
    Replies: 1
    Last Post: 05-19-2003, 03:38 PM