Area of polygon

4
votes

I need to calculate area of 2D polygon. (any shape, any size etc...) I have only list of points, every points contains X and Y.

Polygons are in 2D block map, so: Normal polygon
But becouse I must use blocks/rectangles, then polygon looks more like that: Blocks polygon
So must calculate this: Area of polygon
Block is in area, only if more than 50% of block is in polygon OR is corner/point of this polygon (like this arm at the bottom of image).

That possible to calculate that? without getting minimal, and maximal points, and checking every single block...
I only found some code for normal polygons:

public int getArea(List<BlockVector2D> blockPoints)
{
    double result = 0;
    int j = blockPoints.size() - 1;

    for (int i = 0; i < blockPoints.size(); ++i)
    {
        result += (blockPoints.get(j).getBlockX() + blockPoints.get(i).getBlockX()) * (blockPoints.get(j).getBlockZ() - blockPoints.get(i).getBlockZ());
        j = i;
    }
    return (int) Math.abs(result / 2);
}

But I have no idea how to do that using blocks-point...


Sorry for size and weird images... and my English.

2
javapolygonarearectangles
"if more than 50% of block is in polygon" this is clearly not always the case in your example... I guess a block with a corner is always included? – tobias_k
"Sorry for size and weird images... and my English." Don't be. The pictures may be large but they are extremely helpful for all of us when trying to visualize what you are doing. And your english is just fine :) – takendarkk
I agree with tobias_k, and I think if you try to calculate the integral of the contoure it's both easier and more confident. – mok
Maybe this helps: For each block other than the corner blocks (which seem to be "in" the polygon no matter what), the block is more than 50% "inside" the polygon if and only if it's centre is in the polygon. (There may be an exception if an extremely thin and pointy "arm" of the polygon passes through the centre, as it is almost the case in the lower right corner.) – tobias_k
Alternatively, you could partition your polygon into convex polygons using an algorithm like Chazelle Dobkin, assuming you don't have to worry about self-intersection. Here is a pdf from Princeton about the algorithm. – Sam

2 Answers

2
votes

check out this algorithm, it's a bit complex but explains what you need.

http://www.mathopenref.com/coordpolygonarea2.html

0
votes

I don't have a perfect solution for, just an idea .. (maybe dumb, no guarantee):

I get it that you need to compute it extremely fast. So traversing along every point like:

area = 0;
foreach(point p : points) {
    area += testIfInsidePolygon(p);
}

is not an option.

I believe that there is no analytical solution to this problem that would result in a such nice algorithm that you provided. So my idea is:

  • traverse along each polygon vertex and using Bresenham's line algorithm (http://en.wikipedia.org/wiki/Bresenhams_line_algorithm) compute if particular point is on the edge of the polygon
  • store point locations in 2D k-d tree (http://en.wikipedia.org/wiki/K-d_tree) which is extremely efficient for space partitioning
  • if some point is already stored inside k-d tree, it means that you are dealing with situation like with your lover-right corner point
  • find the top-most and lower-most points using k-d tree
  • traverse from top-most to lower-most coordinate, cast the ray from the side and query k-d tree again for ray <-> polygon edge intersection points
  • using sum of differences between intersection points X coordinates you can calculate your area

Some need for special case corrections is extremely likely :)

This algorithm is by far faster than O(n^2) of traversing all points. However, you'll pay with complexity.