Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Minimum ellipse and 2D convex hull

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Minimum ellipse and 2D convex hull


Chronological Thread 
  • From: Andreas Fabri <>
  • To:
  • Cc: Gärtner Bernd <>
  • Subject: Re: [cgal-discuss] Minimum ellipse and 2D convex hull
  • Date: Mon, 2 May 2022 12:49:50 +0200
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-data: A9a23:zVxqsqp9Y4Fp/BHiI0lOtzwd1C1eBmJcYBIvgKrLsJaIsI4StFCzt garIBmDOvqCa2X3KY92PY2yp0kGu5/RyIVjGgc6rC0yRiNBpOPIVI+TRqvSF3PLf5ebFCqLz O1HN4KedJhsJpP4jk3wWlQ0hSAkjclkfpKlVKicfHoZqTZMEE/Nszo68wICqtMu0IHR7z+l4 4uo+ZWCYAb9gVaYD0pNg069gEM31BjNkGhA1rAOTagjUIj2yhH5pLpGTU2AByOQrrt8RoZWd M6fpF2NxV41yj92Yj+TfhkXRWVRKlLaFVDmZnO7wMFOiDAazsA5+v5T2Pbx9S67hh3R9+2dx umhurSXbCEsN5PCl94FWhYBSABVbfYW0Zn+dC3XXcy7lyUqclO1n7NrCxxmZssd8+dzRGZT6 bofNjBLaB2f7w606OvrGq812JllcZCtbNl3VnJIlVk1Cd4vR5zZTqzRo9FR1i0xrs9DGvPTe 9AIZzNkcBPacltEPVJ/5JcWx7vy2yOkImwwRFS9mfc242zq0ApI+4PmaNbYWuTWZZR1kRPNz o7B1z6hWkxLXDCF8hKO/Xuow+POhijmQ5k6D6y97vcsgVuJx2VVBgd+aLegiaDlzEu5BoIEb Ukd+y5rqrUusku1Tp/7UgHQTGO4UgA0fP92FuQE5g630qPbul24LThfHhdnUYlz3CMpfgAC2 liMltLvIDVgtryJVH6Qnot4SxvuYkD5ykdePkc5oRs5D8rL/NFi0EKUJjp3OPTu1oavcd3l6 2nS9HBWulkFsSIc/4uBlbwtqx+qqZjIQwhw4gjMG0is7wViDGJOT931uQiDhRqsBC1/SlTEs HVBtdKX6usDZaxheQTUHKMIG+z5vLCAOTzYxFlyA98m6TTr/XO/FWyx3N2cDBkzWirnUWWxC KM2he+3zMUDVJdNRfQoC79d8+xwkcDd+S3ND5g4lOZmbJlrbxOg9ypzf0OW1G2FuBFyzPhlZ srLKpb8VCxy5UFbINyeF711PVgDlnpW+I8vbcGkkUjPPUe2PyHIFedbajNikMhgs/nY/V+9H ylj2zuikU0HDbyWjtj/9pATZUsDNhAG6WPe+6Rqmhq4ClM+QgkJUqePqZt4ItwNt/kLyo/go y/sMmcFmAuXrSCWcm2iNyEzAJuxB8oXhSxgZ0QEYw33s0XPlK70sc/zgbNsIeJ4nAGipNYoJ 8Q4lzKoX6ofF2ybq2hMBXQ/xaQ7HCmWacu1F3LNSFACk1RIHmQlI/foIVni8jcgFC2yuZdsq rGszFqKE5UOQAFvENzHZvuk01SrrD4Wn+crBxnEJdxaeUPN9ol2Kn2g0qFoeJtceRiTlCGH0 wu2AAsDobWfqYEC79SU17uPqJ2kErUiExMCTXXb97u/KQLT4nGnnd1bSO+NcD2EDDH09ayua P971fb5NPFbzl9Gv5AlQuRkwKU76sf1trFTxRhjBmSNZFOuU+syLn6D1MhJl6tM2r4I6FfoB RnVqolXYOzbNtnkHVgdIBseQt6CjfxEyCPP6fkVIVnh4HMl9rSwTkgPbQKHjzZQLeUpPdp9k /shosMf9ye2lgEuboSdlilR+mmBci4AXqEgus1ICYPnkFB2mAgeJ5nbV3+tppSGatEJNVQ2Z DiKhOzEiqgFnhjOdH86FH7s2+tBhMRf50oVnANaf1nZyMDYgvIX3QFK9WplRApiziJBj7B5N F9tOhAnPq6J5Tpp2JNOUjz+AQ1HHxHFqEX9x0FTyT+AEw+tUTGddys4MOeJuUcE7yRbYDgd+ ryEkT63XTHvdcD3/y0zRU81+qO5EowtrlXPyJK9AsCIP5gmej670KWgUmo/rUe1C80GgkCa9 /Jh+/x9aPGgOCMdy0Hh51J2CVjEpNG4yG1+rTVJpf9PGGaBKGr03DGPLwW2Z98LIOLKt0m1F 6SC4y6JuwuWjE6zQvIzXMbg4IOYWNYm6d0Hd6/xNGAPuKeYtCsvu5XVnsQ7rHF+WM1gyK7RN auIHw9v0QWsab98lGLKqcRYIHu2aNIYYxftmuuy9Y3l0n7FXP5EKSkP71d/g5lZ3MaLMf5ZU MMvqpI6F9Bf9Lk=
  • Ironport-hdrordr: A9a23:VQJcM6rED36znxOHB1yfaucaV5qxeYIsimQD101hICG9Evb0qy lhpoV86faGskd1ZJhAo7+90ca7IE80maQFmLX5eI3SJDUO21HJEGgB1+XfKlTbckWUnNK1l5 0QFJSWY+eAb2SS4/yKhDVQX+xQo+WvweSPuuab5XJsQQZ2S7gI1WtEIzfeNFJ2ADRcDZA0D9 6966N81kGdUEVSUf/+PEAse8Lqm+fm/aiWHSIuNloZ0021tBuN0pTdKDTw5GZibxp/hYgYtV L9uyjC242fn5iAu2Xh61M=
  • Ironport-phdr: A9a23:gi81CRe76LSyE1nb01L6pNytlGM+XNfLVj580XLHo4xHfqnrxZn+J kuXvawr0AWSG9+GoKkcw6qO6ua8AzZGuc7A+Fk5M7V0HycfjssXmwFySOWkMmbcaMDQUiohA c5ZX0Vk9XzoeWJcGcL5ekGA6ibqtW1aFRrwLxd6KfroEYDOkcu3y/qy+5rOaAlUmTaxe7x/I Au4oAnLqMUbgYRuJ6gtxhDUpndEZ/layXlnKF6NgRrw/Nu88IJm/y9Np/8v6slMXLngca8lV 7JYFjMmM2405M3vqxbOSBaE62UfXGsLjBdGGhDJ4x7mUJj/tCv6rfd91zKBPcLqV7A0WC+t4 LltRRT1lSoILT858GXQisxtkKJWpQ+qqhJjz4LIZoyeKfxzdb7fc9wHX2pMRtpeWS9PDIyzY YQBEvQPPehYoYb/vFYBtweyCBO2Ce/zxDJFhHn71rA63eQ7FgHG2RQtEs4IsHvJttX6Kr0dU fuox6fI1zrMdOlW2Tbg44XPaB8hp+yDXahufsXL0kkjDQ3FgU+Lpoz/PjOYzesNvHac7+plS +2vl3QnqgF/oje12sgslo7JhpgVy1ze6Sp5x4M1KMS+RUVmbtGqDIFeuDuGN4tqXMwiWWdot T40xLEbu5O2czQHxZooyRPeaPGKfYiF7xHgWeufITl0mXJodbC/ihux7USs1OLyW8ap3FtXo CRLnd3Bu38D2hHd7MWMV/Vz/kCk2TmV1gDT7PlJIUEylarBKp4u2KQ8lpQJsUnFAyT4m132g beLekgn+eWk8fnrb7Tmq5OGN4J4lxvyP6cwlsCnBek0LhICUmuB9eii2rDv4Vf1TKhEg/A2l KTSrYrUKt4BpqGjBg9YyoYj5Ai7DzehyNkUgHYKIEhAeBKAj4XkOF/DLOr9DfilglSslC5nx /fbPr39GJnNKWbDkLf7cbZ79UFc1BI/zdFZ551KFrEMOO//V0zyudDCExM0Mgy5z/znBdlgz I8TWnyDDrecMKzIsF+I4uwvI/OLZI8QoDvyMf4l6OP0jXAng1AdZrOl3ZUNZ3+jBPRmIl6UY XXyjdcGFGcFoBY+TPbqiV2MSzFce2qyX6Um5jA7Eo6pEYDDRoW1jLyHxyi0BodWaXxeClCQD XfocJ2JV+oUZCKIPsBhiiAEVaSmS4I5yR6uuxX1y75+IuXJ+y0Yro7s1MVu5+3Ijhwy7jx1D 8GF026XVW10n2UIRyU33K9lu0B9xE2DguBFhedFH4lT++9RSVV9coXNyvRzTdH0QAPIONmTD 023R82vRjA3QNV2yNAHZwNxGs6pkwvYjBesGKIft6COAMk07r7ExCq2YN1szm7PkqgnlVgvB MVVcna3g7Z2sAnVCYmOmEqQk+OmdL8XwTXWp1qF1neEgExITFtwTbndRiJYIVDHqMzwoELEV b6nT7o9dRBQzNaLbapMZNquhlpPQLLvOc/VfnmqyFu3UB2Hz7fJYIvxcHgGxw3cDlIFmkYd5 yWoLw87Uw6nr3jTBScmO1vleUKkpeB4pGm2R1RywQiAdUxJ2Ley/xMJn+2SQvgP2agV/iwmr mMnTx6Gw9vKBo/Y9EJad6JGbIZliL8m/WfQtggne4elM7gnnFkVNQJ+o0Lp0RxzTIRGi8kj6 n0wn0JpMazN9lRHenuD2IzofKXNIzz7+hy1ZqfNnF/X2syX0qgC7/E1t0/ysgiiCk044jNs1 NwGm2CE6MDyBREJGYn0Tl5x8hF7o7/AZSxo7oXYz3BlKu+6uzXY2vomCewgxwq6btlWO7+DD h60GMofVIC1MOJ/vV+vY1ofOfxKsq45O8Tzb/ydxKuiJ/pthhr/0SJC590tiQSJ/it4D+nVw 9AC3fHe2AabP9vlpHGmtM2/2YVNZDVIW3G61TChHolaIKt7YYcMD26qZcyx3NR3wZD3CTZe8 xa4ClUK1dXMG1LaZkHh3QBWyUUcoGC20Sq+wTtuljg1r62ZlCXQyuXmfRADNyZFXm5nxVvrJ IG1iZgdUi3KJ0Agkhe/6E/hgaZSrr5+B2beRkJFYzLnIWhpTqyqp/yJZMsOoJIkvCNLUfitN EiAQ+2YwVNS2CfiEm1CgTEjImj66tOgwUE81TvbfCwgyRiRMdt9zhre+tHGEPtY3z5cATJ9l SGSHF+3ed+g4dSTkZ7H9OG4TWOoEJNJIkyJhcuNsjW24WpyDFixhfe2z5fuFwQg3CbgkddjX z/JhBnxZYzmy76rP+tsYk5yFRn37M8wSeQc2sMgwYod33QXnMDf9HwLi2r6KpNV0KjkbVICS DkOzsLP8Qbs01FkNGPPzIX8HCb4oIMpd5yxZWUY3Tg45sZBBfKP7bBKqiByp0KxsQPbZfUVc i418fI18zZahugIvFBo1SCBGvUIGkIeOyXwlhOO5tT4raNNZW/pf6LinEZ5mNmgCvmFrGQ+E D7wfJs4ECZrqMt2OkjN+HL+7YTpZMPBY9sYqhqOglHLiO0dJJ8ql/UMjDZqIiqk7S1jkrBmy 0E3m8Hg9IGcTgcltLq0GBtZKiH4a4sI9zfhgLwf1sea0oazH4lwTzACXZ/mV/WtQ3oZsfXqM RrLESVp8yfLX+OBQEnCsQE29SGqcdjjLXycKXgHwM83QRCcIBYamwUIRHAgmZV/EAm2xcvne UM/5zYL51e+pAEfr4AgfxT5TGrbox+lLzkuT53KZhNQ4htP7lyTP8WU9ONbECxf+5C9th2DI 2eHYB5ZS2oOXwbXYjKrdqnr/tTG/+WCU6C3KffUbLyV7+JXXe2J7Z2i1Y5r4yydOMyEIn54H rsw3U8JDhUbU4zJ3j4ITSIQjSfEacWW8Qy99iNApce66P33WQjr6NjHG/5IPN5o4RzznbabO rvamnNiMTgBnMBppzeA2P0F0VUVkS0razS9DeFKq3vWVKyJ0rdLFUweYiJ3ccxV8+Q7wAkLP 8PHwsvpzOx9h/8xTVBbVRrnl93MB4RCInnhZgOBXx3Nbe/ZY2STnoasO+u9UeEC1bQO8Uzh/ 2nEVR+6eW/Z327gUxTlWQ1VpAecOhEW+IS0cxI3THPmUMqjcBqwdtl+kTwxx7QwwHLML28Vd zZmIQtLqfWL4CVUj+8aeSQJ52d5LeSChyeS7vXJYpcQv/xxBy1oluVcqH0kwrpR5StASbR7g izX5tJpplinlKGIxF8FGFJWrS1XgYuQoUh4EfyFsJxHBCafuhcE7GHVDAkW4dx7CpvptrwRg tnDmaTvKStTptLZ+cxPYqqcYMmDMXcnLV/oAGuNXFtDFGD2czyGwRwHw5TwvjWPo5M3q4bhg s8LQ75fDhkuE+8CT15iF5oEKYt2WTUtlfiaitQJ7Dywtkq0Jo0Ss5bZW/aVGfiqJiyeiOwOb h0E277xNsIdP4fh2mRtZ15/kZjQCkTZVsxKuDwnZQgx6hYokjA2Xigo1kTpZxn4qmcUDuKxl wUqhxFWOLhr8TCxswxxI1PLoG43jVV3nsvlxzacbHSiScX4FZETAC3yuU8rN5r9SAsgdgy+k 3tvMzLcTq5Qhb9tHYiEoADRvp5CBeRNQ6RPfBgK1LecYPB6iDy0Sw3+mQlC4raVUt1nnQouN JmxszRHxQIlatMpd/S4zE9hwVVXg6+SpD6m3+stxxUPYU0K9THKEBM=
  • Ironport-sdr: V5NUa6RP6umy+0wmrofj9z5Rj0KxGTwS1aK0rg2tEZoT9dH42IdzG5fRGOTS6L3Ksf4E2ho7Ur Zi6iwlFZMNBWTEsW1YnumClH1o5X8BNRilDt/axVCdTc5nfZf6o1wzl7g5+jxwl+1kYowadmtL r/9kRU8bF0nY+1qU1faRlVchCSx+jUW8FWNyl7H8ZAIasT9qzd8jA4wU8W1mOCVQUnQAqaCVk4 Ir8Gu3sDb4NHLxd2wRv1V9cdS7ZlmdihzsFH01PK7iqrP6RAAUkvEf5wvjnRM5GQS/OmwOPgiV sdQlRo/BouZU7DOR1Qd8HYfD

Hello,


It seems correct to me that a point which is inside the convex hull of a point set can not be on the smallest enclosing ellipse.

We maybe should even write that in the manual.


Best,

Andreas



On 4/30/2022 10:53 PM, "Scriven, David" ( via cgal-discuss Mailing List) wrote:

I have to fit a minimum ellipse to a a series of 2D point clouds. When the number of points is large (1000's) this is very slow but I noticed that a convex hull either lies on or is contained within the minimum ellipse. I fitted the convex hull first and then fed those points (usually less than 15) to the minimum ellipse - this is extremely fast.  As far as I can tell the results are identical to those from fitting the entire point cloud. While this makes intuitive sense - interior points should not affect fitting the perimeter - I was wondering whether this approach is valid and whether there was something that I had missed. 


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

-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project


  • Re: [cgal-discuss] Minimum ellipse and 2D convex hull, Andreas Fabri, 05/02/2022

Archive powered by MHonArc 2.6.19+.

Top of Page