kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #38707
Re: PCBNew: Segments/polygons not rendered correctly (from Bug 1806411])
Sorry, I failed to rebase that over the newest changes. This should
apply better as a patch.
Cheers,
John
On Wed, Dec 19, 2018 at 3:15 PM John Beard <john.j.beard@xxxxxxxxx> wrote:
>
> Hi,
>
> I've added a few simple cases to the qa_common unit tests.
>
> I don't know if I will have covered cases which would have exposed any
> bugs here, but any known corner cases (pass or fail) should be added.
>
> Also, they assume the polygons come in a fixed order. I don't know if
> that's a correct assumption, or if the test should merely check the
> triangle is somewhere in the list.
>
> These tests only cover PolygonTriangulation, not the use of it in
> SHAPE_POLY_SET::CacheTriangulation(), so the Fracture bugs aren't
> (yet...) covered. But it would probably be a good idea to also add a
> test including those cases of SHAPE_POLY_SET and check that:
>
> 1) The tests fail before the recent fixes (i.e. the tests are
> sensitive to the bug), and
> 2) They do pass now
>
> Cheers,
>
> John
> On Wed, Dec 19, 2018 at 1:57 PM jp charras <jp.charras@xxxxxxxxxx> wrote:
> >
> > Le 19/12/2018 à 04:48, Seth Hillbrand a écrit :
> > > Am 2018-12-18 14:19, schrieb jp charras:
> > >>
> > >> Sorry Seth,
> > >>
> > >> But with your fixes, CacheTriangulation() crashes with degenerated
> > >> polygons.
> > >>
> > >> To see that, modify gerbview_painter.cpp, line 265 to remove
> > >> absolutePolygon.COutline( 0 ).PointCount() < 3
> > >> and try to load the test file test_polygons_with_arcs.gbr in Gerbview.
> > >
> > > Hi JP-
> > >
> > > Thanks for finding that. The issue was that the Fracture() call
> > > resulted in an empty polygon set with no outlines and I hadn't re-tested
> > > its validity. 64f1fb9e7 fixes the bug.
> > >
> > > -Seth
> >
> >
> > Looks good to me now.
> > And CacheTriangulation() is really faster than GLU tesselation.
> > Thanks.
> >
> >
> > --
> > Jean-Pierre CHARRAS
> >
> > _______________________________________________
> > Mailing list: https://launchpad.net/~kicad-developers
> > Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> > Unsubscribe : https://launchpad.net/~kicad-developers
> > More help : https://help.launchpad.net/ListHelp
From 40aefd8f761b0ba4ea33ef84fa83d02e14a2d103 Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@xxxxxxxxx>
Date: Wed, 19 Dec 2018 13:41:40 +0000
Subject: [PATCH] QA: Add test on Polygon Triangulation
This adds some basic tests on:
* SHAPE_POLY_SET::TRIANGULATED_POLYGON
** Basic run though of the API
* PolygonTriangulation
** Run though a list of a few polys, checking the results make sense
Also add some documentation to these interfaces.
---
include/geometry/polygon_triangulation.h | 36 +-
include/geometry/shape_poly_set.h | 128 +++----
qa/common/CMakeLists.txt | 2 +
.../geometry/test_polygon_triangulation.cpp | 332 ++++++++++++++++++
.../geometry/test_triangulated_polygon.cpp | 80 +++++
.../include/unit_test_utils/unit_test_utils.h | 39 ++
6 files changed, 527 insertions(+), 90 deletions(-)
create mode 100644 qa/common/geometry/test_polygon_triangulation.cpp
create mode 100644 qa/common/geometry/test_triangulated_polygon.cpp
diff --git a/include/geometry/polygon_triangulation.h b/include/geometry/polygon_triangulation.h
index b419b45c6..7b0ff5834 100644
--- a/include/geometry/polygon_triangulation.h
+++ b/include/geometry/polygon_triangulation.h
@@ -51,13 +51,23 @@
#include <vector>
#include <math/box2.h>
+#include <geometry/shape_poly_set.h>
+
#include "clipper.hpp"
+/**
+ * Class that performs triangulation on a polygon: splitting it into a
+ * number of triangles between the existing vertices that completely cover
+ * the original area.
+ */
class PolygonTriangulation
{
public:
-
+ /**
+ * @param aResult a #SHAPE_POLY_SET::TRIANGULATED_POLYGON that will be used
+ * to store the result of successful tessellations.
+ */
PolygonTriangulation( SHAPE_POLY_SET::TRIANGULATED_POLYGON& aResult ) :
m_result( aResult )
{};
@@ -80,7 +90,6 @@ private:
/**
- * Function split
* Splits the referenced polygon between the reference point and
* vertex b, assuming they are in the same polygon. Notes that while we
* create a new vertex pointer for the linked list, we maintain the same
@@ -115,7 +124,6 @@ private:
}
/**
- * Function remove
* Removes the node from the linked list and z-ordered linked list.
*/
void remove()
@@ -141,7 +149,6 @@ private:
}
/**
- * Function updateList
* After inserting or changing nodes, this function should be called to
* remove duplicate vertices and ensure z-ordering is correct
*/
@@ -257,7 +264,6 @@ private:
}
/**
- * Function removeNullTriangles
* Iterates through the list to remove NULL triangles if they exist.
* This should only be called as a last resort when tesselation fails
* as the NULL triangles are inserted as Steiner points to improve the
@@ -294,7 +300,6 @@ private:
}
/**
- * Function createList
* Takes a Clipper path and converts it into a circular, doubly-linked
* list for triangulation
*/
@@ -337,7 +342,6 @@ private:
}
/**
- * Function createList
* Takes the SHAPE_LINE_CHAIN and links each point into a
* circular, doubly-linked list
*/
@@ -371,7 +375,6 @@ private:
}
/**
- * Function: earcutList
* Walks through a circular linked list starting at aPoint. For each point,
* test to see if the adjacent points form a triangle that is completely enclosed
* by the remaining polygon (an "ear" sticking off the polygon). If the three points
@@ -449,13 +452,12 @@ private:
}
/**
- * Function isEar
* Checks whether the given vertex is in the middle of an ear.
* This works by walking forward and backward in zOrder to the limits
* of the minimal bounding box formed around the triangle, checking whether
* any points are located inside the given triangle.
*
- * Returns true if aEar is the apex point of a ear in the polygon
+ * @return true if aEar is the apex point of a ear in the polygon
*/
bool isEar( Vertex* aEar ) const
{
@@ -506,7 +508,6 @@ private:
}
/**
- * Function splitPolygon
* If we cannot find an ear to slice in the current polygon list, we
* use this to split the polygon into two separate lists and slice them each
* independently. This is assured to generate at least one new ear if the
@@ -555,7 +556,6 @@ private:
}
/**
- * Function area
* Returns the twice the signed area of the triangle formed by vertices
* p, q, r.
*/
@@ -565,7 +565,6 @@ private:
}
/**
- * Function intersects
* Checks for intersection between two segments, end points included.
* Returns true if p1-p2 intersects q1-q2
*/
@@ -579,7 +578,6 @@ private:
}
/**
- * Function intersectsPolygon
* Checks whether the segment from vertex a -> vertex b crosses any of the segments
* of the polygon of which vertex a is a member.
* Return true if the segment intersects the edge of the polygon
@@ -602,7 +600,6 @@ private:
}
/**
- * Function locallyInside
* Checks whether the segment from vertex a -> vertex b is inside the polygon
* around the immediate area of vertex a. We don't define the exact area
* over which the segment is inside but it is guaranteed to be inside the polygon
@@ -618,7 +615,6 @@ private:
}
/**
- * Function insertVertex
* Creates an entry in the vertices lookup and optionally inserts the newly
* created vertex into an existing linked list.
* Returns a pointer to the newly created vertex
@@ -644,9 +640,13 @@ private:
return p;
}
-
public:
-
+ /**
+ * Tessellate the given polygon into triangles and store in the
+ * result object.
+ * @param aPoly the polygon to tessellate
+ * @return true if the polygon could be tessellated, false if not
+ */
bool TesselatePolygon( const SHAPE_LINE_CHAIN& aPoly )
{
m_bbox = aPoly.BBox();
diff --git a/include/geometry/shape_poly_set.h b/include/geometry/shape_poly_set.h
index 57a6dc9a6..7f540d9eb 100644
--- a/include/geometry/shape_poly_set.h
+++ b/include/geometry/shape_poly_set.h
@@ -59,9 +59,17 @@ class SHAPE_POLY_SET : public SHAPE
///> N.B. SWIG only supports typedef, so avoid c++ 'using' keyword
typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
+ /**
+ * Represents a set of vertices and a set of triangles made of edges
+ * between the vertices.
+ */
class TRIANGULATED_POLYGON
{
public:
+ /**
+ * A triangle connecting three vertices. The members represent
+ * the indices of the vertices in some other list.
+ */
struct TRI
{
TRI( int _a = 0, int _b = 0, int _c = 0 ) : a( _a ), b( _b ), c( _c )
@@ -71,12 +79,22 @@ class SHAPE_POLY_SET : public SHAPE
int a, b, c;
};
+ /**
+ * Remove all vertices and triangles from this object.
+ */
void Clear()
{
m_vertices.clear();
m_triangles.clear();
}
+ /**
+ * Get the vertex coordinates for the n-th triangle in this polygon
+ * @param index the index of the desired triangle (must be less than #GetTriangleCount())
+ * @param a coordinates of vertex "a"
+ * @param b coordinates of vertex "b"
+ * @param c coordinates of vertex "c"
+ */
void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
{
auto tri = m_triangles[ index ];
@@ -85,6 +103,11 @@ class SHAPE_POLY_SET : public SHAPE
c = m_vertices[ tri.c ];
}
+ /**
+ * Add a new triangle to the list. The vertices that the triangle
+ * connects must be present before calling #GetTriangle
+ * @param aTri The triangle to add
+ */
void AddTriangle( const TRI& aTri )
{
m_triangles.push_back( aTri );
@@ -95,16 +118,30 @@ class SHAPE_POLY_SET : public SHAPE
m_triangles.emplace_back( a, b, c );
}
+ /**
+ * Append a vertex to the list.
+ * @param aP vertex to add
+ */
void AddVertex( const VECTOR2I& aP )
{
m_vertices.push_back( aP );
}
+ /**
+ * Get the number of triangles in this object. Do not try to
+ * access a triangle with a higher index!
+ * @return number of triangles
+ */
size_t GetTriangleCount() const
{
return m_triangles.size();
}
+ /**
+ * Get the number of vertices. Triangles should not refer to vertex
+ * indices higher than this!
+ * @return number of vertices
+ */
size_t GetVertexCount() const
{
return m_vertices.size();
@@ -117,8 +154,6 @@ class SHAPE_POLY_SET : public SHAPE
};
/**
- * Struct VERTEX_INDEX
- *
* Structure to hold the necessary information in order to index a vertex on a
* SHAPE_POLY_SET object: the polygon index, the contour index relative to the polygon and
* the vertex index relative the contour.
@@ -135,8 +170,6 @@ class SHAPE_POLY_SET : public SHAPE
} VERTEX_INDEX;
/**
- * Class ITERATOR_TEMPLATE
- *
* Base class for iterating over all vertices in a given SHAPE_POLY_SET.
*/
template <class T>
@@ -145,7 +178,6 @@ class SHAPE_POLY_SET : public SHAPE
public:
/**
- * Function IsEndContour.
* @return bool - true if the current vertex is the last one of the current contour
* (outline or hole); false otherwise.
*/
@@ -155,7 +187,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function IsLastOutline.
* @return bool - true if the current outline is the last one; false otherwise.
*/
bool IsLastPolygon() const
@@ -169,7 +200,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function Advance
* advances the indices of the current vertex/outline/contour, checking whether the
* vertices in the holes have to be iterated through
*/
@@ -236,7 +266,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function GetIndex
* @return VERTEX_INDEX - indices of the current polygon, contour and vertex.
*/
VERTEX_INDEX GetIndex()
@@ -263,8 +292,6 @@ class SHAPE_POLY_SET : public SHAPE
};
/**
- * Class SEGMENT_ITERATOR_TEMPLATE
- *
* Base class for iterating over all segments in a given SHAPE_POLY_SET.
*/
template <class T>
@@ -272,7 +299,6 @@ class SHAPE_POLY_SET : public SHAPE
{
public:
/**
- * Function IsLastOutline.
* @return bool - true if the current outline is the last one.
*/
bool IsLastPolygon() const
@@ -286,7 +312,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function Advance
* advances the indices of the current vertex/outline/contour, checking whether the
* vertices in the holes have to be iterated through
*/
@@ -353,7 +378,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function GetIndex
* @return VERTEX_INDEX - indices of the current polygon, contour and vertex.
*/
VERTEX_INDEX GetIndex()
@@ -368,7 +392,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function IsAdjacent
* @param aOther is an iterator pointing to another segment.
* @return bool - true if both iterators point to the same segment of the same
* contour of the same polygon of the same polygon set; false
@@ -419,7 +442,6 @@ class SHAPE_POLY_SET : public SHAPE
SHAPE_POLY_SET();
/**
- * Copy constructor SHAPE_POLY_SET
* Performs a deep copy of \p aOther into \p this.
* @param aOther is the SHAPE_POLY_SET object that will be copied.
* @param aDeepCopy if true, make new copies of the triangulated unique_ptr vector
@@ -429,8 +451,6 @@ class SHAPE_POLY_SET : public SHAPE
~SHAPE_POLY_SET();
/**
- * Function GetRelativeIndices
- *
* Converts a global vertex index ---i.e., a number that globally identifies a vertex in a
* concatenated list of all vertices in all contours--- and get the index of the vertex
* relative to the contour relative to the polygon in which it is.
@@ -443,8 +463,7 @@ class SHAPE_POLY_SET : public SHAPE
bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
/**
- * Function GetGlobalIndex
- * computes the global index of a vertex from the relative indices of polygon, contour and
+ * Computes the global index of a vertex from the relative indices of polygon, contour and
* vertex.
* @param aRelativeIndices is the set of relative indices.
* @param aGlobalIdx [out] is the computed global index.
@@ -468,10 +487,8 @@ class SHAPE_POLY_SET : public SHAPE
///> Adds a new hole to the given outline (default: last) and returns its index
int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
- ///> Appends a vertex at the end of the given outline/hole (default: the last outline)
/**
- * Function Append
- * adds a new vertex to the contour indexed by \p aOutline and \p aHole (defaults to the
+ * Adds a new vertex to the contour indexed by \p aOutline and \p aHole (defaults to the
* outline of the last polygon).
* @param x is the x coordinate of the new vertex.
* @param y is the y coordinate of the new vertex.
@@ -491,7 +508,6 @@ class SHAPE_POLY_SET : public SHAPE
void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
/**
- * Function InsertVertex
* Adds a vertex in the globally indexed position aGlobalIndex.
* @param aGlobalIndex is the global index of the position in which teh new vertex will be
* inserted.
@@ -532,7 +548,6 @@ class SHAPE_POLY_SET : public SHAPE
/**
- * Function IsPolygonSelfIntersecting.
* Checks whether the aPolygonIndex-th polygon in the set is self intersecting.
* @param aPolygonIndex index of the polygon that wants to be checked.
* @return bool - true if the aPolygonIndex-th polygon is self intersecting, false
@@ -541,7 +556,6 @@ class SHAPE_POLY_SET : public SHAPE
bool IsPolygonSelfIntersecting( int aPolygonIndex );
/**
- * Function IsSelfIntersecting
* Checks whether any of the polygons in the set is self intersecting.
* @return bool - true if any of the polygons is self intersecting, false otherwise.
*/
@@ -574,7 +588,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function Subset
* returns a subset of the polygons in this set, the ones between aFirstPolygon and
* aLastPolygon.
* @param aFirstPolygon is the first polygon to be included in the returned set.
@@ -627,7 +640,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function Iterate
* returns an object to iterate through the points of the polygons between \p aFirst and
* \p aLast.
* @param aFirst is the first polygon whose points will be iterated.
@@ -651,7 +663,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function Iterate
* @param aOutline the index of the polygon to be iterated.
* @return ITERATOR - an iterator object to visit all points in the main outline of the
* aOutline-th polygon, without visiting the points in the holes.
@@ -662,7 +673,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function IterateWithHoles
* @param aOutline the index of the polygon to be iterated.
* @return ITERATOR - an iterator object to visit all points in the main outline of the
* aOutline-th polygon, visiting also the points in the holes.
@@ -673,7 +683,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function Iterate
* @return ITERATOR - an iterator object to visit all points in all outlines of the set,
* without visiting the points in the holes.
*/
@@ -683,7 +692,6 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function IterateWithHoles
* @return ITERATOR - an iterator object to visit all points in all outlines of the set,
* visiting also the points in the holes.
*/
@@ -786,7 +794,8 @@ class SHAPE_POLY_SET : public SHAPE
return IterateSegments( aOutline, aOutline, true );
}
- /** operations on polygons use a aFastMode param
+ /**
+ * Operations on polygons use a aFastMode param
* if aFastMode is PM_FAST (true) the result can be a weak polygon
* if aFastMode is PM_STRICTLY_SIMPLE (false) (default) the result is (theorically) a strictly
* simple polygon, but calculations can be really significantly time consuming
@@ -850,7 +859,6 @@ class SHAPE_POLY_SET : public SHAPE
void Simplify( POLYGON_MODE aFastMode );
/**
- * Function NormalizeAreaOutlines
* Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s)
* Removes null segments.
* @return int - the polygon count (always >= 1, because there is at least one polygon)
@@ -868,7 +876,6 @@ class SHAPE_POLY_SET : public SHAPE
void Move( const VECTOR2I& aVector ) override;
/**
- * Function Rotate
* rotates all vertices by a given angle
* @param aCenter is the rotation center
* @param aAngle rotation angle in radians
@@ -884,8 +891,6 @@ class SHAPE_POLY_SET : public SHAPE
const BOX2I BBox( int aClearance = 0 ) const override;
/**
- * Function PointOnEdge()
- *
* Checks if point aP lies on an edge or vertex of some of the outlines or holes.
* @param aP is the point to check.
* @return bool - true if the point lies on the edge of any polygon.
@@ -893,7 +898,6 @@ class SHAPE_POLY_SET : public SHAPE
bool PointOnEdge( const VECTOR2I& aP ) const;
/**
- * Function Collide
* Checks whether the point aP collides with the inside of the polygon set; if the point
* lies on an edge or on a corner of any of the polygons, there is no collision: the edges
* does not belong to the polygon itself.
@@ -906,7 +910,6 @@ class SHAPE_POLY_SET : public SHAPE
bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
/**
- * Function Collide
* Checks whether the segment aSeg collides with the inside of the polygon set; if the
* segment touches an edge or a corner of any of the polygons, there is no collision:
* the edges do not belong to the polygon itself.
@@ -920,7 +923,6 @@ class SHAPE_POLY_SET : public SHAPE
bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
/**
- * Function CollideVertex
* Checks whether aPoint collides with any vertex of any of the contours of the polygon.
* @param aPoint is the VECTOR2I point whose collision with respect to the polygon
* will be tested.
@@ -933,7 +935,6 @@ class SHAPE_POLY_SET : public SHAPE
int aClearance = 0 );
/**
- * Function CollideEdge
* Checks whether aPoint collides with any edge of any of the contours of the polygon.
* @param aPoint is the VECTOR2I point whose collision with respect to the polygon
* will be tested.
@@ -962,15 +963,13 @@ class SHAPE_POLY_SET : public SHAPE
}
/**
- * Function RemoveVertex
- * deletes the aGlobalIndex-th vertex.
+ * Deletes the aGlobalIndex-th vertex.
* @param aGlobalIndex is the global index of the to-be-removed vertex.
*/
void RemoveVertex( int aGlobalIndex );
/**
- * Function RemoveVertex
- * deletes the vertex indexed by aIndex (index of polygon, contour and vertex).
+ * Deletes the vertex indexed by aIndex (index of polygon, contour and vertex).
* @param aRelativeIndices is the set of relative indices of the to-be-removed vertex.
*/
void RemoveVertex( VERTEX_INDEX aRelativeIndices );
@@ -979,8 +978,7 @@ class SHAPE_POLY_SET : public SHAPE
void RemoveAllContours();
/**
- * Function RemoveContour
- * deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
+ * Deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
* @param aContourIdx is the index of the contour in the aPolygonIdx-th polygon to be
* removed.
* @param aPolygonIdx is the index of the polygon in which the to-be-removed contour is.
@@ -989,8 +987,7 @@ class SHAPE_POLY_SET : public SHAPE
void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
/**
- * Function RemoveNullSegments
- * looks for null segments; ie, segments whose ends are exactly the same and deletes them.
+ * Looks for null segments; ie, segments whose ends are exactly the same and deletes them.
* @return int - the number of deleted segments.
*/
int RemoveNullSegments();
@@ -1002,8 +999,7 @@ class SHAPE_POLY_SET : public SHAPE
void DeletePolygon( int aIdx );
/**
- * Function Chamfer
- * returns a chamfered version of the aIndex-th polygon.
+ * Returns a chamfered version of the aIndex-th polygon.
* @param aDistance is the chamfering distance.
* @param aIndex is the index of the polygon to be chamfered.
* @return POLYGON - A polygon containing the chamfered version of the aIndex-th polygon.
@@ -1011,8 +1007,7 @@ class SHAPE_POLY_SET : public SHAPE
POLYGON ChamferPolygon( unsigned int aDistance, int aIndex = 0 );
/**
- * Function Fillet
- * returns a filleted version of the aIndex-th polygon.
+ * Returns a filleted version of the aIndex-th polygon.
* @param aRadius is the fillet radius.
* @param aErrorMax is the maximum allowable deviation of the polygon from the circle
* @param aIndex is the index of the polygon to be filleted
@@ -1021,16 +1016,14 @@ class SHAPE_POLY_SET : public SHAPE
POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex = 0 );
/**
- * Function Chamfer
- * returns a chamfered version of the polygon set.
+ * Returns a chamfered version of the polygon set.
* @param aDistance is the chamfering distance.
* @return SHAPE_POLY_SET - A set containing the chamfered version of this set.
*/
SHAPE_POLY_SET Chamfer( int aDistance );
/**
- * Function Fillet
- * returns a filleted version of the polygon set.
+ * Returns a filleted version of the polygon set.
* @param aRadius is the fillet radius.
* @param aErrorMax is the maximum allowable deviation of the polygon from the circle
* @return SHAPE_POLY_SET - A set containing the filleted version of this set.
@@ -1038,8 +1031,7 @@ class SHAPE_POLY_SET : public SHAPE
SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
/**
- * Function DistanceToPolygon
- * computes the minimum distance between the aIndex-th polygon and aPoint.
+ * Computes the minimum distance between the aIndex-th polygon and aPoint.
* @param aPoint is the point whose distance to the aIndex-th polygon has to be measured.
* @param aIndex is the index of the polygon whose distace to aPoint has to be measured.
* @return int - The minimum distance between aPoint and all the segments of the aIndex-th
@@ -1048,8 +1040,7 @@ class SHAPE_POLY_SET : public SHAPE
int DistanceToPolygon( VECTOR2I aPoint, int aIndex );
/**
- * Function DistanceToPolygon
- * computes the minimum distance between the aIndex-th polygon and aSegment with a
+ * Computes the minimum distance between the aIndex-th polygon and aSegment with a
* possible width.
* @param aSegment is the segment whose distance to the aIndex-th polygon has to be
* measured.
@@ -1062,8 +1053,7 @@ class SHAPE_POLY_SET : public SHAPE
int DistanceToPolygon( SEG aSegment, int aIndex, int aSegmentWidth = 0 );
/**
- * Function DistanceToPolygon
- * computes the minimum distance between aPoint and all the polygons in the set
+ * Computes the minimum distance between aPoint and all the polygons in the set
* @param aPoint is the point whose distance to the set has to be measured.
* @return int - The minimum distance between aPoint and all the polygons in the set. If
* the point is contained in any of the polygons, the distance is zero.
@@ -1071,8 +1061,7 @@ class SHAPE_POLY_SET : public SHAPE
int Distance( VECTOR2I aPoint );
/**
- * Function DistanceToPolygon
- * computes the minimum distance between aSegment and all the polygons in the set.
+ * Computes the minimum distance between aSegment and all the polygons in the set.
* @param aSegment is the segment whose distance to the polygon set has to be measured.
* @param aSegmentWidth is the width of the segment; defaults to zero.
* @return int - The minimum distance between aSegment and all the polygons in the set.
@@ -1081,8 +1070,7 @@ class SHAPE_POLY_SET : public SHAPE
int Distance( const SEG& aSegment, int aSegmentWidth = 0 );
/**
- * Function IsVertexInHole.
- * checks whether the aGlobalIndex-th vertex belongs to a hole.
+ * Checks whether the aGlobalIndex-th vertex belongs to a hole.
* @param aGlobalIdx is the index of the vertex.
* @return bool - true if the globally indexed aGlobalIdx-th vertex belongs to a hole.
*/
@@ -1099,8 +1087,8 @@ class SHAPE_POLY_SET : public SHAPE
void unfractureSingle ( POLYGON& path );
void importTree( ClipperLib::PolyTree* tree );
- /** Function booleanOp
- * this is the engine to execute all polygon boolean transforms
+ /**
+ * This is the engine to execute all polygon boolean transforms
* (AND, OR, ... and polygon simplification (merging overlaping polygons)
* @param aType is the transform type ( see ClipperLib::ClipType )
* @param aOtherShape is the SHAPE_LINE_CHAIN to combine with me.
@@ -1120,7 +1108,6 @@ class SHAPE_POLY_SET : public SHAPE
bool pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const;
/**
- * containsSingle function
* Checks whether the point aP is inside the aSubpolyIndex-th polygon of the polyset. If
* the points lies on an edge, the polygon is considered to contain it.
* @param aP is the VECTOR2I point whose position with respect to the inside of
@@ -1144,10 +1131,7 @@ class SHAPE_POLY_SET : public SHAPE
FILLETED
};
-
-
/**
- * Function chamferFilletPolygon
* Returns the camfered or filleted version of the aIndex-th polygon in the set, depending
* on the aMode selected
* @param aMode represent which action will be taken: CORNER_MODE::CHAMFERED will
diff --git a/qa/common/CMakeLists.txt b/qa/common/CMakeLists.txt
index 7ea7084f5..c57b1ebf3 100644
--- a/qa/common/CMakeLists.txt
+++ b/qa/common/CMakeLists.txt
@@ -43,6 +43,8 @@ add_executable( qa_common
libeval/test_numeric_evaluator.cpp
geometry/test_fillet.cpp
+ geometry/test_polygon_triangulation.cpp
+ geometry/test_triangulated_polygon.cpp
view/test_zoom_controller.cpp
)
diff --git a/qa/common/geometry/test_polygon_triangulation.cpp b/qa/common/geometry/test_polygon_triangulation.cpp
new file mode 100644
index 000000000..d94e3de06
--- /dev/null
+++ b/qa/common/geometry/test_polygon_triangulation.cpp
@@ -0,0 +1,332 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2018 KiCad Developers, see CHANGELOG.TXT for contributors.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#include <unit_test_utils/unit_test_utils.h>
+
+#include <geometry/polygon_triangulation.h>
+
+/**
+ * A type holding a triplet of vectors, representing a triangle
+ */
+using VEC_TRI = std::tuple<VECTOR2I, VECTOR2I, VECTOR2I>;
+
+/**
+ * Boost printer for the VEC_TRI type
+ */
+template <> struct BOOST_PRINT::print_log_value<VEC_TRI>
+{
+ void operator()( std::ostream& os, const VEC_TRI& v )
+ {
+ os << "(" << std::get<0>( v ) << "," << std::get<1>( v ) << ", " << std::get<2>( v ) << ")";
+ }
+};
+
+
+struct POLY_TRI_FIXTURE
+{
+ POLY_TRI_FIXTURE() : m_triangulator( m_result )
+ {
+ }
+
+ /// The triangulator to use
+ PolygonTriangulation m_triangulator;
+
+ /// The result that will be written out
+ SHAPE_POLY_SET::TRIANGULATED_POLYGON m_result;
+};
+
+
+BOOST_FIXTURE_TEST_SUITE( PolygonTri, POLY_TRI_FIXTURE )
+
+struct POLY_CASE
+{
+ std::string m_name;
+ std::vector<VECTOR2I> m_pts;
+ bool m_exp_success;
+ size_t m_exp_vtx_cnt;
+ std::vector<VEC_TRI> m_exp_tri_vtxs;
+};
+
+const static std::vector<POLY_CASE> poly_cases = {
+ {
+ "null",
+ {},
+ false,
+ 0,
+ {},
+ },
+ {
+ "point",
+ {
+ { 10, 10 },
+ },
+ false,
+ 0,
+ {},
+ },
+ {
+ "line",
+ {
+ { 10, 10 },
+ { 20, 20 },
+ },
+ false,
+ 2,
+ {},
+ },
+ {
+ "triangle CW unclosed",
+ {
+ { 0, 0 },
+ { 0, 10 },
+ { 10, 10 },
+ },
+ true,
+ 3,
+ {
+ {
+ { 0, 10 },
+ { 0, 0 },
+ { 10, 10 },
+ },
+ },
+ },
+ {
+ "triangle CW closed",
+ {
+ { 0, 0 },
+ { 0, 10 },
+ { 10, 10 },
+ { 0, 0 },
+ },
+ true,
+ 4,
+ {
+ {
+ { 0, 10 },
+ { 0, 0 },
+ { 10, 10 },
+ },
+ },
+ },
+ {
+ "triangle CCW",
+ {
+ { 0, 0 },
+ { 10, 0 },
+ { 10, 10 },
+ },
+ true,
+ 3,
+ {
+ // one triangle, CCW
+ {
+ { 10, 0 },
+ { 10, 10 },
+ { 0, 0 },
+ },
+ },
+ },
+ {
+ "rectangle CCW",
+ {
+ { 0, 0 },
+ { 20, 0 },
+ { 20, 10 },
+ { 0, 10 },
+ },
+ true,
+ 4,
+ {
+ // upper triangle, CCW
+ {
+ { 20, 10 },
+ { 0, 10 },
+ { 0, 0 },
+ },
+ // lower triangle, CCW
+ {
+ { 0, 0 },
+ { 20, 0 },
+ { 20, 10 },
+ },
+ },
+ },
+ {
+ // concave shape, L with outer corner on 0, 0
+ // Splits into 4 triangles radiating out from 0, 0
+ "l-shape CCW",
+ {
+ { 0, 0 },
+ { 20, 0 },
+ { 20, 10 },
+ { 10, 10 },
+ { 10, 20 },
+ { 0, 20 },
+ },
+ true,
+ 6,
+ {
+ // upper left triangle, CCW
+ {
+ { 10, 20 },
+ { 0, 20 },
+ { 0, 0 },
+ },
+ // lower right tri, CCW
+ {
+ { 0, 0 },
+ { 20, 0 },
+ { 20, 10 },
+ },
+ // upper right tri, CCW
+ {
+ { 10, 10 },
+ { 10, 20 },
+ { 0, 0 },
+ },
+ // lower left triangle, CCW
+ {
+ { 0, 0 },
+ { 20, 10 },
+ { 10, 10 },
+ },
+ },
+ },
+ {
+ // rectangle, but one side (the top) has a
+ // collinear point
+ "rectangle with collinear side",
+ {
+ { 0, 0 },
+ { 20, 0 },
+ { 20, 10 },
+ { 10, 10 },
+ { 0, 10 },
+ },
+ true,
+ 5,
+ {
+ // upper/left triangle, CCW
+ {
+ { 10, 10 },
+ { 0, 10 },
+ { 0, 0 },
+ },
+ // middle tri, CCW
+ {
+ { 0, 0 },
+ { 20, 0 },
+ { 20, 10 },
+ },
+ // lower/right tri (CCW)
+ {
+ { 20, 10 },
+ { 10, 10 },
+ { 0, 0 },
+ },
+ },
+ },
+ {
+ // self intersecting hourglass
+ "self-intersecting hourglass",
+ {
+ { 0, 0 },
+ { 10, 0 },
+ { 0, 10 },
+ { 10, 10 },
+ },
+ false,
+ 4,
+ {},
+ },
+ {
+ // self touching hourglass, with vertices at centre
+ "self-touching hourglass",
+ {
+ { 0, 0 },
+ { 5, 5 },
+ { 0, 10 },
+ { 10, 10 },
+ { 5, 5 },
+ { 10, 0 },
+ },
+ true,
+ 6,
+ {
+ // But only the lower triangle comes out
+ {
+ { 10, 0 },
+ { 5, 5 },
+ { 0, 0 },
+ },
+ },
+ },
+};
+
+/**
+ * Tesselation of the defined polygons
+ */
+BOOST_AUTO_TEST_CASE( Polys )
+{
+ for( const auto& c : poly_cases )
+ {
+ BOOST_TEST_CONTEXT( c.m_name )
+ {
+ SHAPE_LINE_CHAIN chain( c.m_pts.data(), c.m_pts.size() );
+
+ const bool result = m_triangulator.TesselatePolygon( chain );
+
+ BOOST_CHECK_EQUAL( c.m_exp_success, result );
+
+ BOOST_CHECK_EQUAL( c.m_exp_vtx_cnt, m_result.GetVertexCount() );
+
+ if( result )
+ {
+ BOOST_CHECK_EQUAL( c.m_exp_tri_vtxs.size(), m_result.GetTriangleCount() );
+
+ // Check the triangles match (only if we have the right number)
+ if( c.m_exp_tri_vtxs.size() == m_result.GetTriangleCount() )
+ {
+ // Check each triangle matches
+ // If the order doesn't matter, could just check each triangle
+ // exists in the result.
+ for( size_t i = 0; i < m_result.GetTriangleCount(); ++i )
+ {
+ VECTOR2I va, vb, vc;
+ m_result.GetTriangle( i, va, vb, vc );
+
+ VEC_TRI got{ va, vb, vc };
+
+ BOOST_CHECK_EQUAL( got, c.m_exp_tri_vtxs[i] );
+ }
+ }
+ }
+ }
+
+ m_result.Clear();
+ }
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/qa/common/geometry/test_triangulated_polygon.cpp b/qa/common/geometry/test_triangulated_polygon.cpp
new file mode 100644
index 000000000..b5f252ed9
--- /dev/null
+++ b/qa/common/geometry/test_triangulated_polygon.cpp
@@ -0,0 +1,80 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2018 KiCad Developers, see CHANGELOG.TXT for contributors.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#include <unit_test_utils/unit_test_utils.h>
+
+#include <geometry/shape_poly_set.h>
+
+
+BOOST_AUTO_TEST_SUITE( TriangulatedPolygon )
+
+/**
+ * Basic ops
+ */
+BOOST_AUTO_TEST_CASE( Basic )
+{
+ SHAPE_POLY_SET::TRIANGULATED_POLYGON tpoly;
+
+ // empty tri poly
+ BOOST_CHECK_EQUAL( 0, tpoly.GetVertexCount() );
+ BOOST_CHECK_EQUAL( 0, tpoly.GetTriangleCount() );
+
+ tpoly.AddVertex( { 0, 0 } );
+ tpoly.AddVertex( { 10, 0 } );
+ tpoly.AddVertex( { 0, 10 } );
+ tpoly.AddVertex( { 10, 10 } );
+
+ BOOST_CHECK_EQUAL( 4, tpoly.GetVertexCount() );
+ BOOST_CHECK_EQUAL( 0, tpoly.GetTriangleCount() );
+
+ tpoly.AddTriangle( 3, 0, 1 ); // A CCW triangle
+
+ BOOST_CHECK_EQUAL( 1, tpoly.GetTriangleCount() );
+
+ tpoly.AddTriangle( SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI{
+ 3, 2, 0 } ); // A CCW triangle, ctro with a TRI
+
+ BOOST_CHECK_EQUAL( 2, tpoly.GetTriangleCount() );
+
+ // retreive and check the triangle points
+ VECTOR2I a, b, c;
+
+ tpoly.GetTriangle( 0, a, b, c );
+ BOOST_CHECK_EQUAL( a, VECTOR2I( 10, 10 ) );
+ BOOST_CHECK_EQUAL( b, VECTOR2I( 0, 0 ) );
+ BOOST_CHECK_EQUAL( c, VECTOR2I( 10, 0 ) );
+
+ tpoly.GetTriangle( 1, a, b, c );
+ BOOST_CHECK_EQUAL( a, VECTOR2I( 10, 10 ) );
+ BOOST_CHECK_EQUAL( b, VECTOR2I( 0, 10 ) );
+ BOOST_CHECK_EQUAL( c, VECTOR2I( 0, 0 ) );
+
+ // clear and check empty
+ tpoly.Clear();
+
+ BOOST_CHECK_EQUAL( 0, tpoly.GetVertexCount() );
+ BOOST_CHECK_EQUAL( 0, tpoly.GetTriangleCount() );
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/qa/unit_test_utils/include/unit_test_utils/unit_test_utils.h b/qa/unit_test_utils/include/unit_test_utils/unit_test_utils.h
index 8efcd46f2..9e54e0fbb 100644
--- a/qa/unit_test_utils/include/unit_test_utils/unit_test_utils.h
+++ b/qa/unit_test_utils/include/unit_test_utils/unit_test_utils.h
@@ -24,6 +24,9 @@
#ifndef UNIT_TEST_UTILS__H
#define UNIT_TEST_UTILS__H
+#include <boost/test/test_case_template.hpp>
+#include <boost/test/unit_test.hpp>
+
#include <functional>
/**
@@ -50,4 +53,40 @@
*/
#undef BOOST_TEST
+
+#if BOOST_VERSION < 105900
+
+/*
+ * BOOST_TEST_INFO is not available before 1.59. It's not critical for
+ * test pass/fail, it's just info, so just pass along to a logging
+ * function.
+ *
+ * This can be removed when our minimum boost version is 1.59 or higher.
+ */
+#define BOOST_TEST_INFO( A ) BOOST_TEST_MESSAGE( A )
+
+/*
+ *
+ * BOOST_TEST_CONTEXT provides scoped info, but again, only after 1.59.
+ * Replacing with a call to BOOST_TEST_MESSAGE will work, and the
+ * scoping will still work for newer boosts.
+ *
+ * This can be removed when our minimum boost version is 1.59 or higher.
+ */
+#define BOOST_TEST_CONTEXT( A ) BOOST_TEST_MESSAGE( A );
+
+#endif
+
+/*
+ * Define a helper to make it easier to use the right namespace for
+ * defining the print helpers like this:
+ *
+ * template<>
+ * struct BOOST_PRINT::print_log_value< MY_TYPE >
+ */
+#if BOOST_VERSION < 105900
+namespace BOOST_PRINT = boost::test_tools;
+#else
+namespace BOOST_PRINT = boost::test_tools::tt_detail;
+#endif
#endif // UNIT_TEST_UTILS__H
\ No newline at end of file
--
2.19.2
Follow ups
References
