← Back to team overview

kicad-developers team mailing list archive

Re: PCBNew: Segments/polygons not rendered correctly (from Bug 1806411])


Hi John-

Am 2018-12-20 06:04, schrieb John Beard:
One thing this test already threw up is that an hourglass made of two
triangles, touching at the apex, triangulates to a single triangle,
and the other one in the original polygon is lost.

That's a good catch. We should figure out how to handle this. Technically, we don't allow self-intersecting polygons but users can still create them.

The main issue here is a discrepancy between what the user sees on the screen and what they see in their gerber output. I think that Gerber does not actually allow self-intersecting polygons, so we should either strictly disallow them or fracture them in the output.

If we fracture them before outputting, we should be fracturing them before drawing as well. This is not so much of an issue for filled zones as they are WSIWYG. But for polygons, we may need to fracture everything. The problem is that fracturing is slow, so we don't want to do it if we don't have to and our routine for checking self-intersections is also slow.

Disallowing them when creating polygons may be better. Or, automatically converting them of simplified polygons on creation/editing might be an option. I wonder what other people's thoughts on this are

I think for a triangulation-pattern-agnostic "correctness" test, you
might consider:

* Take every edge in every triangle. Every edge in the original
polygon should exist once, every edge found only in triangles should
exist twice, once in each direction.

This seems to make sense. I think the first check is better though as edges are not stored, only vertices. So we check that all of the vertices in the polygon exist in the triangulated output.

* Checking winding direction of all triangles matches the original
polygon (if this is a claim the triangulation function makes).

We can't make this claim with concave polygons.

Further sanity checks (which are probably technically superfluous but
still illustrate the expected geometrical properties):

* Check no triangle overlaps any other (also checks no dupes)

Vertices and edges are allowed to overlap. Explicitly so in the case of fracturing polygons with holes. No crossings condition makes sense. This could be implemented as calling PointInPolygon for each vertex in the triangulated set.

* Check no triangle "escapes" the polygon (can only happen for concave polygons)
* Check the summed area = polygon area (combined with no overlap and
no escape, means no gaps inside the polygon)

These three make good sense.

I'll be happy to implement these tests if that sounds sane!