kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #37054
Re: RTree implementation
-
To:
Seth Hillbrand <seth@xxxxxxxxxxxxx>, KiCad Developers <kicad-developers@xxxxxxxxxxxxxxxxxxx>
-
From:
Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>
-
Date:
Mon, 6 Aug 2018 23:18:08 +0200
-
Authentication-results:
spf=pass (sender IP is 188.184.36.46) smtp.mailfrom=cern.ch; lists.launchpad.net; dkim=none (message not signed) header.d=none;lists.launchpad.net; dmarc=bestguesspass action=none header.from=cern.ch;
-
Autocrypt:
addr=tomasz.wlostowski@xxxxxxx; prefer-encrypt=mutual; keydata= xsFNBFRh3ssBEADmCSrn6qwXrSwI2/LcFSv0aXNHrUQ0MyOAHAW1Rn3LNXLcSCxep1w0iH8q M+ag0XxRVf87DGqjv8wKLGc8nIkGtrMSOuiF+hsrtjAiIrOyOipTABLapqGVj1Dm/26NCtiM /0ZU3XjKcSS5rrj4epKaTM0qW7xp6VceZgH79MbiSCjrt/r9Yhx4tGbWBaCSgTOUHwNB3/Oq 0E5VjU5SAQBQhwG71mES/xaIIUxtfxAPLxpvaq81cjTuT2VQ30T65fSDVikwXrc7M/a2hUG0 nyreo4CktY4pazofQpBA8f8gDPOY1CezY1o1or1Ey6Td/YM/G/Q2G9RZZTjPgD1KRdWIC+nG oCP0lcrMh8Ee+JgR2X7iAAfyVuKAeokxkGnCLon2qiuRG6yAGsEeunJDSd0XtBXzn71GqQH6 0NJzndNoI2PptbHMgc6bINbODkl/RFjVLVGMxDQbgxui2inpjayUZVCQ6SHiiY8BMJrpvTWK GvmgXllxGw+9IQ51u/I0W6hBdy0W/P2oXrP7V2GPDdvyIGJaecjvbkEnD1AbRvxlOjVTGFnC cW08ohzNHGfQK/MXaIpnZAWzRqJz8Wx13KkrdN1hT5quJtaHsvuxBclgHmzbqLlfvLnU7iOa tdN/JzL4L3czEFLJhnHOf9e5zd8yith9vGLUwPxjCzQvz5kBEQARAQABzS1Ub21hc3ogV2xv c3Rvd3NraSA8dG9tYXN6Lndsb3N0b3dza2lAY2Vybi5jaD7CwX4EEwECACgFAlRh3ssCGyMF CQlmAYAGCwkIBwMCBhUIAgkKCwQWAgMBAh4BAheAAAoJEMD02zLS2+sBdxkQAM3Nwk6cU8JT A0uR83NsQEUWjoGboIkVtO5amqWqWGLBguolhEt/NTuzQtmD6rFFhPcOpXDKRKdd6ySdlUB7 8XIgQQTEex6uQpWWV/cLACz6a0u0BONA+VPFzRpWSpOMKpCOcm7izGX9H4CZu4f+bqhL3zaC 38Ki5XxyyioGUzyWd/tw84nz2JgrP1zcYih0Qq82ooO1sRIUrJrm7onb4dH29p7d12uGiQZt go+xeYcDW3TlN4m2tmd7l/JqsD8F0CqtvWrGMsdbr1NE5Y2vyIpG3rkkCiTrlUs0SFyqAC7L qRswP6UZa7enNMhRtJN7eqyrya8J7deRTB6qubP8kTGTt+UTlIgivSqThEN9cJu4cWOsdr3X /D9h7aej1jDSerwKIm7UdmrjkOsgUiZhFMphdAgelmfcVdl7CjsqnnYa5eeeVfEMeT3Fv79V qUcg6LfwUGB56gO4OsnMLGCzCbn6kuwbtlCcV10MsTVzvKNFOrs3mm+yZ2msdLJSV2QMNtHW EVXJV2Tlye+XiYtljdyA6GthK+T/Z9qj8nblunMMN9TwCPkIzzKgyKPxIup/MV7CzN2y8nbp BqkFhApTlXt+NflNdqkfqrWcm+XDXbTwvUzFrKVc8QczpVOMuk7kS+MwxtGGEL6QuML/W8hb k1iEeeAQNiNorHshYTJzGb+lzsFNBFRh3ssBEADQpjP/NdQTZFh11UxsKAOM3KVPSjYxyOEO Gd65/klc3ZBTXJAaC2XmUhYU/kzhyJU7/dd+ywhsLYsWB21mVucAsANra1BkTFXPQFPQwsPP 15QnWQQwFdX7AoMZYceiXqNSWc48DvnXqlUB8TqzB3dSHys9tzfmc+2TDAlM/TpYKWTtY9Fc 2xsx3ZvOzHE1wi6KmdMuK5qc5QBWY16FJtcFA2D5scd24Zy2cO+QS7fDuQHVQpuV+y8unUQC l3VBdOb21WpYrkyUCJU5yRxTP7kbHOIaNyr6S05zArg0TtEfaqCSDOrljxzxSqLtgnD35enE G9/lvQbX8rG0nR1W4ZnhnEx0hAJk2eJ7v9X2Fiq+3rYiEhUsthfBexxoailNxrFIYFr1qBiG zj1HvzoEQZ0Mz/WU156JJBSKAg1IrWzKswIrcv1FoRVhISiEo4nfJslBthZbJjGJ5veYSU5V K4yUNEvcG98+Z4YKFLREXBq6V1AmiFUVbZ1FblK8TGvQaQ3YJlOWEtDA1yrHnujz5wgxtBSM pUsNApQOs2c0MaksfIgkM1McRDwTemup+wmPJ2U8Hvb5A6lI1G+iiUrXPYahdy8XRMxyM1aU xQz53A8Ex+YK/Qn/16k9BZYs/0k3tXb+WBFBcsq732oCo6n4hbfCoG4gYDn7jlEhnm/aQ1Vr eQARAQABwsFlBBgBAgAPBQJUYd7LAhsMBQkJZgGAAAoJEMD02zLS2+sB6kgQAM4V4jIUJo98 rbCU0Yy8YLahwQK5TynS8+zsQ/s9q+aYT8qWzdcjavfRKA3VArGP8qYBXRIQW7QbceSChTOG hhai+5nIJbWhGXVfEUtZ2txahcY2ecfsDEkvCOK7pLKsCq7eYQzMHV8ZPwGWPq+hZa+6msHh R2yUHo6NV2u2HjVJROaM2nUSZT6hOMhzp+zYwl1XEZKqo+QxDtLWJQ66MZIOAngyWN9/ePUJ 0dxG6V+r9MjgHS/OtVlgCKtvAYJCRGcGiSaL+wjhiaZ1/nwBAL0mwN2UaoP+oYjI09J5/Mff tbtQQHMQwRxy31b6N1ZFunnVkR0MeBlT8JtUI31zroRoQ/4u0+wXTYaeTANa0R73Y/m8aIhE sj2ZDD6NISA0Yxnm1rXUyJZosrcS5WjrpgjAjQvkFpm7Sx8Sx+QWpS+DcL8rJntzwL9cPHPA 3tutTbZ9vQrH20TT8Z4nFzTvytFKb5bydF92Fawph2NjFcwzMi/6i37tS1q1X93ky10vq2M4 MaTxIwyjENy6GT5mPh2YlKhWHN5K+8K7rf6QBsvud+SdN3T1AEJojZEYIvxXi0MMpfB4iqlu z+oUbkdDqZonG9QZIME1/BJ3y5oVp5h1r6+vs58a5p/lHjurNYMgbNmWUAcW3trFwXWJispd DhAcLoHO+yCvkKJabrfOZoa2
-
In-reply-to:
<CALHbTmYGvN60mQS3geNdiJtgKnoK+nGWfrRFzg4c=xnHVUsuTQ@mail.gmail.com>
-
Openpgp:
preference=signencrypt
-
Spamdiagnosticmetadata:
NSPM
-
Spamdiagnosticoutput:
1:99
-
User-agent:
Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1
On 06/08/18 18:35, Seth Hillbrand wrote:
>
> There's another 32-bit RTree issue that is showing its face
> (https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=905221). The last
> one (https://bugs.launchpad.net/kicad/+bug/1774316), we hacked around
> for v5 but as this seems to be a recurring theme, I'd like to address it
> with some finality.
>
> We could maintain the RTree implementation ourselves with updates to
> correct these errors.
> Or, we could use the Boost-based implementation
> (https://www.boost.org/doc/libs/1_67_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html).
>
> I have a basic framework for shifting to the Boost-based
> implementation. In tests, I don't see a speed difference in running.
> Compiling might be modestly slower.
Hi Seth,
I would be careful with anything related to geometry in Boost. Good
things from Boost sooner or later end up in the standard C++ library
(e.g. unordered). We had a lot of trouble in the past with crashes in
boost::polygon that nobody could debug or even understand because of the
vast complexity of Boost code. We struggled for few months to replace it
with Clipper, since then, we've seen no crashes in polygon boolean ops.
If the solution to fix the current R-tree to work on 32-bit platforms is
to use doubles instead of floats, why not try it out? By changing to
boost::geometry, we'll likely have to report bugs there. I'm also quite
surprised this bug surfaced on one particular OS (Debian) 5 years after
this R-tree implementation had been introduced to pcbnew. Does anyone
here know why it crashes on Debian and not on other 32-bit systems?
Tom
Follow ups
References