0

I have a number of 2D (possibly intersecting) polygons which I rendered using OpenGL ES on the screen. All the polygons are completely contained within the screen. What is the most timely way to find the percentage area of the union of these polygons to the total screen area? Timeliness is required as I have a requirement for the coverage area to be immediately updated whenever a polygon is shifted.

Currently, I am representing each polygon as a 2D array of booleans. Using a point-in-polygon function (from a geometry package), I sample each point (x,y) on the screen to check if it belongs to the polygon, and set polygon[x][y] = true if so, false otherwise.

After doing that to all the polygons in the screen, I loop through all the screen pixels again, and check through each polygon array, counting that pixel as "covered" if any polygon has its polygon[x][y] value set to true.

This works, but the performance is not ideal as the number of polygons increases. Are there any better ways to do this, using open-source libraries if possible? I thought of:

(1) Unioning the polygons to get one or more non-overlapping polygons. Then compute the area of each polygon using the standard area-of-polygon formula. Then sum them up. Not sure how to get this to work?

(2) Using OpenGL somehow. Imagine that I am rendering all these polygons with a single color. Is it possible to count the number of pixels on the screen buffer with that certain color? This would really sound like a nice solution.

Any efficient means for doing this?

genpfault
  • 51,148
  • 11
  • 85
  • 139
Ken Toh
  • 3,721
  • 1
  • 24
  • 30

3 Answers3

1

If you know background color and all polygons have other colors, you can read all pixels from framebuffer glReadPixels() and simply count all pixels that have color different than background.

If first condition is not met you may consider creating custom framebuffer and render all polygons with the same color (For example (0.0, 0.0, 0.0) for backgruond and (1.0, 0.0, 0.0) for polygons). Next, read resulting framebuffer and calculate mean of red color across the whole screen.

Oleg Titov
  • 1,100
  • 1
  • 8
  • 13
  • Thanks. I was thinking that it would be neater to write to the stencil buffer instead. However as I am using OpenGL ES 2.0, glReadPixels() only accepts GL_ALPHA, GL_RGBA and GL_RGB as input format. Any other means that can allow me to read from the stencil buffer? – Ken Toh Jan 07 '13 at 02:42
  • Never worked with stencil buffer myself. You may try to use custom framebuffer in order to have the ability to rebind stencil buffer to color attachment and read from it... However, most probably next you'll have to convert data obtained to process it which will slow down processing. BTW, can't see why use of stencil buffer is neater. Anyway it's designed for different kind of job. – Oleg Titov Jan 07 '13 at 10:26
1

If you want to get non-overlapping polygons, you can run a line intersection algorithm. A simple variant is the Bentley–Ottmann algorithm, but even faster algorithms of O(n log n + k) (with n vertices and k crossings) are possible.

Given a line intersection, you can unify two polygons by constructing a vertex connecting both polygons on the intersection point. Then you follow the vertices of one of the polygons inside of the other polygon (you can determine the direction you have to go in using your point-in-polygon function), and remove all vertices and edges until you reach the outside of the polygon. There you repair the polygon by creating a new vertex on the second intersection of the two polygons.

Unless I'm mistaken, this can run in O(n log n + k * p) time where p is the maximum overlap of the polygons.

After unification of the polygons you can use an ordinary area function to calculate the exact area of the polygons.

Kimi
  • 13,621
  • 9
  • 55
  • 84
user1838636
  • 21
  • 2
0

I think that attempt to calculate area of polygons with number of pixels is too complicated and sometimes inaccurate. You can see something similar in stackoverflow answer about calculation the area covered by a polygon and if you construct regular polygons see area of a regular polygon ,

Community
  • 1
  • 1
Mihai8
  • 3,113
  • 1
  • 21
  • 31