X-Authentication-Warning:	delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient:	geda-user AT delorie DOT com
X-Envelope-From:	paubert AT iram DOT es
Date:	Thu, 7 Jan 2016 09:18:08 +0100
From:	"Gabriel Paubert (paubert AT iram DOT es) [via geda-user AT delorie DOT com]" <geda-user AT delorie DOT com>
To:	"Edward Hennessy (ehennes AT sbcglobal DOT net) [via geda-user AT delorie DOT com]" <geda-user AT delorie DOT com>
Subject:	Re: [geda-user] some more geometry module tweaks (sorry, wall of
	text)
Message-ID:	<20160107081808.GA24116@visitor2.iram.es>
References:	<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>
	<4807F2B3-2914-48B1-8A40-59D511194AE0 AT sbcglobal DOT net>
MIME-Version:	1.0
In-Reply-To:	<4807F2B3-2914-48B1-8A40-59D511194AE0@sbcglobal.net>
User-Agent:	Mutt/1.5.21 (2010-09-15)
X-Spamina-Bogosity:	Unsure
X-Spamina-Spam-Score:	-1.0 (-)
X-Spamina-Spam-Report:	Content analysis details: (-1.0 points)
	pts rule name description
	---- ---------------------- --------------------------------------------------
	0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked.
	See
	http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block
	for more information.
	[URIs: delorie.com]
	-1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP
	-0.0 BAYES_40 BODY: Bayes spam probability is 20 to 40%
	[score: 0.3172]
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

On Wed, Jan 06, 2016 at 08:17:05PM -0800, Edward Hennessy (ehennes AT sbcglobal DOT net) [via geda-user AT delorie DOT com] wrote:
> 
> > 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.

Indeed, moving the origin close to the point allows to use double with
quite good confidence. After all we were spekaing of DRC at te start of
this thread, or am I hopelessly confused?

    Gabriel

- Raw text -