X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f X-Recipient: geda-user AT delorie DOT com Date: Tue, 22 Dec 2015 22:57:30 +0100 From: Martin Beranek To: "Peter Clifton (petercjclifton AT googlemail DOT com) [via geda-user AT delorie DOT com]" Subject: Re: [geda-user] Self-intersecting polygon appears because of intersection coordinates rounding Message-ID: <20151222215730.GQ14853@abax> References: <20151222144719 DOT GN14853 AT abax> <20151222184519 DOT GO14853 AT abax> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) 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 For the polygon.c -- yes, I am aware that there are (in main branch) bugs in frac_circle function and its usage. It was, in fact, one of main reasons why I started to analyze the polygon code. But, exactly as you have written, because modifications in polygon.c can hide bugs in polygon1.c, I have decided to go after bugs there first, at least as long as I have a board producing reproducible bug there. Originally, I believed that disappearing copper fills would be some 'real' bug in a code which just need to be fixed, but it turned out to be more fundamental problem. :-/ Back to the polygons and your points: 1) I see, you have modified the frac_circle() in your branch. What I have noticed is that various calls to frac_circle() does not agree on the fact if first or last point is included, so it leads to long edges between arcs to be not exactly parallel with line or pad (it is not rounding error but missing first/last point in circle approximation). My idea for fix was to change the circle code so that it will produce polygon into which actual exact arc is inscribed. So, transition from straight edge to the circle approximation would be tangent point, not vertex. Coding it this way, some problems related to (not) including first and last point can disappear automatically and the minimal clearance to the object inside is correct without need for adding extra epsilon to radius. I have not read your code yet, so I can not tell how different is my approach compared to yours. > 2. Sometimes we get rounding errors, that make polygon edges which > should end up as exactly straight, out by 1 or 2 nm over their length > - which produces tiny little polygon slivers that are prone to > problems, and rounding. I am not aware of this one. (Given it is really rounding bug and not consequence of point 1.) > 3. Polygon routines that can (under certain circumstances - I forget > _all_ the details) - walk along the wrong contour, and produce > completely incorrect results. This (or at least part of this issue) is what I have fixed in my previous patch, I believe. But your changes are quite different. I'll try to find out if these fix the same or different issue (I have no idea just now, sorry -- similar parts of the code are changed, but in different way). > Martin - I can't promise a lot of availability, but would you be up > for some shared effort on this (perhaps chat on IRC at some point?) to > try to dig to the bottom of these issues once and for all? Availability is an issue for me to. :-/ But yes, sounds good in general. I am not sure I will be much help just now, as I am still spending most of the time trying to understand existing code, but I am about to improve this part. :) We can at least move the discussion to private emails (I am not sure if anyone else in maillist is interested anymore at this point), IRC is OK for me too. > I doubt we'll solve snap-rounding (with any elegant algorithm - unless > we do a mad re-write), but according to Harry Eaton's old comments- It > appears he thought the iterative intersection + edge splitting > approach taken within PCB ought to have avoided the problem. As far as I understand the current code solves the fact that we can get new intersection when straight line is replaced by two segments with integer endpoints, but 1) only intersections between A and B polygons are checked (not self-intersections) and 2) even if we would detect the self-crossing, it is not enough as we would need to do subsequent modification to polygon (split into more parts, change edge directions and add holes) in order to make the contour correct according to the rules. (I am not sure about consequences of such changes during intersection search though.) Modifying the intersection calculating code in a way it avoids generating self-intersecting polygons would be much nicer I think (given it is possible). Martin