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> <20151222195137 DOT GP14853 AT abax> Date: Tue, 22 Dec 2015 20:41:30 +0000 Message-ID: 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]" To: gEDA User Mailing List Content-Type: text/plain; charset=UTF-8 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 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 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 >