X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
X-Original-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s2048; t=1452140226; bh=YzStYdv1++Ea0dnQ3g6NCSk0gI3cNyQGuWTxrbPLR/E=; h=Subject:From:In-Reply-To:Date:References:To:From:Subject; b=uWQK4onW0YMkcGS1BpWNcoDWBiupcLx4Kq/eAkvRg8QxcSJ5sQHkcGN3UJf1nw21/2MFJ7gkeqoTmf7n79V/luJl3AX+or696yUxt3YDuWJiGxJsGA+dVEA/COJWxL7oAXfPBxgojcnjBhXkMEt/Ir+c5OgMlS60xdj5WvKRjYmkLpiIehIj4DGuDtQ+S65aBFrHTsdoQG38GlTVbYEGfJMc+r2i0rtkzxXOJKk0UMUUWUtAv4XIQxwTbfH1GGMLwDtURFSc6EMFtVVLg7ZhhIflaa6roks6DTseX+nUKBLcRcWEZ4BPqnXVvd3tF3ygu5oA2sjhkyv+6HVDXqMzBA==
X-Yahoo-Newman-Id: 838885 DOT 88832 DOT bm AT smtp215 DOT mail DOT gq1 DOT yahoo DOT com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: 1kvLiPEVM1kvUvWbOmzuNS.C.8NqtqXltCzwU77rcXN2MvY
 aucEDpuGEjtsCuIYS4s6r7aR9db2zotdoXUyyZg.QKkYH.sdu27ONqzXYT8i
 Y_ehmhUUPAnDaNAd9O17oPTdE8e.6HzWVehY4nXgPAawItB3X4K6ANEMMAmj
 Lk1x6fDNRYgX8EXWNa.sVwOJYSiUH_bnl.2ypYrLNxKg8Abp0Sa1R3.F.AvD
 YYPkAlowEG1w9PnvEPvZbOw42l.F.VjpVktWTH.hD_MlLOhAZngf4K508E2M
 pL7sM1H5wiIR9E0nanc6LvZS4ESRLlkNzk0fRzi8mVSVl__WTlbyMzX_GowL
 f5QA127R_Ty2P_enyRRPgOkg07wNJVPugb8SR16W0mOYADQX95WzW9XGBzty
 mLkxP0eVAXdNlzbWwJeC.PZ.A6JcsHsZswa.zXevntHXldsbpQt3_cjg8tQx
 JGlkhg3ppm_hS_dp5tuigo0Y0nwOOltAI.gYu0RrUqzGfqT54p4S9tpNfEKb
 5VBXZ_YDBFoe4Jg39PscBiqMFNHOrM6Qmdp9CGp8WhbW0EDo-
X-Yahoo-SMTP: b8jVkbOswBAqZ4BhECp7nxPJUfTGEnEGv_G4qgQeZMeAbA--
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\))
Subject: Re: [geda-user] some more geometry module tweaks (sorry, wall of text)
From: "Edward Hennessy (ehennes AT sbcglobal DOT net) [via geda-user AT delorie DOT com]" <geda-user AT delorie DOT com>
In-Reply-To: <CAC4O8c8_+SwFA1kynZyYAowxNAq0qEv3dJV7FMxZmF9xWceGwQ@mail.gmail.com>
Date: Wed, 6 Jan 2016 20:17:05 -0800
Message-Id: <4807F2B3-2914-48B1-8A40-59D511194AE0@sbcglobal.net>
References: <CAC4O8c-n4cHWum2MUzgDw=NLuKPK395xp_F24cSyoXhnADRskw AT mail DOT gmail DOT com> <alpine DOT DEB DOT 2 DOT 00 DOT 1512230503390 DOT 9035 AT igor2priv> <CAC4O8c8A271d5unQWRV=PoaEsJECgZt33Wy16uCnK6D+4LCzww AT mail DOT gmail DOT com> <alpine DOT DEB DOT 2 DOT 00 DOT 1512260402081 DOT 9035 AT igor2priv> <CAC4O8c-49Fn191KT-p0hXi1jXW=OeTSaNUh11pLmBQYHeGtyoA AT mail DOT gmail DOT com> <alpine DOT DEB DOT 2 DOT 00 DOT 1512310512510 DOT 9035 AT igor2priv> <CAC4O8c8Or1FS=x18C7Zv5uu+dUOXX2My4K+njsoufNeotm_CBQ AT mail DOT gmail DOT com> <alpine DOT DEB DOT 2 DOT 00 DOT 1601060519350 DOT 9035 AT igor2priv> <CAC4O8c97TUwyxV44kt7UhLrnTBVxZjPR1H-T9r6RgLuQeGbQyw AT mail DOT gmail DOT com> <8985B557-CC87-48A0-A745-298A501945F0 AT noqsi DOT com> <CAC4O8c8_+SwFA1kynZyYAowxNAq0qEv3dJV7FMxZmF9xWceGwQ AT mail DOT gmail DOT com>
To: "geda-user AT delorie DOT com" <geda-user AT delorie DOT com>
X-Mailer: Apple Mail (2.2104)
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by delorie.com id u074HAcr011068
Reply-To: geda-user AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: geda-user AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk


> On Jan 6, 2016, at 5:04 PM, Britton Kerin (britton DOT kerin AT gmail DOT com) [via geda-user AT delorie DOT com] <geda-user AT delorie DOT com> wrote:
> 
> 
> 
> On Wed, Jan 6, 2016 at 3:47 PM, John Doty <jpd AT noqsi DOT com> wrote:
> 
> On Jan 6, 2016, at 7:29 PM, Britton Kerin (britton DOT kerin AT gmail DOT com) [via geda-user AT delorie DOT com] <geda-user AT delorie DOT com> wrote:
> 
>> Yeah DJ hinted at this as well.  My knee-jerk reaction is to use an even winder type for the internal floating point representation.  Short of arbitrary precision there's no way to support arbitrary intermediate results, but if you can count bye ones all the way to a squared value that would seem to cover all the simple geometrical calculations we're interested in.  Things like hypot() help, but I admit I don't fully understand exactly how much.  They certainly keep the numbers smaller and thereby prevent overflow, but I don't fully understand the consequences for intermediate results outside the range where the float can represent all integers.
> 
> This particular calculation is numerically stable, even if written as sqrt(x*x+y*y). It can’t generally be perfect, but it’s not the kind of thing that sends numerical analysts into cold sweats.
> 
> Going through and auditing geometry.h for big things they're mostly in hypot() but there are a few others. 
> 
> Do you know about the sensitivity of these:
> 
>   http://mathworld.wolfram.com/Circle-LineIntersection.html
>   http://mathworld.wolfram.com/Circle-CircleIntersection.html
> 
> Britton

To make it easy, the circle could be converted to a polygon. The polygons work well with line sweep algorithms:

https://www.youtube.com/watch?v=dePDHVovJlE

Another great presentation for rectangle intersection:

https://www.youtube.com/watch?v=p9cChQlgx08

Here is the line intersection line sweep code inside libgeda:

http://git.geda-project.org/geda-gaf/tree/libgeda/src/m_hatch.c

If you need a bit more accuracy for geometric calculations, the problem can be translated to center around the origin, convert to double, then run the calculations, and then translate back to the original location, then back to integer.

Ed