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=6HT7iLI24LnHcr9TkeVlS5khrJChTjAunRf9RqVORII=; b=sZaRGFSwfpJ0KnxJrryJIEXTuWx/t0vblac3Bkd5xG8u9CtRiP1uLFH4d3bPzy9bHv hJzFw9m9SLSUnATInOtr2SsFnKUf6EJ+wz/rQ23ORro7iwCQ3pGuhL9PUHztEcRMxR2f v1lVTcOIimxkNKd+uLbeHNWYWoA4+iQi8PKWo8EYY/cf3xjwP1XyiZtIuerNbPmLAVkC f+tHATW9K1OhrzKAvblsO8jCsOe1ki462YJl/gnorBfSHa/OQvF2ScNGHhL8W689c7Y/ GLFBm3iTUG+iKOYzNnixsYI9oxlKS1/McqOaZOV8g1bEuU1e101nSPr1qBMuf/VABdxJ BZ3g== MIME-Version: 1.0 X-Received: by 10.202.201.77 with SMTP id z74mr10806347oif.24.1450798399676; Tue, 22 Dec 2015 07:33:19 -0800 (PST) In-Reply-To: References: <20151222144719 DOT GN14853 AT abax> Date: Tue, 22 Dec 2015 15:33:19 +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 Oh - and Martin, I'd be interested to know how you got on running your board against this old branch of mine: http://www.repo.or.cz/geda-pcb/pcjc2.git/shortlog/refs/heads/for_master2 Take a look at the commit log, and you will see fixes and descriptions of a number of polygon bugs. One or more might impact upon your recent fix for the Collect1 routine - but as you've been studying the code more recently than I, you're probably in a better place to assess these. FWIW, I've seen less problems running this code in anger, and haven't bumped into any new ones. Testing these polygon fixes for changes in behaviour takes some time! - Looks like about 8 months since I last touch my branch :(. Peter On 22 December 2015 at 15:22, Peter Clifton wrote: > Clever solutions exist, and fall into the category of "snap rounding" > algorithms. > > They are moderately complex, and as I'm sure you will appreciate > having dug into PCB's code - so is our existing algorithm. > > If you're interested in working on this, I can dig out some papers and > references. Most start with an assumption of exact arithmetic, which > makes things "interesting". In reality, you may just need to guarantee > "enough" precision. > > FWIW, the BOOST polygon intersection algorithm looks like a good one. > (Although I don't think it does online edits quite as efficiently as > we might - it is WAY better in terms of computational complexity in > the start-from-scratch case). It also solves the snap-rounding problem > on the fly. > > Boost isn't the immediate answer to all problems though.... KiCAD uses > it, and I know they have at least one test-case which causes it to > crash and burn fairly repeatedly. (I had meant to dig into that for > them is a cross-project peace offering, but I ran out of time last > time I started digging). > > Peter > > On 22 December 2015 at 14:47, Martin Beranek wrote: >> Hi, >> >> I was tracing down the cause for a bug when a polygon sometimes >> disappears after component was moved and "Error while clipping PBO_SUB: 3" >> is printed. And I have discovered quite nasty issue related to >> intersections calculation and rounding. >> >> The little PCB which shows this bug is attached (click in the center of >> upper-left silk screen dot in component labeled "*MOVE_ME* and drop it >> over second dot, that is 0.2 mm down and 0.1mm right), but I think the >> problem behind is much more general. >> >> >> Imagine part of contour A--B--C such that A->B edge goes approximately >> in bottom right direction and B->C edge goes back to the left (located >> below A->B, the exact value of angle ABC is not important, say about 45 >> degrees). The inside of the polygon is "between" points 'A' and 'C'. >> >> Then let's have edge C->D which is part of second contour and which >> intersects edge AB really close to the point B. >> >> Calculating the intersection point 'E' and consequent rounding can >> result in coordinate which is actually bellow (!) edge BC, not above it >> as it should be. So we get contour A-E-B-C which intersects itself (the >> edges A-E and B-C intersects and the order of edges and inner/outer >> areas is thus wrong at 'E'. >> >> Bit ascii-art of the result: >> >> >> A. >> \ >> \ >> C-___ \ >> \ `--\-__ >> `-,_ \ `-. >> `---E----B >> \__ >> `----, >> `-----D >> >> >> It seems that current polygon code leave things like this (first contour >> A->E->B->C and second C->E->D). >> >> The edge C->E of second contour is labeled "outer" as it lies below >> 'B->C', so far mostly OK, I guess. But next labeling step at 'E' results >> in (wrong) label "inner" because the assumption that inside of the >> polygon is to the right from the edge is violated there. >> >> >> The actual coordinates which lead to this kind of bug are: >> >> A = [4309892, 10990108] >> B = [4331483, 11008549] >> C = [3998398, 10981358] >> D = [6078476, 11151160] >> >> Calculating intersection between A-B and C-D gives [4331482.44, 11008548.52] >> which is rounded to >> >> E = [4331482, 11008549] >> >> Note that point E is directly to the left from 'B', so below 'B->C'. And >> the point 'B' is above 'E->D'. It feels strange that such intersection >> and rounding can actually exists, but there is real-world case. And it >> totally breaks polygon code. >> >> (I have seen such polygon-disappearing quite often in more complicated >> boards, but it is not so easy to make minimal example and trace the >> actual cause, so I can not tell it is the same issue every time ...) >> >> >> >> What I am wondering about is if there is any sane solution to this >> issue. Some 'clever' rounding which avoids self-intersecting lines would >> be probably quite complicated to code and maybe computation intensive as >> well(?). Maybe still leading to unsolvable situations sometimes? >> But is there any other, better way how to avoid this? >> >> >> Martin >> >>