4
$\begingroup$

I have a complicated polygon in the 2d plane, that is an RegionIntersection of RegionUnion of triangles.

Finally, I want to calculate it's Area. Unfortunatly, the Area is really slow. I am not sure why, but presumably because it calculates the result analytically.

I have an example that represents the shapes I am dealing with:

TotalTime = 0;
For[cc = 1, cc <= 50, cc++,
  (* Reconstructing roughly the shapes I am using *)
  BoundIntersect = RegionIntersection[
    RegionDifference[Triangle[RandomReal[{-0.2, 0.2}, {3, 2}]], 
     Polygon[RandomReal[{-0.2, 0.2}, {3, 2}]]], 
    RegionUnion[Triangle[RandomReal[{-0.2, 0.2}, {3, 2}]], 
     Triangle[RandomReal[{-0.2, 0.2}, {3, 2}]], 
     Triangle[RandomReal[{-0.2, 0.2}, {3, 2}]], 
     Triangle[RandomReal[{-0.2, 0.2}, {3, 2}]], 
     Triangle[RandomReal[{-0.2, 0.2}, {3, 2}]]]];

  CurrentTime = AbsoluteTime[];
  BoundaryIntersectRatio = Area[BoundIntersect];
  TotalTime += (AbsoluteTime[] - CurrentTime);
  ];
Print["Total Time: " <> ToString[TotalTime] <> " sec."];

Can you speed it up? In particular, error-ratios in the order of $10^{-4}$ are tolerable.

Update (25.12.2019):

A fair comparison (100 iterations with same polygons for each method):

  1. Henrik Schumacher's method using undocumented Graphics`PolygonUtils function: 0.75005 sec.
  2. Alx's suggestion using BoundaryDiscretizeRegion: 5.03149 sec.
  3. My original method: 24.50163 sec.

Result: Speedup of >factor 30! And learned about undocumented function that i can use all over my code. Fantastic, thank you!

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Maybe some speed-up can be obtained with BoundaryDiscretizeRegion: Area@RegionIntersection[BoundaryDiscretizeRegion@RegionDifference[...],BoundaryDiscretizeRegion@RegionUnion[...]]. $\endgroup$ – Alx Dec 24 '19 at 2:32
  • $\begingroup$ You can try one of the implemenations of the shoelace formula: mathematica.stackexchange.com/a/207903/280 $\endgroup$ – Alexey Popkov Dec 24 '19 at 9:10
2
$\begingroup$

These undocumented functions do the job almost two orders of magnitude faster:

BoundIntersect = Graphics`PolygonUtils`PolygonIntersection[
    Graphics`PolygonUtils`PolygonComplement @@ (Polygon /@ 
       RandomReal[{-0.2, 0.2}, {2, 3, 2}]),
    Graphics`PolygonUtils`PolygonCombine[
     Polygon /@ RandomReal[{-0.2, 0.2}, {5, 3, 2}]]
    ];
Graphics`PolygonUtils`PolygonArea[BoundIntersect]
Improve this answer
$\endgroup$
  • $\begingroup$ Area[BoundIntersect] returns different result than Graphics`PolygonUtils`PolygonArea[BoundIntersect]. Why? $\endgroup$ – Alexey Popkov Dec 24 '19 at 8:57
  • $\begingroup$ Good point. I also observed this. Probably some sign errors. But Area[BoundaryDiscretizeRegion@BoundIntersect] returns the same result as Graphics`PolygonUtils`PolygonArea[BoundIntersect], so I am quite confident that this result is true. Of course, this requires some further testing... $\endgroup$ – Henrik Schumacher Dec 24 '19 at 9:03
  • $\begingroup$ Thanks this is great! How do you find about undocumented functions? And how do you get more infos about this specific one? $\endgroup$ – Mario Krenn Dec 26 '19 at 0:53
  • 1
    $\begingroup$ Well, they are undocumented, so you hardly can find out. What I did to find it: You can search all Mathematica contexts for a symbol that has Polygon in its name by evaluating ?*`Polygon*. Then I saw that the context Graphics`PolygonUtils might contain quite useful functions (see ?Graphics`PolygonUtils`*) The rest is just trying out different ways to call the functions in order to figure out the correct syntax. This works more often than one might expected. $\endgroup$ – Henrik Schumacher Dec 26 '19 at 8:45
  • $\begingroup$ Those undocumented are usually often backends to the more fleshed-out built-in functions. Often, they lack all the fancy argument processing capabilities, but this leads not seldomly to higher performance. IHowever, IIRC, the functions from the context Graphics`PolygonUtils predate all the Region-related functions. $\endgroup$ – Henrik Schumacher Dec 26 '19 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.