kicad-developers team mailing list archive

[John Beard <john.j.beard@xxxxxxxxx>]

Hi Seth,

Glad you think it's useful! I did wonder about the robustness of the
test against different triangle patterns, but decided to just keep it
simple as a demo, as the exact triangle pattern is not specified to be
(or not to be) predictable.

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.

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.
* Checking winding direction of all triangles matches the original
polygon (if this is a claim the triangulation function makes).

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

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

This is analogous to the philosophy behind the fillet test, which just
checks that the points produced satisfy the expected geometrical
constraints, but doesn't prescribe any specific values.

Cheers,

John
On Wed, Dec 19, 2018 at 7:40 PM Seth Hillbrand <seth@xxxxxxxxxxxxx> wrote:
>
> Am 2018-12-19 10:19, schrieb John Beard:
> > Sorry, I failed to rebase that over the newest changes. This should
> > apply better as a patch.
>
> Hi John-
>
> Thanks for the really useful test harness.  I'll have time to look at it
> in detail in Jan.  Briefly, I have some concerns about testing for
> specific triangle outputs as a triangulation can still be valid with
> different outputs.  I'm not yet sure what kind of test we want here,
> perhaps a total area check or something similar.
>
> I'll give it some thought but if you or others have any ideas off-hand,
> I'd love to hear them.
>
> -Seth