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=TgFW9ODIZu9/4ZeW9z2yXwqrsfXLgpJgCZKQDKBL0VA=;
        b=eZc8guedjInoo8ue55zTFxgePXaWMo3Qc9zXwMfMdV97fmq+T+deNDLv8hVb0Jwrg2
         9wNJFiVi8oc37bKH4wrp+PmSfWYh7D22SWvXFkQWe8HpVyyU92l4tlFXQ01oQeM/6MpW
         RHf2KXPhkZsceuwuQKm/dIuM1tTn7Pw/zwHH4KglTy4WvFBUBFiPw/ehGlK/Eui2EPiX
         pvab6y8d/1yFd5lzQ0OglEj0qjYW6s2rDpJpDIKjwv36RMPLBApqYPzZG8jq+IFRZK2b
         UH8run2+FO343yykqUSjlt5hwUA0gLbXvDgvI0Bjwu2kW5BTzHrB8/PS0vvGqKZLacHg
         sVcw==
MIME-Version: 1.0
X-Received: by 10.182.245.167 with SMTP id xp7mr5289921obc.63.1450797742679;
 Tue, 22 Dec 2015 07:22:22 -0800 (PST)
In-Reply-To: <20151222144719.GN14853@abax>
References: <20151222144719 DOT GN14853 AT abax>
Date: Tue, 22 Dec 2015 15:22:22 +0000
Message-ID: <CAJXU7q9yKKheYd5fnQz=cax=+rMmjDGNCuojLquq6zsiYZmRxw@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

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
>
>