1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * This file is part of the LibreOffice project.
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
9 * This file incorporates work covered by the following license notice:
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
20 #ifndef INCLUDED_BASEGFX_POLYGON_B2DPOLYGONTOOLS_HXX
21 #define INCLUDED_BASEGFX_POLYGON_B2DPOLYGONTOOLS_HXX
23 #include <basegfx/point/b2dpoint.hxx>
24 #include <basegfx/vector/b2dvector.hxx>
25 #include <basegfx/range/b2drectangle.hxx>
26 #include <basegfx/polygon/b3dpolygon.hxx>
27 #include <basegfx/polygon/b2dpolygontriangulator.hxx>
28 #include <com/sun/star/drawing/PointSequence.hpp>
29 #include <com/sun/star/drawing/FlagSequence.hpp>
31 #include <basegfx/basegfxdllapi.h>
32 #include <o3tl/typed_flags_set.hxx>
35 namespace basegfx
{ class B2DPolyPolygon
; }
37 // Definitions for the cut flags used from the findCut methods
38 enum class CutFlagValue
46 ALL
= LINE
|START1
|START2
|END1
|END2
,
47 DEFAULT
= LINE
|START2
|END2
,
51 template<> struct typed_flags
<CutFlagValue
> : is_typed_flags
<CutFlagValue
, 0x1f> {};
64 // open/close with point add/remove and control point corrections
65 BASEGFX_DLLPUBLIC
void openWithGeometryChange(B2DPolygon
& rCandidate
);
66 BASEGFX_DLLPUBLIC
void closeWithGeometryChange(B2DPolygon
& rCandidate
);
68 /** Check if given polygon is closed.
70 This is kind of a 'classic' method to support old polygon
71 definitions. Those old polygon definitions define the
72 closed state of the polygon using identical start and
73 endpoints. This method corrects this (removes double
74 start/end points) and sets the Closed()-state of the
77 BASEGFX_DLLPUBLIC
void checkClosed(B2DPolygon
& rCandidate
);
79 // Get successor and predecessor indices. Returning the same index means there
80 // is none. Same for successor.
81 BASEGFX_DLLPUBLIC sal_uInt32
getIndexOfPredecessor(sal_uInt32 nIndex
, const B2DPolygon
& rCandidate
);
82 BASEGFX_DLLPUBLIC sal_uInt32
getIndexOfSuccessor(sal_uInt32 nIndex
, const B2DPolygon
& rCandidate
);
84 // Get orientation of Polygon
85 BASEGFX_DLLPUBLIC B2VectorOrientation
getOrientation(const B2DPolygon
& rCandidate
);
87 // isInside tests for B2dPoint and other B2dPolygon. On border is not inside as long as
88 // not true is given in bWithBorder flag.
89 BASEGFX_DLLPUBLIC
bool isInside(const B2DPolygon
& rCandidate
, const B2DPoint
& rPoint
, bool bWithBorder
= false);
90 BASEGFX_DLLPUBLIC
bool isInside(const B2DPolygon
& rCandidate
, const B2DPolygon
& rPolygon
, bool bWithBorder
= false);
92 /** Get the range of a polygon
94 This method creates the outer range of the subdivided bezier curve.
95 For detailed discussion see B2DPolygon::getB2DRange()
98 The B2DPolygon possibly containing bezier segments
101 The outer range of the bezier curve
103 BASEGFX_DLLPUBLIC B2DRange
getRange(const B2DPolygon
& rCandidate
);
105 // get signed area of polygon
106 BASEGFX_DLLPUBLIC
double getSignedArea(const B2DPolygon
& rCandidate
);
108 // get area of polygon
109 BASEGFX_DLLPUBLIC
double getArea(const B2DPolygon
& rCandidate
);
111 /** get length of polygon edge from point nIndex to nIndex + 1 */
112 BASEGFX_DLLPUBLIC
double getEdgeLength(const B2DPolygon
& rCandidate
, sal_uInt32 nIndex
);
114 /** get length of polygon */
115 BASEGFX_DLLPUBLIC
double getLength(const B2DPolygon
& rCandidate
);
117 // get position on polygon for absolute given distance. If
118 // length is given, it is assumed the correct polygon length, if 0.0 it is calculated
119 // using getLength(...)
120 BASEGFX_DLLPUBLIC B2DPoint
getPositionAbsolute(const B2DPolygon
& rCandidate
, double fDistance
, double fLength
= 0.0);
122 // get position on polygon for relative given distance in range [0.0 .. 1.0]. If
123 // length is given, it is assumed the correct polygon length, if 0.0 it is calculated
124 // using getLength(...)
125 BASEGFX_DLLPUBLIC B2DPoint
getPositionRelative(const B2DPolygon
& rCandidate
, double fDistance
, double fLength
= 0.0);
127 // get a snippet from given polygon for absolute distances. The polygon is assumed
128 // to be opened (not closed). fFrom and fTo need to be in range [0.0 .. fLength], where
129 // fTo >= fFrom. If length is given, it is assumed the correct polygon length,
130 // if 0.0 it is calculated using getLength(...)
131 BASEGFX_DLLPUBLIC B2DPolygon
getSnippetAbsolute(const B2DPolygon
& rCandidate
, double fFrom
, double fTo
, double fLength
= 0.0);
133 // Continuity check for point with given index
134 BASEGFX_DLLPUBLIC B2VectorContinuity
getContinuityInPoint(const B2DPolygon
& rCandidate
, sal_uInt32 nIndex
);
136 // Subdivide all contained curves. Use distanceBound value if given.
137 BASEGFX_DLLPUBLIC B2DPolygon
adaptiveSubdivideByDistance(const B2DPolygon
& rCandidate
, double fDistanceBound
);
139 // Subdivide all contained curves. Use angleBound value if given.
140 BASEGFX_DLLPUBLIC B2DPolygon
adaptiveSubdivideByAngle(const B2DPolygon
& rCandidate
, double fAngleBound
= 0.0);
142 // This version works with two points and vectors to define the
143 // edges for the cut test.
144 BASEGFX_DLLPUBLIC CutFlagValue
findCut(
145 const B2DPoint
& rEdge1Start
, const B2DVector
& rEdge1Delta
,
146 const B2DPoint
& rEdge2Start
, const B2DVector
& rEdge2Delta
,
147 CutFlagValue aCutFlags
= CutFlagValue::DEFAULT
,
148 double* pCut1
= nullptr, double* pCut2
= nullptr);
150 // test if point is on the given edge in range ]0.0..1.0[ without
151 // the start/end points. If so, return true and put the parameter
152 // value in pCut (if provided)
153 BASEGFX_DLLPUBLIC
bool isPointOnEdge(
154 const B2DPoint
& rPoint
,
155 const B2DPoint
& rEdgeStart
,
156 const B2DVector
& rEdgeDelta
,
157 double* pCut
= nullptr);
159 /** Apply given LineDashing to given polygon
161 This method is used to cut down line polygons to the needed
162 pieces when a dashing needs to be applied.
163 It is now capable of keeping contained bezier segments.
164 It is also capable of delivering line and non-line portions
165 depending on what target polygons You provide. This is useful
166 e.g. for dashed lines with two colors.
167 If the last and the first snippet in one of the results have
168 a common start/end ppoint, they will be merged to achieve as
169 view as needed result line snippets. This is also relevant for
170 further processing the results.
173 The polygon based on which the snippets will be created.
176 The line pattern given as array of length values
179 The target for line snippets, e.g. the first entry will be
180 a line segment with length rDotDashArray[0]. The given
181 polygon will be emptied as preparation.
184 The target for gap snippets, e.g. the first entry will be
185 a line segment with length rDotDashArray[1]. The given
186 polygon will be emptied as preparation.
188 @param fFullDashDotLen
189 The summed-up length of the rDotDashArray. If zero, it will
190 be calculated internally.
192 BASEGFX_DLLPUBLIC
void applyLineDashing(
193 const B2DPolygon
& rCandidate
,
194 const ::std::vector
<double>& rDotDashArray
,
195 B2DPolyPolygon
* pLineTarget
,
196 B2DPolyPolygon
* pGapTarget
= nullptr,
197 double fFullDashDotLen
= 0.0);
199 // test if point is inside epsilon-range around an edge defined
200 // by the two given points. Can be used for HitTesting. The epsilon-range
201 // is defined to be the rectangle centered to the given edge, using height
202 // 2 x fDistance, and the circle around both points with radius fDistance.
203 BASEGFX_DLLPUBLIC
bool isInEpsilonRange(const B2DPoint
& rEdgeStart
, const B2DPoint
& rEdgeEnd
, const B2DPoint
& rTestPosition
, double fDistance
);
205 // test if point is inside epsilon-range around the given Polygon. Can be used
206 // for HitTesting. The epsilon-range is defined to be the rectangle centered
207 // to the given edge, using height 2 x fDistance, and the circle around both points
208 // with radius fDistance.
209 BASEGFX_DLLPUBLIC
bool isInEpsilonRange(const B2DPolygon
& rCandidate
, const B2DPoint
& rTestPosition
, double fDistance
);
211 /** Create a polygon from a rectangle.
214 The rectangle which describes the polygon size
218 Radius of the edge rounding, relative to the rectangle size. 0.0 means no
219 rounding, 1.0 will lead to an ellipse
221 BASEGFX_DLLPUBLIC B2DPolygon
createPolygonFromRect( const B2DRectangle
& rRect
, double fRadiusX
, double fRadiusY
);
223 /** Create a polygon from a rectangle.
225 BASEGFX_DLLPUBLIC B2DPolygon
createPolygonFromRect( const B2DRectangle
& rRect
);
227 /** Create the unit polygon
229 BASEGFX_DLLPUBLIC B2DPolygon
const & createUnitPolygon();
231 /** Create a circle polygon with given radius.
233 This method creates a circle approximation consisting of
234 12 cubic bezier segments, which approximate the given
235 circle with an error of less than 0.5 percent.
238 Center point of the circle
243 BASEGFX_DLLPUBLIC B2DPolygon
createPolygonFromCircle( const B2DPoint
& rCenter
, double fRadius
);
245 /// create half circle centered on (0,0) from [0 .. F_PI]
246 B2DPolygon
const & createHalfUnitCircle();
248 /** create a polygon which describes the unit circle and close it
250 @param nStartQuadrant
251 To be able to rebuild the old behaviour where the circles started at bottom,
252 this parameter is used. Default is 0 which is the first quadrant and the
253 polygon's start point will be the rightmost one. When using e.g. 1, the
254 first created quadrant will start at the YMax-position (with Y down on screens,
255 this is the lowest one). This is needed since when lines are dashed, toe old
256 geometry started at bottom point, else it would look different.
258 BASEGFX_DLLPUBLIC B2DPolygon
const & createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant
= 0);
260 /** Create an ellipse polygon with given radii.
262 This method creates an ellipse approximation consisting of
263 12 cubic bezier segments, which approximate the given
264 ellipse with an error of less than 0.5 percent.
267 Center point of the circle
270 Radius of the ellipse in X direction
273 Radius of the ellipse in Y direction
275 @param nStartQuadrant
276 With Y down on screens, 0 = 3 o'clock, 1 = 6 o'clock, 2 = 9 o'clock, 3 = 12 o'clock
278 BASEGFX_DLLPUBLIC B2DPolygon
createPolygonFromEllipse( const B2DPoint
& rCenter
, double fRadiusX
, double fRadiusY
, sal_uInt32 nStartQuadrant
= 0);
280 /** Create an unit ellipse polygon with the given angles, from start to end
282 BASEGFX_DLLPUBLIC B2DPolygon
createPolygonFromEllipseSegment( const B2DPoint
& rCenter
, double fRadiusX
, double fRadiusY
, double fStart
, double fEnd
);
284 BASEGFX_DLLPUBLIC B2DPolygon
createPolygonFromUnitEllipseSegment( double fStart
, double fEnd
);
286 /** Predicate whether a given polygon is a rectangle.
291 @return true, if the polygon describes a rectangle
292 (polygon is closed, and the points are either cw or ccw
293 enumerations of a rectangle's vertices). Note that
294 intermediate points and duplicate points are ignored.
296 BASEGFX_DLLPUBLIC
bool isRectangle( const B2DPolygon
& rPoly
);
298 // create 3d polygon from given 2d polygon. The given fZCoordinate is used to expand the
300 BASEGFX_DLLPUBLIC B3DPolygon
createB3DPolygonFromB2DPolygon(const B2DPolygon
& rCandidate
, double fZCoordinate
= 0.0);
302 // create 2d tools::PolyPolygon from given 3d PolyPolygon. All coordinates are transformed using the given
303 // matrix and the resulting x,y is used to form the new polygon.
304 BASEGFX_DLLPUBLIC B2DPolygon
createB2DPolygonFromB3DPolygon(const B3DPolygon
& rCandidate
, const B3DHomMatrix
& rMat
);
306 // calculate the smallest distance to given edge and return. The relative position on the edge is returned in Cut.
307 // That position is in the range [0.0 .. 1.0] and the returned distance is adapted accordingly to the start or end
309 BASEGFX_DLLPUBLIC
double getSmallestDistancePointToEdge(const B2DPoint
& rPointA
, const B2DPoint
& rPointB
, const B2DPoint
& rTestPoint
, double& rCut
);
311 // for each contained edge calculate the smallest distance. Return the index to the smallest
312 // edge in rEdgeIndex. The relative position on the edge is returned in rCut.
313 // If nothing was found (e.g. empty input plygon), DBL_MAX is returned.
314 BASEGFX_DLLPUBLIC
double getSmallestDistancePointToPolygon(const B2DPolygon
& rCandidate
, const B2DPoint
& rTestPoint
, sal_uInt32
& rEdgeIndex
, double& rCut
);
316 // distort single point. rOriginal describes the original range, where the given points describe the distorted corresponding points.
317 BASEGFX_DLLPUBLIC B2DPoint
distort(const B2DPoint
& rCandidate
, const B2DRange
& rOriginal
, const B2DPoint
& rTopLeft
, const B2DPoint
& rTopRight
, const B2DPoint
& rBottomLeft
, const B2DPoint
& rBottomRight
);
319 // distort polygon. rOriginal describes the original range, where the given points describe the distorted corresponding points.
320 BASEGFX_DLLPUBLIC B2DPolygon
distort(const B2DPolygon
& rCandidate
, const B2DRange
& rOriginal
, const B2DPoint
& rTopLeft
, const B2DPoint
& rTopRight
, const B2DPoint
& rBottomLeft
, const B2DPoint
& rBottomRight
);
322 // expand all segments (which are not yet) to curve segments. This is done with setting the control
323 // vectors on the 1/3 resp. 2/3 distances on each segment.
324 BASEGFX_DLLPUBLIC B2DPolygon
expandToCurve(const B2DPolygon
& rCandidate
);
326 // expand given segment to curve segment. This is done with setting the control
327 // vectors on the 1/3 resp. 2/3 distances. The return value describes if a change took place.
328 BASEGFX_DLLPUBLIC
bool expandToCurveInPoint(B2DPolygon
& rCandidate
, sal_uInt32 nIndex
);
330 // set continuity for given index. If not a curve, nothing will change. Non-curve points are not changed, too.
331 // The return value describes if a change took place.
332 BASEGFX_DLLPUBLIC
bool setContinuityInPoint(B2DPolygon
& rCandidate
, sal_uInt32 nIndex
, B2VectorContinuity eContinuity
);
334 // test if polygon contains neutral points. A neutral point is one whos orientation is neutral
335 // e.g. positioned on the edge of its predecessor and successor
336 BASEGFX_DLLPUBLIC
bool hasNeutralPoints(const B2DPolygon
& rCandidate
);
338 // remove neutral points. A neutral point is one whos orientation is neutral
339 // e.g. positioned on the edge of its predecessor and successor
340 BASEGFX_DLLPUBLIC B2DPolygon
removeNeutralPoints(const B2DPolygon
& rCandidate
);
342 // tests if polygon is convex
343 BASEGFX_DLLPUBLIC
bool isConvex(const B2DPolygon
& rCandidate
);
345 // calculates the orientation at edge nIndex
346 BASEGFX_DLLPUBLIC B2VectorOrientation
getOrientationForIndex(const B2DPolygon
& rCandidate
, sal_uInt32 nIndex
);
348 // calculates if given point is on given line, taking care of the numerical epsilon
349 BASEGFX_DLLPUBLIC
bool isPointOnLine(const B2DPoint
& rStart
, const B2DPoint
& rEnd
, const B2DPoint
& rCandidate
, bool bWithPoints
);
351 // calculates if given point is on given polygon, taking care of the numerical epsilon. Uses
352 // isPointOnLine internally
353 BASEGFX_DLLPUBLIC
bool isPointOnPolygon(const B2DPolygon
& rCandidate
, const B2DPoint
& rPoint
, bool bWithPoints
= true);
355 // test if candidate is inside triangle
356 BASEGFX_DLLPUBLIC
bool isPointInTriangle(const B2DPoint
& rA
, const B2DPoint
& rB
, const B2DPoint
& rC
, const B2DPoint
& rCandidate
, bool bWithBorder
);
358 // test if candidateA and candidateB are on the same side of the given line
359 BASEGFX_DLLPUBLIC
bool arePointsOnSameSideOfLine(const B2DPoint
& rStart
, const B2DPoint
& rEnd
, const B2DPoint
& rCandidateA
, const B2DPoint
& rCandidateB
, bool bWithLine
);
361 // add triangles for given rCandidate to rTarget. For each triangle, 3 points will be added to rCandidate.
362 // All triangles will go from the start point of rCandidate to two consecutive points, building (rCandidate.count() - 2)
364 BASEGFX_DLLPUBLIC
void addTriangleFan(
365 const B2DPolygon
& rCandidate
,
366 triangulator::B2DTriangleVector
& rTarget
);
368 // grow for polygon. Move all geometry in each point in the direction of the normal in that point
369 // with the given amount. Value may be negative.
370 BASEGFX_DLLPUBLIC B2DPolygon
growInNormalDirection(const B2DPolygon
& rCandidate
, double fValue
);
372 // force all sub-polygons to a point count of nSegments
373 BASEGFX_DLLPUBLIC B2DPolygon
reSegmentPolygon(const B2DPolygon
& rCandidate
, sal_uInt32 nSegments
);
375 // create polygon state at t from 0.0 to 1.0 between the two polygons. Both polygons must have the same
376 // organisation, e.g. same amount of points
377 BASEGFX_DLLPUBLIC B2DPolygon
interpolate(const B2DPolygon
& rOld1
, const B2DPolygon
& rOld2
, double t
);
379 // #i76891# Try to remove existing curve segments if they are simply edges
380 BASEGFX_DLLPUBLIC B2DPolygon
simplifyCurveSegments(const B2DPolygon
& rCandidate
);
382 // makes the given indexed point the new polygon start point. To do that, the points in the
383 // polygon will be rotated. This is only valid for closed polygons, for non-closed ones
384 // an assertion will be triggered
385 BASEGFX_DLLPUBLIC B2DPolygon
makeStartPoint(const B2DPolygon
& rCandidate
, sal_uInt32 nIndexOfNewStatPoint
);
387 /** create edges of given length along given B2DPolygon
390 The polygon to move along. Points at the given polygon are created, starting
391 at position fStart and stopping at less or equal to fEnd. The closed state is
393 The polygon is subdivided if curve segments are included. That subdivision is the base
394 for the newly created points.
395 If the source is closed, the indirectly existing last edge may NOT have the
397 If the source is open, all edges will have the given length. You may use the last
398 point of the original when You want to add the last edge Yourself.
401 The length of the created edges. If less or equal zero, an empty polygon is returned.
404 The start distance for the first to be generated point. Use 0.0 to get the
405 original start point. Negative values are truncated to 0.0.
408 The maximum distance for the last point. No more points behind this distance will be created.
409 Use 0.0 to process the whole polygon. Negative values are truncated to 0.0. It also
410 needs to be more or equal to fStart, else it is truncated to fStart.
413 The newly created polygon
415 BASEGFX_DLLPUBLIC B2DPolygon
createEdgesOfGivenLength(const B2DPolygon
& rCandidate
, double fLength
, double fStart
= 0.0, double fEnd
= 0.0);
417 /** Create Waveline along given polygon
418 The implementation is based on createEdgesOfGivenLength and creates a curve
419 segment with the given dimensions for each created line segment. The polygon
420 is treated as if opened (closed state will be ignored) and only for whole
421 edges a curve segment will be created (no rest handling)
424 The polygon along which the waveline will be created
427 The length of a single waveline curve segment
430 The height of the waveline (amplitude)
432 BASEGFX_DLLPUBLIC B2DPolygon
createWaveline(const B2DPolygon
& rCandidate
, double fWaveWidth
, double fWaveHeight
);
434 /** snap some polygon coordinates to discrete coordinates
436 This method allows to snap some polygon points to discrete (integer) values
437 which equals e.g. a snap to discrete coordinates. It will snap points of
438 horizontal and vertical edges
444 The modified version of the source polygon
446 BASEGFX_DLLPUBLIC B2DPolygon
snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon
& rCandidate
);
448 /// get the tangent with which the given point is entered seen from the previous
449 /// polygon path data. Take into account all stuff like closed state, zero-length edges and others.
450 BASEGFX_DLLPUBLIC B2DVector
getTangentEnteringPoint(const B2DPolygon
& rCandidate
, sal_uInt32 nIndex
);
452 /// get the tangent with which the given point is left seen from the following
453 /// polygon path data. Take into account all stuff like closed state, zero-length edges and others.
454 BASEGFX_DLLPUBLIC B2DVector
getTangentLeavingPoint(const B2DPolygon
& rCandidate
, sal_uInt32 nIndex
);
456 /// converters for css::drawing::PointSequence
457 BASEGFX_DLLPUBLIC B2DPolygon
UnoPointSequenceToB2DPolygon(
458 const css::drawing::PointSequence
& rPointSequenceSource
);
459 BASEGFX_DLLPUBLIC
void B2DPolygonToUnoPointSequence(
460 const B2DPolygon
& rPolygon
,
461 css::drawing::PointSequence
& rPointSequenceRetval
);
463 /* converters for css::drawing::PointSequence and
464 css::drawing::FlagSequence to B2DPolygon (curved polygons)
466 B2DPolygon
UnoPolygonBezierCoordsToB2DPolygon(
467 const css::drawing::PointSequence
& rPointSequenceSource
,
468 const css::drawing::FlagSequence
& rFlagSequenceSource
);
469 void B2DPolygonToUnoPolygonBezierCoords(
470 const B2DPolygon
& rPolyPolygon
,
471 css::drawing::PointSequence
& rPointSequenceRetval
,
472 css::drawing::FlagSequence
& rFlagSequenceRetval
);
474 /** Read poly-polygon from SVG.
476 This function imports a poly-polygon from an SVG points
477 attribute (a plain list of coordinate pairs).
480 The output polygon. Note that svg:points can only define a
483 @param rSvgPointsAttribute
484 A valid SVG points attribute string
486 @return true, if the string was successfully parsed
488 BASEGFX_DLLPUBLIC
bool importFromSvgPoints( B2DPolygon
& o_rPoly
,
489 const OUString
& rSvgPointsAttribute
);
491 /** Write poly-polygon to SVG.
493 This function imports a non-bezier polygon to SVG points
494 (a plain list of coordinate pairs).
497 The polygon to export
499 @param rSvgPointsAttribute
500 A valid SVG points attribute string
502 @return true, if the string was successfully parsed
504 BASEGFX_DLLPUBLIC OUString
exportToSvgPoints( const B2DPolygon
& rPoly
);
506 } // end of namespace utils
507 } // end of namespace basegfx
509 #endif // INCLUDED_BASEGFX_POLYGON_B2DPOLYGONTOOLS_HXX
511 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */