Area of union of circles

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Area of union of circles

Yann GAVET
Hi all,

Sorry to bother with this probably naive question. I want to compute the
area of the union of a set of disks. I found the example of "2D
regularized boolean set-operations", at the end of this page:

https://doc.cgal.org/latest/Boolean_set_operations_2/index.html.

Is there a way to modify this example in order to compute the area of
the union, which is (if I am right) a general polygon with holes.


thank you for your time.

regards

--
Yann

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Area of union of circles

Efi Fogel
Hi Yann,

There is no out-of-the-box function in CGAL that does that.
Here is one approach.
First compute the general (circle-segment) polygon with holes.
If your resulting point set is bounded by (linear) segments only, then you can do the following:
Pick a point, say the origin, o; then, for every pair of consecutive points on the boundaries (either outer or holes) and o construct a triangle.
Sum up the signed area of all these triangles. (A clockwise triangle has negative area).
Essentially, you can do the same with circular arcs, only the computation of the area of a general triangle the boundary of which contains a circular arc is a more difficult.
(As a matter of fact such a general triangle can be self intersecting;)
Nevertheless, it is possible. If you implement a function that computes the signed area of such a general triangle, the rest is a simple loop....

Efi
   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




On Wed, 26 Feb 2020 at 16:10, Yann GAVET <[hidden email]> wrote:
Hi all,

Sorry to bother with this probably naive question. I want to compute the
area of the union of a set of disks. I found the example of "2D
regularized boolean set-operations", at the end of this page:

https://doc.cgal.org/latest/Boolean_set_operations_2/index.html.

Is there a way to modify this example in order to compute the area of
the union, which is (if I am right) a general polygon with holes.


thank you for your time.

regards

--
Yann

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Area of union of circles

Sebastien Loriot (GeometryFactory)
In reply to this post by Yann GAVET
As an alternative solution to Efi's, you can compute the boundary of the
union of the disks efficiently using the 2D Alpha shape package.

Then the area of the union of disk is given by a formula that involves
the signed arc length and angle between tangents at intersection point.
I don't remember precisely the formula but I guess you can easily find
it online.

For the union of disks, if you are interested we can send you a link to
some code that is computing the union of the disks that we wrote some
time ago (yet another piece of code that should be integrated into
CGAL).

Best regards,

Sebastien.

On 2/26/20 3:09 PM, Yann GAVET wrote:

> Hi all,
>
> Sorry to bother with this probably naive question. I want to compute the
> area of the union of a set of disks. I found the example of "2D
> regularized boolean set-operations", at the end of this page:
>
> https://doc.cgal.org/latest/Boolean_set_operations_2/index.html.
>
> Is there a way to modify this example in order to compute the area of
> the union, which is (if I am right) a general polygon with holes.
>
>
> thank you for your time.
>
> regards
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss