Is there a way to compute the empty area between a group of touching polygons?

Question

Given a bunch of convex polygons layed out like a house truss, is there a way to compute the empty area, or get a polygon for each of those "holes" between the polygons?

I tried starting from any given polygon and then finding the intersections between some of the lines of the polygons and somehow I'm stuck at how to properly select which lines to use for the intersections.

I then tried to verify for a clockwise detection of the area but it seem that my algo for determining the CW/CCW of two lines does not work as, I think, it act as if the lines have the same origin instead of being "in sequence" from each other.

Answer 1

According to comments the solution is quite easy

1.prepare data

• represent your mesh as table of points and remove redundant points (point = x,y,z... + int cnt=0; )
• and table of lines (line = 2 * index of point from point table + bool deleted=false)
• while creating table of lines for each used point increment its cnt counter

2.remove redundant lines (join border between thick lines)

• find all lines that are overlapping and lie on the same line
• they have the same or opposite direction
• remove the shorter one and dissect the bigger one and update all tables accordingly (also point cnt !!!)
• after this find all lines between points used booth more than twice
• delete them ...

3.find all closed loops

• something like this:

  1.create list of polygons

  • polygon is list of point indexes

  2.take any undeleted line

  • if found add new polygon to list and
  • copy its points to polygon
  • flag line as deleted
  • if not found stop

  3.find line with point matching last polygon point

  • add the other point to polygon
  • flag line as deleted
  • repeat bullet 2 until there is no such line found

  4.goto 1

4.now found polygon with the biggest bounding box

• this polygon is the outer perimeter
• so delete it
• also you can draw it by different color for debugging purposes

5.now sum the rest

• all remaining polygons are the holes
• so triangulate them
• and sum all triangle areas by basic math formula ...
• also you can draw them by other different color for debugging purposes

Answer 2

This is not a straightforward problem, as the complete geometry needs to be computed incrementally, using some intersection points and/or chamfering/trimming rules.

I imagine two approaches:

1) build yourself a toolbox of the required geometric operations (using analytic geometry), among which segment/segment intersection and probably a few others (which will map to the truss design rules); using this toolbox, construct all required polygon vertices "by hand", based on the picture; lastly, compute the area of the polygonal holes with the general formula: http://en.wikipedia.org/wiki/Polygon#Area_and_centroid.

2) use a ready-made polygon manipulation library like Clipper (http://www.angusj.com/delphi/clipper.php), which will allow you to draw the logs without much care about the trimmings at endpoints (you will perform a union of rectangles and get a polygon with holes).

After my understanding of your question, the first approach is better.

UPDATE:

If what you have is a set of polygons corresponding to every log, the answer is different:

If you only care about the total area of the voids, compute the area of the outer outline and deduce the areas of every log.

And if you need the areas of individual holes, then use the second approach: perform the union of the polygons and query for the holes.