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=googlemail.com; s=20120113;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:to
	:content-type;
	bh=nBWFGT8Wkc3gMdh329R0QBT6m1lcIBxhhyarBUrnF7w=;
	b=mswlUJNd3QqhlvBZm6vVmCrWGKbsKRHqDRRw/htZGDG04DodkuEJUma7+yI2zQCOtU
	d0FsVJb01iyYcPD1Ryr8MAzQmIw0hmOvozjg5eJ/blFTcxyAiC9ymlnI5l29CvXPtozk
	huTn9ZIrhAqub6Re72du/FZxPcOzyVqK3TxyEWxm286X5IEq9vrX499yFRCb1DFW65T/
	l8lhcJgZrrKwGNFNEAeqF8Uu79n6uSPdBolDAdrw19RiYWvuRkTKQ4k7AMjOunC6NUUq
	Fm8fKcvTNro7f0/7vCPEuzk2Rsw+MQ9e/TYSyiuwT1aIhF4KoPVadzb3kwOZk4eSfIWw
	KvEA==
MIME-Version:	1.0
X-Received:	by 10.60.81.202 with SMTP id c10mr12777213oey.61.1450816890561;
	Tue, 22 Dec 2015 12:41:30 -0800 (PST)
In-Reply-To:	<20151222195137.GP14853@abax>
References:	<20151222144719 DOT GN14853 AT abax>
	<CAJXU7q9yKKheYd5fnQz=cax=+rMmjDGNCuojLquq6zsiYZmRxw AT mail DOT gmail DOT com>
	<20151222195137 DOT GP14853 AT abax>
Date:	Tue, 22 Dec 2015 20:41:30 +0000
Message-ID:	<CAJXU7q-hTK5y8R52CTGvRb__sZzDPwMtTudFuLJPBYzjbK9g4g@mail.gmail.com>
Subject:	Re: [geda-user] Self-intersecting polygon appears because of
	intersection coordinates rounding
From:	"Peter Clifton (petercjclifton AT googlemail DOT com) [via geda-user AT delorie DOT com]" <geda-user AT delorie DOT com>
To:	gEDA User Mailing List <geda-user AT delorie DOT com>
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

Snap rounding is where the results of intersections are rounded to a
grid (usually an integer grid).

This is a vague, and from memory understanding (based on the BOOST
algorithm), in that the algorithms are based on looking at what
topology changes might occur during the amount of movement necessary
to shift an intersection point from its exact location, onto the
integer grid.

I believe the algorithms guarantee well conditioned output (it is what
they are designed to cope with), but are probably also quite fast at
computing the intersections and resulting polygons.

The PCB source-code refers to an algorithm, and its academic paper -
which you might like to start with searching for. I'm not sure I ever
fully understood it, and it unfortunately also requires exact
arithmetic were you to implement the pseudo-code.

Most of these are loosely based on a Bentley-Ottman sweep-line
algorithm. Ours is not, and probably suffers in speed because of it.
(I did try to port our intersecton finder to BO once, based on the BO
implementation I lifted out of the Cairo source-code but never really
finished validating it). My later OpenGL rasterisation (in my branch)
uses a cut-down of the cairo BO code to produce trapezoids from
polygon geometry fed from PCB. All I recall from the cairo BO code,
was that it used integer fixed-point arithmetic, and had a number of
128 bit primitives coded up (integer math), in order to guarantee
enough precision to avoid the necessity for exact arithmetic.

One thing I was reflecting on last time I thought about this all, is
that fundamentally, all intersections between polygon edges (or vertex
- edge intersections) in a PCB must actually be lying on points
generated from geometry one layer deep.

Said another - less vague way, whilst our algorithms produce polygons
by adding and subtracting clearance shapes, filling in with patches,
re-subtracting new clearances etc...  ultimately, the final answer is
based upon edges, and intersections from the clearance shapes.

The clearance shapes all come from exact integer geometry of the board
elements - and thus, there is a well bounded amount of extra precision
required to identify the locations of those intersections.


Peter

On 22 December 2015 at 19:51, Martin Beranek <martin AT mb5 DOT cz> wrote:
>> Clever solutions exist, and fall into the category of "snap rounding"
>> algorithms.
>
> Yepp, I have notice only now, that it is mentioned in geda wiki already.
> Together with the fact that cases leading to self-crossing polygons as
> a result exists.
>
> But, referring again to the geda wiki as I have almost no experience in
> this field, the snap rounding algorithm is not a fix (or not guaranteed
> fix?) to this self-intersecting issue, rather just faster algorithm to
> finding intersection points. Is it correct?
>
> Do you have any reference related to this degenerated case particularly?
>
> Martin
>

- Raw text -