1

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?

enter image description here

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.

Stécy
  • 11,951
  • 16
  • 64
  • 89
  • Do you have some ideas how to approach the problem maybe? – Niklas B. Mar 13 '14 at 21:53
  • 1
    Also, what is your input. You say "convex polygons layed out *like a house tross*". I find that hardly precise enough to draw any conclusions – Niklas B. Mar 13 '14 at 21:54
  • Does http://doc.cgal.org/latest/Boolean_set_operations_2/index.html help? – MvG Mar 14 '14 at 08:45
  • I assume your lines are with some thickness in that case you need all the lines inner and outer separated. You may already have them in your mesh if not you need to find the outlines , then polygonize all inlines (find all closed non-separable loops) then triangulate and then simply summ all triangle areas together – Spektre Mar 14 '14 at 09:06
  • there is an shortcut if you do not need too much precision ... draw image on bitmap , fill the background with some color , count all pixels with original background color (white usually) and multiply the cunt by pixel area (more resolution get you more precision) – Spektre Mar 14 '14 at 09:09
  • @NiklasB. Updated my question with additional details. Each individual member of the truss is a polygon. I'll update the image with a better one. – Stécy Mar 14 '14 at 12:03
  • @Spektre Using a bitmap is not an option as this is not precise enough. Updated the question with more precision about the input data. – Stécy Mar 14 '14 at 12:05
  • 2
    @Spektre multiply the _what_? :D – Gusdor Mar 14 '14 at 12:36
  • @Gusdor :) typo yes multiply the original background color pixels count by the area of single pixel (width of pixel * height of pixel in original dimensions represented by the bitmap) also the precision can be boosted by doing few scales and guess-interpolate the size of very big scale (high DPI bmp) ... but newer actually tried that one – Spektre Mar 14 '14 at 13:37
  • @Stécy I still dont know what kind of input you have? the complete polygon (or set of quads representing thick lines) or just lines+thickness ? – Spektre Mar 14 '14 at 13:43
  • @Spektre In the figure there are 8 polygons to which I have the cartesian coordinates. Line thickness is not relevant for my problem. As an example, the bottom polygon consists of 6 points. – Stécy Mar 14 '14 at 13:47
  • btw may be will be more easy to find just outer perimeter polygon and the iner area is then its area - sum of all sub polygons from input ... – Spektre Mar 14 '14 at 16:17
  • Yeah, tried that but somehow my algo was not working correctly. I tried by going from one polygon (say the bottom one) and finding the intersections between all the lines with the lines of other polygons. Then I tried to locate the inner area but failed since I was not able to determine how to properly "turn" around the polygons outside. – Stécy Mar 14 '14 at 17:05

2 Answers2

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 ...

enter image description here

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
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Thanks for the detailed answer. If I understand correctly, I need to consider all my polygons as a list of points and then proceed from there? Would this result in losing where is the inside of each polygon ? – Stécy Mar 14 '14 at 14:27
  • Also, in point 2 you mention thick lines. I'm confused by this. What do you mean? – Stécy Mar 14 '14 at 14:28
  • bullet 2 is the most problematic ... debug it properly. the line removal must be done after all dissections !!! also if your 'quads' are not aligned then the lines could overlap only partially so you need to keep it mind in that case – Spektre Mar 14 '14 at 14:28
  • the thick line is the single polygon in your input (wood bar) whole bullet 2 is removal of all join lines bluish line on the image – Spektre Mar 14 '14 at 14:36
  • here you can find closed loop finding example http://stackoverflow.com/a/21884021/2521214 – Spektre Mar 14 '14 at 14:38
  • Thanks a lot for the pseudocode, I will have to digest this to C# and I'll let you know of the result. – Stécy Mar 14 '14 at 14:49
0

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.