Subject: CGAL users discussion list
List archive
- From: Bob Bill <>
- To: "" <>
- Subject: Re: [cgal-discuss] Compute radius of inscribed circle of a polygon
- Date: Mon, 18 Dec 2023 15:03:08 +0000 (UTC)
- Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
- Ironport-data: A9a23:MW1kA69QYrS13CzFGu+HDrUDE3uTJUtcMsCJ2f8bNWPcYEJGY0x3m mEWX23UPP3YYWv2fNslaYWx9U4CusLVnNRkSgo6/CFEQiMRo6IpJ/zJdxaqZ3v6wu7rFR88s Z1GMrEsCOhuExcwcz/0auCJQUFUjP3OHPymYAL9EngZbRd+Tys8gg5Ulec8g4p56fC0GArlV ena+qUzA3f7nWYoWo4ow/jb8kg25q2i4GpwUmEWPJingneOzxH5M7pEfcldH1OgKqFIE+izQ fr0zb3R1gs1KD9wYj8Nuu+TnnwiGtY+DyDW4pZlc/TKbix5m8AH+v1T2Mzwxqtgo27hc9hZk L2hvHErIOsjFvWkdO81C3G0H8ziVEHvFXCuzXWX6KSuI0P6n3TEkqstUH49P6wi9etWX1BOr qwqeW8cR0XW7w626OrTpuhEncMlLcKwZNha4CkmxjbfFvM8B5XKQqGM5MUCmiY5hsdJW/3ZY qL1axIwM1KaOE0JYwhHTshmxY9EhVGnG9FcgFiUoa49vjSN5B140L/qdtHSf7RmQO0MwhzJ/ TucrjWR7hcyEtKUwwDVzn+Qo+qQlgGqXp85TKyW+as/6LGU7ilJYPEMbnOwrvC9z0K/QNlCM Fc84TsrtaF09UqxT9C7UQfQnZKflgUbXdtbSLVhrVvVjKHT5R2cHC4BRz9FLt087oknTDwt0 RmCmNaB6SFTjYB5gEm1rt+8xQ5e8wBPRYPbTXZcEFtX0Mqpu4wpkBPEQ/BqFaP/3JW/Gij9z 3rO5GIyjqkax5xDnaiq30H1sxT1rLjwTykx+lr2WECh5VhHf4KLXdGjxmXayvdiF7ynaGe9k kIKoOWgydwfLIqskXWNSdodHbvy6PeiNibdsGFVHJIg1mqM/Vi9d4VU4hRsDVVNDucbXTrPf kXVnx9a5cJPDUSudotyZ5OUCpl3/JfgC970C/LeNIJPRrNTdwa32j5kSmDN/mLqkWkqyboeP 7XCe+mSLH8qM4ZV5xvoePU8iJgA2TIb6V7IYILSlzCL8Oa7dWGEb7UoK36MZb0J17yFqwDr7 NpvDcuG5BFBWunYYCOM04osAX0VDHo8F7bkgtd2c7OdHw9YB20RMf/d7rc/cYhDna4OtOPp/ Gm4a3BI2mjEmnzLBgWbWE9NMIq1c85Ekks6GigwMXKD+XspO9+v5ZhCUaoHR+As8eg7wMNkS /UARd67Pc1ObTb64BUYU4j2qd1zVRashD/WBRGfXhoEQ8dCSTDKq/jeRSm+0AkVDyGyi9kyn K346CPfXqg4ZlpDCOT4VauR6m2f7FkntsB8ZU/qGuVoWV7N9dFqIhPhj/VsLMArLw7C9wSg1 A2XIEk5o+3NqqBk7v3Mo76OlKayMu5EBkEBNXLq3bW3Eij7/2SY3o5LVtiTTw3dTG/Z/KaDZ /1f6vPBbNkruUlsiJVtNJpO1oc81svLi54B6To8B1TNTVCgKo04E0m8xcMV65F8nO5IizW5S mek24d/K76WHOjHDVRIBg4uTtrb5MEugjOIsMgEehTr1hRWooiCf15ZZSSXqSpnK7BwDoMp7 MEhtOMS6C29khAaCcmHvA8F61WzKmE8bIt/uqE4GIPLji8Z+mNGa7HYCQ7058irQPdIOU8IP DSVpfTjg5Jx+0n8SEcwREP9hbdluZczuR5x3AAjIXaNkYH7nfMZ5kBa3gk2aQV39S959dxPF FJlDXAoGpXWzQxU3JBCe0uOBzB+AAao/x2t6lkRy0zcYUqadk3MC2wfZNey/F4T4j9edGID/ ZWz6mXsYRD1du7fgwowXk9EraT4bNpTrwftpuGuL/6nLbIbPwX3o/aJTnUajjfaGuYzi1/ji cgw2d1veIvpMSI0iI8qObmwjLg/ZkiNGz1ffKtH4qgMI1D5RBiz/jqrcGWaZcJHIq3xw3+SU sBBCJpGaEWj6XyosDseOK8rJo10lt4P4P4pWOviBUwCgoulggtZirDi3QmguzZzWPRrq9g3F a3JfTHbEmCwu2pdq1WQkOZ6YFiHcfs2Tyyi+tuq8dc5NYMJ68BtVkAQ7oGanVuoNClfwhbFm z+bOoH3ybVux705ysGoWu9GCh6vINz+aPWQ/Urh+55SZNfIKoHVuxlTtlDjOB9MMKAMX8hs0 46Aq8PzwFiPqYNev7o1QHVdP/UhCQSOsOtr3gbfN35cnCDZAJSpuUNF8Ge+MplT1tZU583hR hHiLtq5ddkSHdxawRW5rsSY/wk1U8zKgmXI/EtRbMhgzjAM2AzAK5Ws8nqBgaRzaHoTI5OnY uPrk6/G2z2bxbigwDcVDvFhBNlzJ1qLtW7KsTHunWHwM1RESW9udlcvedTMJN0L5rS5/B7G3 K/4
- Ironport-hdrordr: A9a23:Ob2e4KgQtvwi0dJXX65G1i/MxHBQXiMji2hC6mlwRA09T+Wzkc eykPMHkTr5jzgNWRgb6Ku90ci7MArhHPtOirX5Uo3CYOCLgguVxcRZnO7fKl7bakvDH4xmpM VdmsFFYbWfMbE5t7ef3ODSKadG/DDoytHKuQ6n9QYUcShaL5tHyCdSTiu4MmkzfilpIvMCfq a01458oT2hczA2Q62AaUUtbqz4odrKntbDTnc9ayLOvGG14A+V1A==
- Ironport-phdr: A9a23:ZAMqQhD6XvnVB4IuR2IfUyQU+0gY04WdBeb1wqQuh78GSKm/5ZOqZ BWZua89ygWRDc6Fu7ptsKn/jePJYS863d65qncMcZhBBVcuqP49uEgeOvODElDxN/XwbiY3T 4xoXV5h+GynYwAOQJ6tL1LdrWev4jEMBx7xKRR6JvjvGo7Vks+7y/2+94fcbglWhzexe61+I Am1oAnet8QbgpZpJ7osxBfOvnZHdONayH9yK16Ugxjy+Nq78oR58yRXtfIh9spAXrv/cq8lU 7FWDykoPn4s6sHzuhbNUQWA5n0HUmULiRVIGBTK7Av7XpjqrCT3sPd21TSAMs33SbA0Ximi7 7tuRRT1hioLKyI1/WfKgcF2kalVog+upwZnzoDaYI+bKvlwcaHTfd0HSmVOQsFfWjdbDY+gd IQAFPAMMfpaooT7ulAArQG+BQ6pBO731zJIgWT51rAn3uQgFQHG2BErEtUVv3TVqNX1MLwdX OC6waTJ1jjCb+lZ2Tf66IjPaBwuvfaMXbdpfMfX1EIgGB/LgE+Kpoz5IzOayP4Ns26D4uduS e6jlm4pph9vrjah28ohhJfFi5wJxl7K+yt0zok4KNm2RUJmfNOoDpVeuiGbOodoXs4uXX9kt TomxrAHpZK2ejUBxpc/xxPHafGKcZKE7gztWeuSOzt0mXBodbGlixqs7USs1+vxXdSq3VZOs ypFicXMuW4X1xLO68iGS+Vy81+91TuJygvd8PtLIVoumqreM5MhwqA/lp4UsUnbBS/2n0P2j K6KeUgq5uSl5f3rbqv6qpOGK4B0jQf+Mr8rmsylG+g4NxIBX2mf+eim1b3j51P1TK9Kj/Isk qnZt5faKd4Hqa6+Bg9Zyocj6xChADe6yNkVn3sKIEhbdB+JjIXlIUzCLfL7APulnVigjCpny +jDPrL7A5XNKnbDkK3mfbZ480NT0wszzdRb551PCrwML/P+V1TxtdPCDh85NAu0z/z7B9V60 4MSQWSPDbSBP6PIrVCI/v4vI/WLZIINpTrxM+Il6OL2jX8lhV8derGk0ocYaH+iGvRqOliWY Xv3gtgdDGcKpRE+QffxiFyCVD5Tf2y9U7g95jE9EoKmDJ3MSpqjgLybj2+HGcgcbW9PDhWAE Gzjap6fc/YKciObZMF72HRQXreoT8ot1AqlqRTh47thNOvdvCMC48HNzt9wssfUn1kY9DhwR 5CX0mWJRTwowEsZTj8x2+Z0pkkrmQTL6rRxn/ENTY8b3PhOSApvbfY0rsR/AtH2AEfae8uRD UyhSZOgCC0wSdQ4x5kPZVx8EpOslEOLxDKkVpkSkbHDH5ko6uTExXGkLcd5z3ybiPcJnlAmR cwJPmqj1eZk7waGP4fSiA2CkrqyM6EV3SrD7mCGmGCPuEVSDVIuebTMXXcYIEDRqIex/VvMG pmpD7lvKQ5d0YiCJ69NP8XulklDTez/Nc72eGW3mmzrXU3NnOvKZ43sYGAHmiDUCUxCkhpJu 2ePNQ85QCympgoyFRRIElTiKwPp+Oh68jagS1MsihuNZAtn3qa0/RgcgbqdTekS1/QKonVpr TI8B1u709/MbrjI7wN8YKVRZ88861ZbxCrYsQJ6JJmpM6FlgBYXbQ12u0rk0xg/BJ9HlIAmq 3YjzQw6Lqz9shsJfTKc2ZqtZuP/O2Dy+xfpYKnTmxnf3NuQ5qYT+aEgsVyw9AqtF0ck7zBmy 4wKjD3GvcWMVVVCF8ipCxVSlVAyvbzRbygj6pmB0HRtNfPxqTrew5czA+BjzB+8ftBZOafCF QnoEsRcCdL9TY5i01WvcB8AO/hfsaAuOMbzPfGH3KqhYbo+tCOvjWNApot61wjfkkg0Av6Nx JsDz/yCi0GNVjP4hgr97OjmkIBDYncZGW/1mmD0QYVWYKN1Z4MCD2yjdta2yttJjJnoQ3dE9 VSnCjvqweeRcAGJJxz41AxUjwEMpGC/3DG/xHpymi0oqayW2GrPxf7jfVwJIDwDSG5nhFbqa Y+66rJSFEKpawwjyUf7zVfzx69c4q94KiHfTFxJcC7/M2x5GvTv8ODZM4gWt8Nu630OGO2nK UiXULv8vwcX30aBVyNFyTY3eivr8pT1khpmiX6MeXN6rX7XY8Z1ll/U4N3RQ+IU3yJTG3Y+0 2KHQAHjb5/zpYzH8vWL+vqzXG+gSJBJJCzizIfa8TC++XUvGxq02fa6htzgFwE+ly79zdhjE yvS/3OeKsHm0bq3NeV/cwxmHlj5voBwG4V6mNZs2rkB0HgdgdOe+n9NwgKReZ1LnLnzanYAX 2tByd/R5AK4hBNLP3uJwIW/XXKYiJgpd5yxZWUY3Tg45sZBBfKP7bBKqiByp0KxsQPbZfUu+ 1VVgetr8nMRhPsF/RY81ijISK5HBlFWZGa/3wTN9d21q79bIXqiYaTlnlQrhsivVfmavhsOS X/5fZBkFih1i6c3eErQyi/i44Hjf5/WYM5b4RSQl12oY/F9DpU3m7JKgCNmPTi4png506shi hco25imvY+BImEr/aSjAxceOCenL8UUsirgi6pThKP0l8imA4lhFzMXXZDpUePgETQcsu7iP hqPFzt0o2mSGL7WFwuSoEl8qHeHH5euPnCRbH4XqLcqDAGaP1BaiRsIUS8ShZk/FwvxnJekK h8/7TcX/Vvi7B5Fy+YuNgOlFHbWpACvLDwzTdn6TlIe7w1P4VvULd3L7u93GHIQ9ZmgoQqRb 22DMlsXSztSCgrdWAClZOH3tryiu6CCC+GzLuXDe+CLoO1aDbKTwI63l5Fh9HCKP9mOOX9rC 7s63FBCVDZ3AZe8+X1HRioJmibKd8Peqg27/3g9pMG79P62BFzH9IKPDLwUOtJqsUPT4+/LJ 6uLiSB1JCwNnIsL3mPNwaMD0UQ6kCZodjL2Se9F73aLR6XWgapNSRsSaic1NdESqbM13g5Kf 8Xcj5mms9wwxu5wAFBDW1v7n8ivbsFfOGCxOmTMA0OTPaiHLznGqykYSbK1SbpXyu5Tsk/p0 d5+O17qPjOE0TLuUkL3WQmtpDqcOh1V49nmN0w1T2PkSsnjcFu+Od5zyzwsm/slj3PNMigXN j0uKytw
- Ironport-sdr: 65805f3b_Lag8OMXtaikBGfoZhlXdkdf2G+GzuxzLLgwqTh5rURfy2cJ Ywls9b1Zq1CKkaZld+7u1/OL7Ytu0rAa18GEDpw==
Dear all,
sorry for writing again, but unfortunately I am still stuck on this topic. I am following the procedure written in the previous email to compute the radius of the inscribed circle.
- Compute Voronoi diagram of the edges, call it V.- Find the node of V with the maximum distance to edges in P. Such a node is the centre of the maximum inscribed circle (and this maximum distance should be the radius I am looking for).
If the procedure is correct, I am stuck while computing the point-edge distance. I am providing next a MWE where I compute the Voronoi diagram of the edges of the unit square.
Could you tell me how to extract the endpoints of the edge and hence compute the point-edge distance? I am not able to extract and compute this information.
#include <CGAL/Simple_cartesian.h>
#include <cassert>
#include <fstream>
#include <iostream>
typedef CGAL::Simple_cartesian<double> K;
#include <CGAL/Segment_Delaunay_graph_2.h>
#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
typedef CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<K>
Gt;
typedef CGAL::Segment_Delaunay_graph_2<Gt> SDG2;
int main() {
std::vector<std::pair<Gt::Point_2, Gt::Point_2>> segments;
std::pair<Gt::Point_2, Gt::Point_2> segm0({0, 0}, {1, 0});
std::pair<Gt::Point_2, Gt::Point_2> segm1({1, 0}, {1, 1});
std::pair<Gt::Point_2, Gt::Point_2> segm2({1, 1}, {0, 1});
std::pair<Gt::Point_2, Gt::Point_2> segm3({1, 1}, {0, 0});
segments.push_back(segm0);
segments.push_back(segm1);
segments.push_back(segm2);
segments.push_back(segm3);
SDG2 sdg;
std::size_t n_segments =
sdg.insert_segments(segments.begin(), segments.end());
assert(sdg.is_valid(true, 1));
// Loop over all finite vertices of the diagram
for (auto it_p = sdg.finite_vertices_begin();
it_p != sdg.finite_vertices_end(); ++it_p) {
// Loop over all finite edges
for (auto it_edge = sdg.finite_edges_begin();
it_edge != sdg.finite_edges_end(); ++it_edge) {
// get endpoints of the edge
// compute distance point-edge
}
}
return 0;
}
Best,
Bob
Il venerdì 15 dicembre 2023 alle ore 18:55:05 CET, Bob Bill <> ha scritto:
Thanks for your answers. I am actually interested in the radius, not just the center.
So, given with a polygon P, the practical steps would be:
- Compute Voronoi diagram of the edges, call it V.
- Find the node of V with the maximum distance to edges in P. Such a node is the centre of the maximum inscribed circle (and this maximum distance should be the radius I am looking for).
Is that correct?
Best,
Bob
Il venerdì 15 dicembre 2023 alle ore 11:59:39 CET, Bob Bill <> ha scritto:
Hi everybody,
Given a general polygonal shape, I need to compute **the radius** of the inscribed circle. I've searched a while in the documentation but I didn't find a way to do that. Is there a way to compute it?
Best regards,
Bob
- [cgal-discuss] Compute radius of inscribed circle of a polygon, Bob Bill, 12/15/2023
- Re: [cgal-discuss] Compute radius of inscribed circle of a polygon, Andreas Fabri, 12/15/2023
- Re: [cgal-discuss] Compute radius of inscribed circle of a polygon, Claus Volko, 12/15/2023
- Re: [cgal-discuss] Compute radius of inscribed circle of a polygon, Bob Bill, 12/15/2023
- Re: [cgal-discuss] Compute radius of inscribed circle of a polygon, Bob Bill, 12/18/2023
- Re: [cgal-discuss] Compute radius of inscribed circle of a polygon, Andreas Fabri, 12/15/2023
Archive powered by MHonArc 2.6.19+.