kicad-developers team mailing list archive

[Seth Hillbrand <seth@xxxxxxxxxxxxx>]

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!

Definitely!

Best-
Seth