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=mksneaED/YvkSLXTmkylXvcVXt9/c0ZmTAnhcz28x4E=;
        b=GbbR05zWK4U5TSGG6OQK8Tp7hFtGzoWvLXXpUMMrFnCx0FJkreSzrXTpBRj6Mxvocy
         6hC+DRivoz1eE40xq2W2S7xyyAmN3SWhvZm4Szs4N68ZjloRwXzt5PFKr2hNiZ7gtlKF
         tSnI3t0GH1ltRKNshqYvOL1En1iKoA9ItSqzqW4NrOym8LK5dKootJSrDCDPaD/r0PFR
         uoVbSmBHLMxRHy7P8qEo/4rjNCTSiuH6lRSK/1Y56on0Y1nkWkncpuyhbekWjT2Soxjr
         xmB9u41MvAcEvdq2wjKZWL3Z+wsuNDNQfFBvrcox12ATe/6EchfxPtyKnvVJQuMWrM30
         js0Q==
MIME-Version: 1.0
X-Received: by 10.202.213.215 with SMTP id m206mr10908686oig.26.1450798921134;
 Tue, 22 Dec 2015 07:42:01 -0800 (PST)
In-Reply-To: <CAJXU7q9ufwTHKAZf2Dp-_S5FpAs5BmJSPatrWnCi8uCXmPeyVg@mail.gmail.com>
References: <20151222144719 DOT GN14853 AT abax>
	<CAJXU7q9yKKheYd5fnQz=cax=+rMmjDGNCuojLquq6zsiYZmRxw AT mail DOT gmail DOT com>
	<CAJXU7q9ufwTHKAZf2Dp-_S5FpAs5BmJSPatrWnCi8uCXmPeyVg AT mail DOT gmail DOT com>
Date: Tue, 22 Dec 2015 15:42:01 +0000
Message-ID: <CAJXU7q-Srx0OH7fmzkPc19-+B3yU8yUvNwfwOgnVjosTiOz6jA@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>
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 - one thing else I'd say (which you may have already realised...)

These are two things I learned whilst trying to add support for
primitive arc-segments, and make poly-curve outlines:

It is _really_ easy to make a change to the polygon code which breaks
something in subtle ways elsewhere.
It is _really_ easy to make a tiny change to the collecting code,
which means a bad test-case will now pass - but in fact, it just
no-longer hits the still-existing bug.

It turns out that adding arcs into polygons makes a whole extra load
of pain, and I never got it completely working. I actually got much
better results (or approximations to the correct result), by leaving
the computation in line-segments, but tracking along with each segment
whether it was an original line-segment, or a straight line
approximation to some other curve (the details of which you can attach
and record with the data-structure).

Arcs in polygons (or at least approximating them) was a highly desired
feature for producing better board outlines for 3D export - where such
outlines might have specified arc geometry, or intersect with a via /
pin barrel etc., to include it.

Peter

On 22 December 2015 at 15:33, Peter Clifton
<petercjclifton AT googlemail DOT com> wrote:
> 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
> <petercjclifton AT googlemail DOT com> 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 <martin AT mb5 DOT cz> 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
>>>
>>>