Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Understanding Exact Computation in CGAL

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Understanding Exact Computation in CGAL


Chronological Thread 
  • From: Himanshu Sharma <>
  • To: "" <>
  • Subject: Re: [cgal-discuss] Understanding Exact Computation in CGAL
  • Date: Fri, 20 Nov 2020 04:19:55 +0000
  • Accept-language: en-US
  • Arc-authentication-results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=northeastern.edu; dmarc=pass action=none header.from=northeastern.edu; dkim=pass header.d=northeastern.edu; arc=none
  • Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=xfb/kz8lnyq7zc/VOa+bH8bzdife14vhBInrGwhYdio=; b=L9cS1Gn6loOcGe03ZD2Wib66Q1NRaqQB4ji6R2T13pr0SNPDrvn7ladyRa8ofYRN4Q1QqEp73PW4IrqxJ/Eo1GJxjGUL0iA6dszcPh5Qo/dYBlC+zbup2gNtpKONVx64nE36w75sVtA1TgLB/V1kMVeOaKvarvC1cl4VuTF6RnDpossUI48OQ7aRUs47vjprLsLBwZs3vgHi7Z50yM+fzrwfqbbjzuxDZouBnqpJoJzZ3/FzSWW0APa+wu7qC+fJe8mEKYhMvlHeea/nMIM/5gyCqvioGhM7HEgVz76OoK4SlqxFl3ZMNfvgIlRiiTPnI4YA/UW/t+W6jI+nZaD8cA==
  • Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=mVHsBrjXFVO0MZUJ95GLifhxUNmHflIDCXR0GRJLqaqF5oP/A0O1d3HOGp6546VSe8stq5e73UFEkBH3bTP9YbB/UoHRTmR6Opqo+KXju56DMqQ5RT2Sp6xFbkDAH09YXsnZ4nJR0pxngjhvSA48SUpy2lr0xJY6aJ59/9YldOSyECJTMhoOAd3fWdUoq0xsu8pI0EVYk4BaEuaC/opPrII+Onz/UujBEhgTQUGhC/e+w3aYm2GTRd//NKvCO+/3wvq9bktm9uXKupk771TOVoAcHobyP7dgzqON31oPuNak/rrvpXyMwm9/h8WBja0QjMBg2hVxhU17x3bSUJkZMg==
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=Pass
  • Ironport-phdr: 9a23:FyJgohCOTR1b2/2OPNrDUyQJP3N1i/DPJgcQr6AfoPdwSP/7oM+wAkXT6L1XgUPTWs2DsrQY0rWQ6vuxEjdbqb+681k6OKRWUBEEjchE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i764jEdAAjwOhRoLerpBIHSk9631+ev8JHPfglEnjWwba5wIRmssAncuM0bjYRsJ6s/1xDEvmZGd+NKyG1yOFmdhQz85sC+/J5i9yRfpfcs/NNeXKv5Yqo1U6VWACwpPG4p6sLrswLDTRaU6XsHTmoWiBtIDBPb4xz8Q5z8rzH1tut52CmdIM32UbU5Uims4qt3VBPljjoMOjgk+2/Vl8NwlrpWrhK/qRJi347aboKbNPR8caPcYdwVSnFMUdxNWyBdGI6wc5cDA/cHMO1Fr4f9vVwOrR6mCAeuBePvzyVHhnnt3a06zuQqDBzI3Aw6ENIUtXTbtsj+OaAJUeC11qbI1zDDYOlM1Tf96YjIdwssofeLXbJqbcrRyVcgGBnejlWMt4PlJTWV2v4TvGeG8uptTOSigHMopA9tuDag3NssipXXiYIPzFDJ7SZ0zYk6KNC3S0N1b96pHZtfuS+VNYZ6XsMsT390tSskxbMLp5+2cicKxpkjxxDSZf6KfpWV7x/tUOufLjh1iXFjdbmiiRiy9k2gxff9VsmyyFtKqTdFksXItnAK0BzT6dKLRed6/kekwTqO1wfT6vxYIUApjqXUNYQtzaI3lpoWqUjCHij2mFjqjK+LbEkr4fan5/z7bbXpvJCcM5V4igbkMqQhgsC/AOI4MhIPX2eB4+i82qfj8EvkS7tJlv07iqbUvIzAKcgGuqK0ARVZ34Qi5hqlEjur3toVkWEaIF5Zex+LlYrkN0vQLPzkEfuzmUqgnThryv3AI7bvGI/CLmLZn7fkZbt961BTyA40zd1H/5xZFrYPLO7tVkPoqtHXDAI1PxWzw+n8FtpxzIQeWX+TAqCCN6PSrFmI6f81L+mUfo8Vvyr9JOY56P7yjH85nlkdcbOu3ZsKdHC4GvNmI0KaYXb2ntgBFmIKshI/TOzsllKCTSZeanmuU64m+z03FICrAZ3BS42smrCNwSm2E5NOamBDEF+MEHPod4ueW/cLbSKfOtRhkjweWri7To8uzwuitA/7y7piNefU/CoYtYj/1Nh1+eLcjwoy9SBqAMSH1WGBVX97kX4VRzMuxqBwvVR9ykuf0ah/m/FXCdNT6OlNUgsjKJHczvd6BMzvWgLaZdeEU02mQ9WjATEpVN092d4OY0BnG9WjlB/PxSSqA6VG34GNH4E+p6LAw2DqdYE6zX/DjfNnlFAoT89OM269wLZl8BTeDJLIlEPfkLu2caMb32jG82LEmneUuBRYTBJoSuiedD1FSAaMg8/o41vLCb6oE7UudAVbhJSsMbpPctSk13tHQvnkdY7waG24nyK8BA2D26iXIobjZ2xIhHmONU4fjgpG/WqaLRNsQWCnqmeHVnp1HFziZ0Lq8vI4sGm8UkI/0wCNaQtmyqax/RkWw/ebTrREw6gA7Sc9ty1vUQ2Ukoj4RoCuvBtkZKwaYNUn4V4B23iU7SJmL5m4Ju04qF8YfQM65W3l2BxzT4lBisM3t2hkxQ9qeq6RzFoUL2/VgruoY/CIAXLy9QqqYujW21STjI6Q/b0T6PkxsEnupgfvG0Y/vipM34VegnWVvcqRBVFCDZuoXhY6pkIi972KMiJivorZ3CEhboK94jLP0Ih5XeIsw038c95SOajVHl77SJxKDZn0cbEnxBX2RUpJY8sKufEfYZj5K6Ldh/D0Zbc8wmP93T0Wrd9W70SP8S1jTKOX9Ko67emS8TmcXWzw3FqwkP/Wm4dFQBpOAU694DfBKKdQQoZQRKcJDmaQecmq48dfhrrGeVRk9X/9JlBf2MaWZhu2RH7N4yZxi2ER+TH8tWbn5GUsy2lnp6+HjzfCyvjrIUomZD5EH2pj3XHyE4aptfk4XUGLXlkluSaO63T27LZHhI8jd2/4flwYIni7dE0sW66o5aCPeMNV9p4k5H0EbeKnfFrPSqLhuwBIlGTlFm4HnnYgfj+nvpT/nAc8kHiaMHt4sHvef4d32Avb49vfA/VW231RWTN83DnLGkCncoKAsI+62s3tqfG7T2vnEJxVayjii42a+XGV/nxvGRTyxd6ynNPgXFIU2iDy05xmVD7DsQ3nLIDuz/e2OP5uKxE0SQDXs5M3RaplkoIqgZhW2Xkfy8nN+30djWf+OM5H1Lj4KncBWHNU6NKJ61nr0RY8dXvSl97wD3nNz5o7P4m2MjMdhXs04skWRfi/5exJkCAv8gOxpAuKPfR0kz4WmPF/4SVL0+tY4lNww3rQXZtKUBZzZWGzvErTsIzn9/oJOz/+LebhjxonzJ3+J4yEoQdbR3C0JbweIgFo5OpNK1iX3C3++6PbWdvXbPc46gKwkT7fqsR8KbYatMMrhy1mBzj5oFg36u8fpj5E4ZCb4qmEcmVkw724JjV6BgPeRp02/Gmg1ooTwe3Ph9j3UJxkAmYQUJL0RKf4MWxCuq/kNlaoDg8yt02yO7vWPj7O5GpbhHz9H7u1K1G8eCEf5up5FETNaRdzzgkRRGYgk4U0DB6nyJm5I3p//S0bxkL9rk5M1v5wLEu4FWHWoV7yLCw9RpWbLRxV9Uda/UDJPMeC7+V1WSZF4pmmqw/LIWueIFNVF2VcWlCYH0uuZZDjv/eNqcaDF++mJr3PZ6+PoKpQTbrS64m+15NvsmyiN8OBOTQ4IfY0004GUXFiENnCgHsDQjAewnqRPPOdvwq2xiBnspW/7OjzQ1Cooo2GDuIId85m9R2ygKGALKiIniFlJD1E15QKg3jV1LwY211UgCZrMG6wC7BVtTLRVLmdwYYaVTBWMQ1oJc5Q5uQ92BNMMIjVkJ6v+KVpi+Y8Rg1rVFrvnYzzS8cFKmX4OFLcD1uQL/qPICWYz8jraPbkFfAPp70N+kKbojaSCUrqeDSCknS1DxaoK/1MgSiAIBFEvsewfgsgVkPvENm3ZBTgb4R+1m1qyOQ41n6bbzZMPWgseBwUp7CZsW4HqfwvFmFKtCo8JOCNwHqV5uTRIccc4PIwU3R+xrgDvXllhuR+tGwbb6Q4xwCM9YEy+gr5zLbWm2Y5AUEe82cG26m2u0ZkPrrfu8ZrZUnq5Bgi336aUBhaqspHNfztvKF14YTQsKDaNxJu2tPw1uklJsrTKfzdNGcEIzvoPBX2JjcEbGCKNjjfjnNCkdW51E2rhblkj5601cEiB+BwDQRtTr0TD1w2B9ALPJ4iDhJ6wbHAj89Yw2SMogTrbedbt7P2B/6/PN7hGjqyk6VkTEdQx5jHNtROZsCg9wJrb0EphonRFlDOUNwY+n5caBQpqnlA4GQrTnEvw1m3LUSr6XpKT7ivlxA7jgp4Yv9r7C3r/1o8OlvNom03jVU1ntLmxzuWdXmmMb20CIFKFzLv+hMYf8nVDlxbdhy3hUUicjbCXbNYybV6ODpFkx7ZoZICQ9BdS6NDLUU+zv6eY7Ak0E9Xtz68i0ZC/bjJAIdrwVN2PMGH9ysNhCl4bNcvIKWWJKtMgwQIgKWUoi+l3/stzRUYYUsB7S7NUyJUsx0GP+J5fCPzrrBlsADSlmoZIDgAB6oh/atj+0phdrurxnLt3rUZehm4PuXEc6+QtmHLxMTZSwhhhklZzRAY8Oc7jux7PhW/Dw1w5+XKSEhQbpWcdlgEM5QDryiKLGvRmtjLwpRyIIPwScvUcsGWvokmmUj/EFYkDqYzz8YGH7yHjF78L+74CZIsyDEGxj3KJlKEMq5NZTeZsTYjiOOV8J5Wg6hefzEUPnp8FQ6V1oj8h1EPhqLOB/t7PVxDBtNceHszQJ6hlydFtiEQLWfn3bkayVik8Q3yux75Ljj1TOsyaNqpTh1eBPqo5RUUr/CwomHMosiOajrWe91noozV5PgXvYiKB6YMHoV65g3XlIBcAnCrSGXSCsWdJp7qaoBqY8a+QiKxXVW7zj40VMzsJ82FL66SgAiuS5wC46eB2zV2Fc64HzcFGwo4nOEK/qd1LVkYY5MhZBeutwU7H6q4OhuY39y1X2u3L31bQ+QJnrbyXKBe0yd5Nrzy83AnVJxvl7Dmo35If4kDi1Tl/djmYoBfVSbpHXkEK1fJojAll2VoLfo/2OF5zR/V4wBFb2K7MddxYWkBhOkSQEuIKCwmWGw/XUOcgIPY/gO22fYf8zYPx48Jg90Ai2D3u9rkWBzpWKGvrsmK4QwJSIB85oZAaMnkKMbAs47ClDvCSpWWqheCTCOxC/tdnJ5XPT5cR/5L32oiPJ5ftA==

Thanks Sylvain and Sebastein. This was helpful. Enjoyed the talk as well.

Regards,
Himanshu

From: <> on behalf of Sylvain Pion <>
Sent: Thursday, November 19, 2020 4:58 AM
To: <>
Subject: Re: [cgal-discuss] Understanding Exact Computation in CGAL
 
Hi Himanshu,

On this particular subject, here is another « mooc » I made, which you may find of interest :
https://nam12.safelinks.protection.outlook.com/?url="https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D7cz7RNYoWow&amp;data=04%7C01%7Csharma.him%40northeastern.edu%7Cd4c9fa373a384a1d8e9208d88c71aea4%7Ca8eec281aaa34daeac9b9a398b9215e7%7C0%7C0%7C637413767194688820%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=1ewbZ4ImbY1qXALtjKAapPhuOjT%2Fb3Njk93XhzJtE0Q%3D&amp;reserved=0

Regards,
Sylvain

> Le 19 nov. 2020 à 10:06, Sebastien Loriot (GeometryFactory) ( via cgal-discuss Mailing List) <> a écrit :
>
> CGAL relies on an multiprecision number type.
> They are several alternative but the most used is the third party GMP.
> Then, since exact arithmetic is costly, they are several filters applied
> to avoid relying on this multiprecision number type (static filters,
> interval arithmetic, ...).
>
> You can watch the google tech talk starting from here:
>
https://nam12.safelinks.protection.outlook.com/?url="https%3A%2F%2Fyoutu.be%2F3DLfkWWw_Tg%3Ft%3D2310&amp;data=04%7C01%7Csharma.him%40northeastern.edu%7Cd4c9fa373a384a1d8e9208d88c71aea4%7Ca8eec281aaa34daeac9b9a398b9215e7%7C0%7C0%7C637413767194693819%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=kRRbhXFq3Yrb6jMA0V1YuL4Uq2%2BS4Y%2BAHX8BREAGUGw%3D&amp;reserved=0
> to get more details.
>
> Best,
>
> Sebastien.
>
> On 11/19/20 2:48 AM, Himanshu Sharma ( via cgal-discuss Mailing List) wrote:
>> Hi Team,
>> I am trying to understand how CGAL goes about doing exact computation. You have a page
https://nam12.safelinks.protection.outlook.com/?url="https%3A%2F%2Fwww.cgal.org%2Fexact.html&amp;data=04%7C01%7Csharma.him%40northeastern.edu%7Cd4c9fa373a384a1d8e9208d88c71aea4%7Ca8eec281aaa34daeac9b9a398b9215e7%7C0%7C0%7C637413767194693819%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=5r3P0iBxc28QxPYCEsZflffR6wKLXhc5SYjGWyy8c%2F8%3D&amp;reserved=0 where you explain it a bit. I need some clarification.
>> Quoting from the page:
>> In CGAL, we write the high-level algorithms in terms of a well-chosen set of basic questions (where is a point with respect to a line?) and basic objects (like a circle through three points). Doing this in the right way is not always easy, but once it is done, we have outsourced all the numerical issues, and we only have to make sure that the part of CGAL concerned with the basics returns correct results. Given this, the algorithms on top of it just work. Not in most cases, but always!
>> Can you tell me that how do you go about computing answers to set of 'basic questions' ? Are you using a third party library for it or you implement that part yourself ? If you do it yourself, can you guide me to where I can find it in the source code.
>> Regards,
>> Himanshu
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>>
https://nam12.safelinks.protection.outlook.com/?url="https%3A%2F%2Fsympa.inria.fr%2Fsympa%2Finfo%2Fcgal-discuss&amp;data=04%7C01%7Csharma.him%40northeastern.edu%7Cd4c9fa373a384a1d8e9208d88c71aea4%7Ca8eec281aaa34daeac9b9a398b9215e7%7C0%7C0%7C637413767194693819%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=8I68g3ki8NvZfuRAJiaKY9dEUCfZdCvtHC40nCWs858%3D&amp;reserved=0
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
>
https://nam12.safelinks.protection.outlook.com/?url="https%3A%2F%2Fsympa.inria.fr%2Fsympa%2Finfo%2Fcgal-discuss&amp;data=04%7C01%7Csharma.him%40northeastern.edu%7Cd4c9fa373a384a1d8e9208d88c71aea4%7Ca8eec281aaa34daeac9b9a398b9215e7%7C0%7C0%7C637413767194693819%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=8I68g3ki8NvZfuRAJiaKY9dEUCfZdCvtHC40nCWs858%3D&amp;reserved=0
>
>


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://nam12.safelinks.protection.outlook.com/?url="https%3A%2F%2Fsympa.inria.fr%2Fsympa%2Finfo%2Fcgal-discuss&amp;data=04%7C01%7Csharma.him%40northeastern.edu%7Cd4c9fa373a384a1d8e9208d88c71aea4%7Ca8eec281aaa34daeac9b9a398b9215e7%7C0%7C0%7C637413767194693819%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=8I68g3ki8NvZfuRAJiaKY9dEUCfZdCvtHC40nCWs858%3D&amp;reserved=0





Archive powered by MHonArc 2.6.19+.

Top of Page