19 using System.Collections.Generic;
33 public List<Segment>
Segments {
get;
set; } =
new List<Segment>();
43 cachedLength =
double.NaN;
68 cachedLength =
double.NaN;
105 cachedLength =
double.NaN;
110 Segments.Add(
new MoveSegment(center.
X + radius * Math.Cos(startAngle), center.
Y + radius * Math.Sin(startAngle)));
112 Segments.Add(
new ArcSegment(center, radius, startAngle, endAngle));
126 public GraphicsPath Arc(
double centerX,
double centerY,
double radius,
double startAngle,
double endAngle)
128 Arc(
new Point(centerX, centerY), radius, startAngle, endAngle);
144 if (radiusX == 0 || radiusY == 0)
146 return this.
LineTo(endPoint);
150 radiusX = Math.Abs(radiusX);
151 radiusY = Math.Abs(radiusY);
159 for (
int i = this.
Segments.Count - 1; i >= 0; i--)
170 double x2 = endPoint.
X;
171 double y2 = endPoint.
Y;
173 double x1P = Math.Cos(axisAngle) * (x1 - x2) * 0.5 + Math.Sin(axisAngle) * (y1 - y2) * 0.5;
175 if (Math.Abs(x1P) < 1e-7)
180 double y1P = -Math.Sin(axisAngle) * (x1 - x2) * 0.5 + Math.Cos(axisAngle) * (y1 - y2) * 0.5;
182 if (Math.Abs(y1P) < 1e-7)
187 double lambda = x1P * x1P / (radiusX * radiusX) + y1P * y1P / (radiusY * radiusY);
191 double sqrtLambda = Math.Sqrt(lambda);
192 radiusX *= sqrtLambda;
193 radiusY *= sqrtLambda;
196 double sqrtTerm = (largeArc != sweepClockwise ? 1 : -1) * Math.Sqrt(Math.Max(0, (radiusX * radiusX * radiusY * radiusY - radiusX * radiusX * y1P * y1P - radiusY * radiusY * x1P * x1P) / (radiusX * radiusX * y1P * y1P + radiusY * radiusY * x1P * x1P)));
198 double cXP = sqrtTerm * radiusX * y1P / radiusY;
199 double cYP = -sqrtTerm * radiusY * x1P / radiusX;
201 double cX = Math.Cos(axisAngle) * cXP - Math.Sin(axisAngle) * cYP + (x1 + x2) * 0.5;
202 double cY = Math.Sin(axisAngle) * cXP + Math.Cos(axisAngle) * cYP + (y1 + y2) * 0.5;
204 double theta1 = AngleVectors(1, 0, (x1P - cXP) / radiusX, (y1P - cYP) / radiusY);
205 double deltaTheta = AngleVectors((x1P - cXP) / radiusX, (y1P - cYP) / radiusY, (-x1P - cXP) / radiusX, (-y1P - cYP) / radiusY) % (2 * Math.PI);
207 if (!sweepClockwise && deltaTheta > 0)
209 deltaTheta -= 2 * Math.PI;
211 else if (sweepClockwise && deltaTheta < 0)
213 deltaTheta += 2 * Math.PI;
216 double r = Math.Min(radiusX, radiusY);
218 ArcSegment arc =
new ArcSegment(0, 0, r, theta1, theta1 + deltaTheta);
220 Segment[] segments = arc.ToBezierSegments();
222 for (
int i = 0; i < segments.Length; i++)
224 for (
int j = 0; j < segments[i].
Points.Length; j++)
226 double newX = segments[i].
Points[j].
X * radiusX / r;
227 double newY = segments[i].
Points[j].
Y * radiusY / r;
229 segments[i].
Points[j] =
new Point(newX * Math.Cos(axisAngle) - newY * Math.Sin(axisAngle) + cX, newX * Math.Sin(axisAngle) + newY * Math.Cos(axisAngle) + cY);
233 cachedLength =
double.NaN;
241 private static double AngleVectors(
double uX,
double uY,
double vX,
double vY)
243 double tbr = Math.Acos((uX * vX + uY * vY) / Math.Sqrt((uX * uX + uY * uY) * (vX * vX + vY * vY)));
244 double sign = Math.Sign(uX * vY - uY * vX);
263 cachedLength =
double.NaN;
268 Segments.Add(
new MoveSegment(control1));
270 Segments.Add(
new CubicBezierSegment(control1, control2, endPoint));
285 public GraphicsPath CubicBezierTo(
double control1X,
double control1Y,
double control2X,
double control2Y,
double endPointX,
double endPointY)
297 cachedLength =
double.NaN;
314 return AddText(
new Point(originX, originY), text, font, textBaseline);
329 Point baselineOrigin = origin;
331 switch (textBaseline)
334 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y);
337 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y + metrics.Top);
340 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y + metrics.Bottom);
343 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y + (metrics.Top - metrics.Bottom) * 0.5 + metrics.Bottom);
347 Point currentGlyphPlacementDelta =
new Point();
352 for (
int i = 0; i < text.Length; i++)
358 currentGlyphPlacementDelta = nextGlyphPlacementDelta;
359 currentGlyphAdvanceDelta = nextGlyphAdvanceDelta;
360 nextGlyphAdvanceDelta =
new Point();
361 nextGlyphPlacementDelta =
new Point();
367 currentGlyphPlacementDelta =
new Point(currentGlyphPlacementDelta.
X + kerning.Glyph1Placement.X, currentGlyphPlacementDelta.
Y + kerning.Glyph1Placement.Y);
368 currentGlyphAdvanceDelta =
new Point(currentGlyphAdvanceDelta.
X + kerning.Glyph1Advance.X, currentGlyphAdvanceDelta.
Y + kerning.Glyph1Advance.Y);
370 nextGlyphPlacementDelta =
new Point(nextGlyphPlacementDelta.
X + kerning.Glyph2Placement.X, nextGlyphPlacementDelta.
Y + kerning.Glyph2Placement.Y);
371 nextGlyphAdvanceDelta =
new Point(nextGlyphAdvanceDelta.
X + kerning.Glyph2Advance.X, nextGlyphAdvanceDelta.
Y + kerning.Glyph2Advance.Y);
377 for (
int j = 0; j < glyphPaths.Length; j++)
379 for (
int k = 0; k < glyphPaths[j].Length; k++)
383 this.
MoveTo(glyphPaths[j][k].X + baselineOrigin.
X + currentGlyphPlacementDelta.
X, -glyphPaths[j][k].Y + baselineOrigin.
Y + currentGlyphPlacementDelta.
Y);
387 if (glyphPaths[j][k].IsOnCurve)
389 this.
LineTo(glyphPaths[j][k].X + baselineOrigin.
X + currentGlyphPlacementDelta.
X, -glyphPaths[j][k].Y + baselineOrigin.
Y + currentGlyphPlacementDelta.
Y);
394 Point quadCtrl =
new Point(glyphPaths[j][k].X + baselineOrigin.
X + currentGlyphPlacementDelta.
X, -glyphPaths[j][k].Y + baselineOrigin.
Y + currentGlyphPlacementDelta.
Y);
395 Point endPoint =
new Point(glyphPaths[j][k + 1].X + baselineOrigin.
X + currentGlyphPlacementDelta.
X, -glyphPaths[j][k + 1].Y + baselineOrigin.
Y + currentGlyphPlacementDelta.
Y);
398 Point ctrl1 =
new Point(startPoint.
X / 3 + 2 * quadCtrl.
X / 3, startPoint.
Y / 3 + 2 * quadCtrl.
Y / 3);
399 Point ctrl2 =
new Point(endPoint.
X / 3 + 2 * quadCtrl.
X / 3, endPoint.
Y / 3 + 2 * quadCtrl.
Y / 3);
412 baselineOrigin.
Y += (currentGlyphAdvanceDelta.
Y) * font.
FontSize / 1000;
429 cachedLength =
double.NaN;
432 double currDelta = 0;
442 currDelta = -fullMetrics.
Width * 0.5 / pathLength;
445 currDelta = -fullMetrics.Width / pathLength;
449 Point currentGlyphPlacementDelta =
new Point();
454 for (
int i = 0; i < text.Length; i++)
456 string c = text.Substring(i, 1);
460 currentGlyphPlacementDelta = nextGlyphPlacementDelta;
461 currentGlyphAdvanceDelta = nextGlyphAdvanceDelta;
462 nextGlyphAdvanceDelta =
new Point();
463 nextGlyphPlacementDelta =
new Point();
469 currentGlyphPlacementDelta =
new Point(currentGlyphPlacementDelta.
X + kerning.Glyph1Placement.X, currentGlyphPlacementDelta.
Y + kerning.Glyph1Placement.Y);
470 currentGlyphAdvanceDelta =
new Point(currentGlyphAdvanceDelta.
X + kerning.Glyph1Advance.X, currentGlyphAdvanceDelta.
Y + kerning.Glyph1Advance.Y);
472 nextGlyphPlacementDelta =
new Point(nextGlyphPlacementDelta.
X + kerning.Glyph2Placement.X, nextGlyphPlacementDelta.
Y + kerning.Glyph2Placement.Y);
473 nextGlyphAdvanceDelta =
new Point(nextGlyphAdvanceDelta.
X + kerning.Glyph2Advance.X, nextGlyphAdvanceDelta.
Y + kerning.Glyph2Advance.Y);
481 Point tangent = path.
GetTangentAtRelative(reference + currDelta + currentGlyphPlacementDelta.
X * font.
FontSize / 1000 + (metrics.Width + metrics.RightSideBearing + metrics.LeftSideBearing) / pathLength * 0.5);
483 origin =
new Point(origin.
X - tangent.
Y * currentGlyphPlacementDelta.
Y * font.
FontSize / 1000, origin.
Y + tangent.
X * currentGlyphPlacementDelta.
Y * font.
FontSize / 1000);
487 switch (textBaseline)
512 glyphPath.
AddText(
new Point(metrics.LeftSideBearing, fullMetrics.Bottom), c, font, textBaseline:
TextBaselines.Baseline);
522 glyphPath.
AddText(
new Point(metrics.LeftSideBearing, fullMetrics.Bottom + fullMetrics.Height / 2), c, font, textBaseline:
TextBaselines.Baseline);
526 glyphPath.
AddText(
new Point(0, fullMetrics.Bottom + fullMetrics.Height / 2), c, font, textBaseline:
TextBaselines.Baseline);
531 double angle = Math.Atan2(tangent.
Y, tangent.
X);
533 for (
int j = 0; j < glyphPath.
Segments.Count; j++)
535 if (glyphPath.
Segments[j].Points !=
null)
537 for (
int k = 0; k < glyphPath.
Segments[j].Points.Length; k++)
539 double newX = glyphPath.
Segments[j].Points[k].X * Math.Cos(angle) - glyphPath.
Segments[j].Points[k].Y * Math.Sin(angle) + origin.
X;
540 double newY = glyphPath.
Segments[j].Points[k].X * Math.Sin(angle) + glyphPath.
Segments[j].Points[k].Y * Math.Cos(angle) + origin.
Y;
551 currDelta += (metrics.Width + metrics.RightSideBearing + metrics.LeftSideBearing + currentGlyphAdvanceDelta.
X * font.
FontSize / 1000) / pathLength;
555 currDelta += (metrics.Width + metrics.RightSideBearing + currentGlyphAdvanceDelta.
X * font.
FontSize / 1000) / pathLength;
583 if (
double.IsNaN(italicAngle))
588 Point baselineOrigin = origin;
590 switch (textBaseline)
593 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y);
596 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y + metrics.Top);
599 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y + metrics.Bottom);
602 baselineOrigin =
new Point(origin.
X - metrics.LeftSideBearing, origin.
Y + (metrics.Top - metrics.Bottom) * 0.5 + metrics.Bottom);
702 bool started =
false;
704 double currX = baselineOrigin.
X;
705 double underlineStartX = baselineOrigin.
X + metrics.LeftSideBearing;
706 double currUnderlineX = underlineStartX - metrics.LeftSideBearing;
708 Point currentGlyphPlacementDelta =
new Point();
713 for (
int i = 0; i < text.Length; i++)
719 currentGlyphPlacementDelta = nextGlyphPlacementDelta;
720 currentGlyphAdvanceDelta = nextGlyphAdvanceDelta;
721 nextGlyphAdvanceDelta =
new Point();
722 nextGlyphPlacementDelta =
new Point();
728 currentGlyphPlacementDelta =
new Point(currentGlyphPlacementDelta.
X + kerning.Glyph1Placement.X, currentGlyphPlacementDelta.
Y + kerning.Glyph1Placement.Y);
729 currentGlyphAdvanceDelta =
new Point(currentGlyphAdvanceDelta.
X + kerning.Glyph1Advance.X, currentGlyphAdvanceDelta.
Y + kerning.Glyph1Advance.Y);
731 nextGlyphPlacementDelta =
new Point(nextGlyphPlacementDelta.
X + kerning.Glyph2Placement.X, nextGlyphPlacementDelta.
Y + kerning.Glyph2Placement.Y);
732 nextGlyphAdvanceDelta =
new Point(nextGlyphAdvanceDelta.
X + kerning.Glyph2Advance.X, nextGlyphAdvanceDelta.
Y + kerning.Glyph2Advance.Y);
738 if (intersections !=
null)
740 intersections[0] = intersections[0] * font.
FontSize / 1000;
741 intersections[1] = intersections[1] * font.
FontSize / 1000;
764 else if (i == text.Length - 1)
807 bool started =
false;
809 double currX = baselineOrigin.
X;
810 double underlineStartX = baselineOrigin.
X + metrics.LeftSideBearing;
811 double currUnderlineX = underlineStartX - metrics.LeftSideBearing;
813 Point currentGlyphPlacementDelta =
new Point();
818 for (
int i = 0; i < text.Length; i++)
824 currentGlyphPlacementDelta = nextGlyphPlacementDelta;
825 currentGlyphAdvanceDelta = nextGlyphAdvanceDelta;
826 nextGlyphAdvanceDelta =
new Point();
827 nextGlyphPlacementDelta =
new Point();
833 currentGlyphPlacementDelta =
new Point(currentGlyphPlacementDelta.
X + kerning.Glyph1Placement.X, currentGlyphPlacementDelta.
Y + kerning.Glyph1Placement.Y);
834 currentGlyphAdvanceDelta =
new Point(currentGlyphAdvanceDelta.
X + kerning.Glyph1Advance.X, currentGlyphAdvanceDelta.
Y + kerning.Glyph1Advance.Y);
836 nextGlyphPlacementDelta =
new Point(nextGlyphPlacementDelta.
X + kerning.Glyph2Placement.X, nextGlyphPlacementDelta.
Y + kerning.Glyph2Placement.Y);
837 nextGlyphAdvanceDelta =
new Point(nextGlyphAdvanceDelta.
X + kerning.Glyph2Advance.X, nextGlyphAdvanceDelta.
Y + kerning.Glyph2Advance.Y);
843 if (intersections !=
null)
845 intersections[0] = intersections[0] * font.
FontSize / 1000;
846 intersections[1] = intersections[1] * font.
FontSize / 1000;
869 else if (i == text.Length - 1)
903 bool started =
false;
905 double currX = baselineOrigin.
X;
906 double underlineStartX = baselineOrigin.
X + metrics.LeftSideBearing;
907 double currUnderlineX = underlineStartX - metrics.LeftSideBearing;
909 Point currentGlyphPlacementDelta =
new Point();
914 for (
int i = 0; i < text.Length; i++)
920 currentGlyphPlacementDelta = nextGlyphPlacementDelta;
921 currentGlyphAdvanceDelta = nextGlyphAdvanceDelta;
922 nextGlyphAdvanceDelta =
new Point();
923 nextGlyphPlacementDelta =
new Point();
929 currentGlyphPlacementDelta =
new Point(currentGlyphPlacementDelta.
X + kerning.Glyph1Placement.X, currentGlyphPlacementDelta.
Y + kerning.Glyph1Placement.Y);
930 currentGlyphAdvanceDelta =
new Point(currentGlyphAdvanceDelta.
X + kerning.Glyph1Advance.X, currentGlyphAdvanceDelta.
Y + kerning.Glyph1Advance.Y);
932 nextGlyphPlacementDelta =
new Point(nextGlyphPlacementDelta.
X + kerning.Glyph2Placement.X, nextGlyphPlacementDelta.
Y + kerning.Glyph2Placement.Y);
933 nextGlyphAdvanceDelta =
new Point(nextGlyphAdvanceDelta.
X + kerning.Glyph2Advance.X, nextGlyphAdvanceDelta.
Y + kerning.Glyph2Advance.Y);
939 if (intersections !=
null)
941 intersections[0] = intersections[0] * font.
FontSize / 1000;
942 intersections[1] = intersections[1] * font.
FontSize / 1000;
967 else if (i == text.Length - 1)
1004 bool started =
false;
1006 double currX = baselineOrigin.
X;
1007 double underlineStartX = baselineOrigin.
X + metrics.LeftSideBearing;
1008 double currUnderlineX = underlineStartX - metrics.LeftSideBearing;
1010 Point currentGlyphPlacementDelta =
new Point();
1011 Point currentGlyphAdvanceDelta =
new Point();
1015 for (
int i = 0; i < text.Length; i++)
1021 currentGlyphPlacementDelta = nextGlyphPlacementDelta;
1022 currentGlyphAdvanceDelta = nextGlyphAdvanceDelta;
1023 nextGlyphAdvanceDelta =
new Point();
1024 nextGlyphPlacementDelta =
new Point();
1028 if (kerning !=
null)
1030 currentGlyphPlacementDelta =
new Point(currentGlyphPlacementDelta.
X + kerning.Glyph1Placement.X, currentGlyphPlacementDelta.
Y + kerning.Glyph1Placement.Y);
1031 currentGlyphAdvanceDelta =
new Point(currentGlyphAdvanceDelta.
X + kerning.Glyph1Advance.X, currentGlyphAdvanceDelta.
Y + kerning.Glyph1Advance.Y);
1033 nextGlyphPlacementDelta =
new Point(nextGlyphPlacementDelta.
X + kerning.Glyph2Placement.X, nextGlyphPlacementDelta.
Y + kerning.Glyph2Placement.Y);
1034 nextGlyphAdvanceDelta =
new Point(nextGlyphAdvanceDelta.
X + kerning.Glyph2Advance.X, nextGlyphAdvanceDelta.
Y + kerning.Glyph2Advance.Y);
1040 if (intersections !=
null)
1042 intersections[0] = intersections[0] * font.
FontSize / 1000;
1043 intersections[1] = intersections[1] * font.
FontSize / 1000;
1072 else if (i == text.Length - 1)
1125 if (points.Length == 0)
1129 else if (points.Length == 1)
1131 return this.
LineTo(points[0]);
1133 else if (points.Length == 2)
1138 Point[] smoothedSpline = SmoothSpline.SmoothSplines(points);
1140 this.
LineTo(smoothedSpline[0]);
1142 for (
int i = 1; i < smoothedSpline.Length; i += 3)
1144 this.
CubicBezierTo(smoothedSpline[i], smoothedSpline[i + 1], smoothedSpline[i + 2]);
1150 private double cachedLength =
double.NaN;
1158 if (
double.IsNaN(cachedLength))
1164 for (
int i = 0; i < this.
Segments.Count; i++)
1169 currPoint = this.
Segments[i].Point;
1170 figureStartPoint = this.
Segments[i].Point;
1175 cachedLength += this.
Segments[i].Measure(currPoint);
1176 currPoint = this.
Segments[i].Point;
1180 currPoint = this.
Segments[i].Point;
1181 figureStartPoint = this.
Segments[i].Point;
1187 cachedLength += this.
Segments[i].Measure(currPoint);
1188 currPoint = this.
Segments[i].Point;
1192 ArcSegment seg = (ArcSegment)this.
Segments[i];
1193 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
1194 cachedLength += this.
Segments[i].Measure(figureStartPoint);
1195 currPoint = this.
Segments[i].Point;
1199 cachedLength += Math.Sqrt((currPoint.
X - figureStartPoint.
X) * (currPoint.
X - figureStartPoint.
X) + (currPoint.
Y - figureStartPoint.
Y) * (currPoint.
Y - figureStartPoint.
Y));
1200 currPoint = figureStartPoint;
1205 cachedLength += this.
Segments[i].Measure(currPoint);
1206 currPoint = this.
Segments[i].Point;
1210 currPoint = this.
Segments[i].Points[0];
1211 figureStartPoint = this.
Segments[i].Points[0];
1212 cachedLength += this.
Segments[i].Measure(currPoint);
1213 currPoint = this.
Segments[i].Point;
1220 return cachedLength;
1242 if (length >= 0 && length <= pathLength)
1249 for (
int i = 0; i < this.
Segments.Count; i++)
1254 currPoint = this.
Segments[i].Point;
1255 figureStartPoint = this.
Segments[i].Point;
1260 double segLength = this.
Segments[i].Measure(currPoint);
1262 if (currLen + segLength < length)
1264 currLen += segLength;
1265 currPoint = this.
Segments[i].Point;
1269 double pos = (length - currLen) / segLength;
1270 return this.
Segments[i].GetPointAt(currPoint, pos);
1275 currPoint = this.
Segments[i].Point;
1276 figureStartPoint = this.
Segments[i].Point;
1282 double segLength = this.
Segments[i].Measure(currPoint);
1284 if (currLen + segLength < length)
1286 currLen += segLength;
1287 currPoint = this.
Segments[i].Point;
1291 double pos = (length - currLen) / segLength;
1292 return this.
Segments[i].GetPointAt(currPoint, pos);
1297 ArcSegment seg = (ArcSegment)this.
Segments[i];
1298 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
1299 currPoint = figureStartPoint;
1301 double segLength = this.
Segments[i].Measure(currPoint);
1303 if (currLen + segLength < length)
1305 currLen += segLength;
1306 currPoint = this.
Segments[i].Point;
1310 double pos = (length - currLen) / segLength;
1311 return this.
Segments[i].GetPointAt(currPoint, pos);
1317 double segLength = Math.Sqrt((currPoint.
X - figureStartPoint.
X) * (currPoint.
X - figureStartPoint.
X) + (currPoint.
Y - figureStartPoint.
Y) * (currPoint.
Y - figureStartPoint.
Y));
1319 if (currLen + segLength < length)
1321 currLen += segLength;
1322 currPoint = figureStartPoint;
1326 double pos = (length - currLen) / segLength;
1327 return new Point(currPoint.
X * (1 - pos) + figureStartPoint.
X * pos, currPoint.
Y * (1 - pos) + figureStartPoint.
Y * pos);
1334 double segLength = this.
Segments[i].Measure(currPoint);
1336 if (currLen + segLength < length)
1338 currLen += segLength;
1339 currPoint = this.
Segments[i].Point;
1343 double pos = (length - currLen) / segLength;
1344 return this.
Segments[i].GetPointAt(currPoint, pos);
1349 currPoint = this.
Segments[i].Points[0];
1350 figureStartPoint = this.
Segments[i].Points[0];
1351 double segLength = this.
Segments[i].Measure(currPoint);
1353 if (currLen + segLength < length)
1355 currLen += segLength;
1356 currPoint = this.
Segments[i].Point;
1360 double pos = (length - currLen) / segLength;
1361 return this.
Segments[i].GetPointAt(currPoint, pos);
1368 throw new InvalidOperationException(
"Unexpected code path!");
1370 else if (length > pathLength)
1372 double currLength = 0;
1377 for (
int i = 0; i < this.
Segments.Count - 1; i++)
1382 currPoint = this.
Segments[i].Point;
1383 figureStartPoint = this.
Segments[i].Point;
1388 currLength += this.
Segments[i].Measure(currPoint);
1389 currPoint = this.
Segments[i].Point;
1393 currPoint = this.
Segments[i].Point;
1394 figureStartPoint = this.
Segments[i].Point;
1400 currLength += this.
Segments[i].Measure(currPoint);
1401 currPoint = this.
Segments[i].Point;
1405 ArcSegment seg = (ArcSegment)this.
Segments[i];
1406 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
1407 currLength += this.
Segments[i].Measure(figureStartPoint);
1408 currPoint = this.
Segments[i].Point;
1412 currLength += Math.Sqrt((currPoint.
X - figureStartPoint.
X) * (currPoint.
X - figureStartPoint.
X) + (currPoint.
Y - figureStartPoint.
Y) * (currPoint.
Y - figureStartPoint.
Y));
1413 currPoint = figureStartPoint;
1418 currLength += this.
Segments[i].Measure(currPoint);
1419 currPoint = this.
Segments[i].Point;
1423 currPoint = this.
Segments[i].Points[0];
1424 figureStartPoint = this.
Segments[i].Points[0];
1425 currLength += this.
Segments[i].Measure(currPoint);
1426 currPoint = this.
Segments[i].Point;
1438 double pos = 1 + (length - pathLength) / this.
Segments[this.
Segments.Count - 1].Measure(currPoint);
1447 throw new InvalidOperationException(
"Unexpected code path!");
1454 for (
int i = 0; i < this.
Segments.Count; i++)
1459 currPoint = this.
Segments[i].Point;
1460 figureStartPoint = this.
Segments[i].Point;
1465 double segLength = this.
Segments[i].Measure(currPoint);
1466 double pos = length / segLength;
1467 return this.
Segments[i].GetPointAt(currPoint, pos);
1471 currPoint = this.
Segments[i].Point;
1472 figureStartPoint = this.
Segments[i].Point;
1478 double segLength = this.
Segments[i].Measure(currPoint);
1479 double pos = length / segLength;
1480 return this.
Segments[i].GetPointAt(currPoint, pos);
1484 ArcSegment seg = (ArcSegment)this.
Segments[i];
1485 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
1486 currPoint = figureStartPoint;
1488 double segLength = this.
Segments[i].Measure(currPoint);
1489 double pos = length / segLength;
1490 return this.
Segments[i].GetPointAt(currPoint, pos);
1494 double segLength = Math.Sqrt((currPoint.
X - figureStartPoint.
X) * (currPoint.
X - figureStartPoint.
X) + (currPoint.
Y - figureStartPoint.
Y) * (currPoint.
Y - figureStartPoint.
Y));
1495 double pos = length / segLength;
1496 return new Point(currPoint.
X * (1 - pos) + figureStartPoint.
X * pos, currPoint.
Y * (1 - pos) + figureStartPoint.
Y * pos);
1501 double segLength = this.
Segments[i].Measure(currPoint);
1502 double pos = length / segLength;
1503 return this.
Segments[i].GetPointAt(currPoint, pos);
1507 currPoint = this.
Segments[i].Points[0];
1508 figureStartPoint = this.
Segments[i].Points[0];
1509 double segLength = this.
Segments[i].Measure(currPoint);
1510 double pos = length / segLength;
1511 return this.
Segments[i].GetPointAt(currPoint, pos);
1516 throw new InvalidOperationException(
"Unexpected code path!");
1539 if (length >= 0 && length <= pathLength)
1546 for (
int i = 0; i < this.
Segments.Count; i++)
1551 currPoint = this.
Segments[i].Point;
1552 figureStartPoint = this.
Segments[i].Point;
1557 double segLength = this.
Segments[i].Measure(currPoint);
1559 if (currLen + segLength < length)
1561 currLen += segLength;
1562 currPoint = this.
Segments[i].Point;
1566 double pos = (length - currLen) / segLength;
1567 return this.
Segments[i].GetTangentAt(currPoint, pos);
1572 currPoint = this.
Segments[i].Point;
1573 figureStartPoint = this.
Segments[i].Point;
1579 double segLength = this.
Segments[i].Measure(currPoint);
1581 if (currLen + segLength < length)
1583 currLen += segLength;
1584 currPoint = this.
Segments[i].Point;
1588 double pos = (length - currLen) / segLength;
1589 return this.
Segments[i].GetTangentAt(currPoint, pos);
1594 ArcSegment seg = (ArcSegment)this.
Segments[i];
1595 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
1596 currPoint = figureStartPoint;
1598 double segLength = this.
Segments[i].Measure(currPoint);
1600 if (currLen + segLength < length)
1602 currLen += segLength;
1603 currPoint = this.
Segments[i].Point;
1607 double pos = (length - currLen) / segLength;
1608 return this.
Segments[i].GetTangentAt(currPoint, pos);
1614 double segLength = Math.Sqrt((currPoint.
X - figureStartPoint.
X) * (currPoint.
X - figureStartPoint.
X) + (currPoint.
Y - figureStartPoint.
Y) * (currPoint.
Y - figureStartPoint.
Y));
1616 if (currLen + segLength < length)
1618 currLen += segLength;
1619 currPoint = figureStartPoint;
1623 double pos = (length - currLen) / segLength;
1624 return new Point(figureStartPoint.
X - currPoint.
X, figureStartPoint.
Y - currPoint.
Y).
Normalize();
1631 double segLength = this.
Segments[i].Measure(currPoint);
1633 if (currLen + segLength < length)
1635 currLen += segLength;
1636 currPoint = this.
Segments[i].Point;
1640 double pos = (length - currLen) / segLength;
1641 return this.
Segments[i].GetTangentAt(currPoint, pos);
1646 currPoint = this.
Segments[i].Points[0];
1647 figureStartPoint = this.
Segments[i].Points[0];
1648 double segLength = this.
Segments[i].Measure(currPoint);
1650 if (currLen + segLength < length)
1652 currLen += segLength;
1653 currPoint = this.
Segments[i].Point;
1657 double pos = (length - currLen) / segLength;
1658 return this.
Segments[i].GetTangentAt(currPoint, pos);
1665 throw new InvalidOperationException(
"Unexpected code path!");
1667 else if (length > pathLength)
1669 double currLength = 0;
1674 for (
int i = 0; i < this.
Segments.Count - 1; i++)
1679 currPoint = this.
Segments[i].Point;
1680 figureStartPoint = this.
Segments[i].Point;
1685 currLength += this.
Segments[i].Measure(currPoint);
1686 currPoint = this.
Segments[i].Point;
1690 currPoint = this.
Segments[i].Point;
1691 figureStartPoint = this.
Segments[i].Point;
1697 currLength += this.
Segments[i].Measure(currPoint);
1698 currPoint = this.
Segments[i].Point;
1702 ArcSegment seg = (ArcSegment)this.
Segments[i];
1703 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
1704 currLength += this.
Segments[i].Measure(figureStartPoint);
1705 currPoint = this.
Segments[i].Point;
1709 currLength += Math.Sqrt((currPoint.
X - figureStartPoint.
X) * (currPoint.
X - figureStartPoint.
X) + (currPoint.
Y - figureStartPoint.
Y) * (currPoint.
Y - figureStartPoint.
Y));
1710 currPoint = figureStartPoint;
1715 currLength += this.
Segments[i].Measure(currPoint);
1716 currPoint = this.
Segments[i].Point;
1720 currPoint = this.
Segments[i].Points[0];
1721 figureStartPoint = this.
Segments[i].Points[0];
1722 currLength += this.
Segments[i].Measure(currPoint);
1723 currPoint = this.
Segments[i].Point;
1735 double pos = 1 + (length - pathLength) / this.
Segments[this.
Segments.Count - 1].Measure(currPoint);
1736 return this.
Segments[this.
Segments.Count - 1].GetTangentAt(currPoint, pos);
1744 throw new InvalidOperationException(
"Unexpected code path!");
1751 for (
int i = 0; i < this.
Segments.Count; i++)
1756 currPoint = this.
Segments[i].Point;
1757 figureStartPoint = this.
Segments[i].Point;
1762 double segLength = this.
Segments[i].Measure(currPoint);
1763 double pos = length / segLength;
1764 return this.
Segments[i].GetTangentAt(currPoint, pos);
1768 currPoint = this.
Segments[i].Point;
1769 figureStartPoint = this.
Segments[i].Point;
1775 double segLength = this.
Segments[i].Measure(currPoint);
1776 double pos = length / segLength;
1777 return this.
Segments[i].GetTangentAt(currPoint, pos);
1781 ArcSegment seg = (ArcSegment)this.
Segments[i];
1782 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
1783 currPoint = figureStartPoint;
1785 double segLength = this.
Segments[i].Measure(currPoint);
1786 double pos = length / segLength;
1787 return this.
Segments[i].GetTangentAt(currPoint, pos);
1791 double segLength = Math.Sqrt((currPoint.
X - figureStartPoint.
X) * (currPoint.
X - figureStartPoint.
X) + (currPoint.
Y - figureStartPoint.
Y) * (currPoint.
Y - figureStartPoint.
Y));
1792 double pos = length / segLength;
1793 return new Point(figureStartPoint.
X - currPoint.
X, figureStartPoint.
Y - currPoint.
Y).
Normalize();
1798 double segLength = this.
Segments[i].Measure(currPoint);
1799 double pos = length / segLength;
1800 return this.
Segments[i].GetTangentAt(currPoint, pos);
1804 currPoint = this.
Segments[i].Points[0];
1805 figureStartPoint = this.
Segments[i].Points[0];
1806 double segLength = this.
Segments[i].Measure(currPoint);
1807 double pos = length / segLength;
1808 return this.
Segments[i].GetTangentAt(currPoint, pos);
1813 throw new InvalidOperationException(
"Unexpected code path!");
1825 return new Point(-tangent.
Y, tangent.
X);
1836 return new Point(-tangent.
Y, tangent.
X);
1846 if (!(resolution > 0))
1848 throw new ArgumentOutOfRangeException(nameof(resolution), resolution,
"The resolution must be greater than 0!");
1853 Point? previousPoint =
null;
1857 tbr.Segments.AddRange(seg.
Linearise(previousPoint, resolution));
1861 previousPoint = seg.
Point;
1876 List<Point> currFigure =
null;
1877 bool returned =
true;
1888 yield
return currFigure;
1891 startPoint = currPoint;
1892 currFigure =
new List<Point>();
1895 currFigure.Add(currPoint);
1899 currFigure.Add(startPoint);
1900 yield
return currFigure;
1907 yield
return currFigure;
1919 if (!(resolution > 0))
1921 throw new ArgumentOutOfRangeException(nameof(resolution), resolution,
"The resolution must be greater than 0!");
1927 List<Point> currFigure =
null;
1928 bool returned =
true;
1930 for (
int i = 0; i < this.
Segments.Count; i++)
1941 yield
return currFigure;
1944 startPoint = currPoint;
1945 currFigure =
new List<Point>();
1952 currFigure.Add(
new Point(-tangent.
Y, tangent.
X));
1956 currFigure.Add(
new Point());
1963 currFigure.Add(
new Point(-tangent.
Y, tangent.
X));
1967 previousPoint = currPoint;
1973 if (!startPoint.
IsEqual(previousPoint, 1e-4))
1976 normal =
new Point(-tangent.
Y, tangent.
X);
1980 normal = currFigure[currFigure.Count - 1];
1983 currFigure.Add(normal);
1984 currFigure[0] =
new Point((currFigure[1].X + normal.
X) * 0.5, (currFigure[1].Y + normal.
Y) * 0.5).
Normalize();
1986 yield
return currFigure;
1993 yield
return currFigure;
1999 private enum VertexType
2001 Start, End, Regular, Split, Merge
2010 public IEnumerable<GraphicsPath>
Triangulate(
double resolution,
bool clockwise)
2012 double shiftAmount = 0.01 * resolution;
2014 if (!(resolution > 0))
2016 throw new ArgumentOutOfRangeException(nameof(resolution), resolution,
"The resolution must be greater than 0!");
2021 List<Point> vertices =
new List<Point>();
2022 List<List<int>> vertexEdges =
new List<List<int>>();
2023 List<(int, int)> edges =
new List<(
int,
int)>();
2024 int lastStartingPoint = -1;
2025 int lastSegmentEnd = -1;
2028 foreach (
Segment seg
in linearisedPath.Segments)
2030 if (seg is MoveSegment)
2032 vertices.Add(seg.
Point);
2033 vertexEdges.Add(
new List<int>(2));
2034 lastStartingPoint = vertices.Count - 1;
2035 lastSegmentEnd = vertices.Count - 1;
2037 else if (seg is LineSegment)
2039 if (!vertices[lastSegmentEnd].IsEqual(seg.
Point, 1e-4))
2041 vertices.Add(seg.
Point);
2042 vertexEdges.Add(
new List<int>(2));
2043 edges.Add((lastSegmentEnd, vertices.Count - 1));
2044 area += (seg.
Point.
X - vertices[lastSegmentEnd].X) * (seg.
Point.
Y + vertices[lastSegmentEnd].Y);
2045 vertexEdges[lastSegmentEnd].Add(edges.Count - 1);
2046 vertexEdges[vertices.Count - 1].Add(edges.Count - 1);
2047 lastSegmentEnd = vertices.Count - 1;
2050 else if (seg is CloseSegment)
2052 if (!vertices[lastSegmentEnd].IsEqual(vertices[lastStartingPoint], 1e-4))
2054 edges.Add((lastSegmentEnd, lastStartingPoint));
2055 area += (vertices[lastStartingPoint].X - vertices[lastSegmentEnd].X) * (vertices[lastStartingPoint].Y + vertices[lastSegmentEnd].Y);
2056 vertexEdges[lastSegmentEnd].Add(edges.Count - 1);
2057 vertexEdges[lastStartingPoint].Add(edges.Count - 1);
2061 vertices.RemoveAt(lastSegmentEnd);
2062 vertexEdges.RemoveAt(lastSegmentEnd);
2064 for (
int i = 0; i < edges.Count; i++)
2066 if (edges[i].Item1 == lastSegmentEnd)
2068 edges[i] = (lastStartingPoint, edges[i].Item2);
2069 vertexEdges[lastStartingPoint].Add(i);
2071 else if (edges[i].Item2 == lastSegmentEnd)
2073 edges[i] = (edges[i].Item1, lastStartingPoint);
2074 vertexEdges[lastStartingPoint].Add(i);
2079 lastStartingPoint = -1;
2080 lastSegmentEnd = -1;
2084 if (vertices.Count < 3)
2089 bool isAntiClockwise = area > 0;
2095 return Math.Sign(a.
Y - b.
Y);
2099 return Math.Sign(a.
X - b.
X);
2103 Dictionary<double, int> yCoordinates =
new Dictionary<double, int>();
2104 Dictionary<double, int> yShiftCount =
new Dictionary<double, int>();
2106 foreach (
Point pt
in vertices)
2108 if (yCoordinates.ContainsKey(pt.
Y))
2110 yCoordinates[pt.
Y]++;
2114 yCoordinates[pt.
Y] = 1;
2115 yShiftCount[pt.
Y] = 0;
2119 HashSet<double> yS =
new HashSet<double>(from el in yCoordinates select el.Key);
2121 for (
int i = 0; i < vertices.Count; i++)
2123 if (yCoordinates[vertices[i].Y] > 1)
2125 int shiftCount = yShiftCount[vertices[i].Y];
2127 double targetCoordinate;
2133 targetCoordinate = vertices[i].Y + (2 * (shiftCount % 2) - 1) * (1 - Math.Pow(0.5, (shiftCount - 1) / 2 + 1)) * shiftAmount;
2135 while (yS.Contains(targetCoordinate));
2137 yS.Add(targetCoordinate);
2138 yCoordinates[vertices[i].Y]--;
2139 yShiftCount[vertices[i].Y] = shiftCount;
2140 vertices[i] =
new Point(vertices[i].X, targetCoordinate);
2145 Queue<int> sortedVertices =
new Queue<int>(Enumerable.Range(0, vertices.Count).OrderBy(i => vertices[i], Comparer<Point>.Create(compareVertices)));
2147 VertexType[] vertexTypes =
new VertexType[vertices.Count];
2149 List<(int, int)> exploredEdges =
new List<(
int,
int)>();
2150 List<int> helpers =
new List<int>();
2151 List<(int, int)> diagonals =
new List<(
int,
int)>();
2152 int[] nexts =
new int[vertices.Count];
2153 int[] prevs =
new int[vertices.Count];
2155 while (sortedVertices.Count > 0)
2157 int vertex = sortedVertices.Dequeue();
2159 Point pt = vertices[vertex];
2161 (int, int) edge1 = edges[vertexEdges[vertex][0]];
2162 (int, int) edge2 = edges[vertexEdges[vertex][1]];
2164 int neighbour1 = edge1.Item1 != vertex ? edge1.Item1 : edge1.Item2;
2165 int neighbour2 = edge2.Item1 != vertex ? edge2.Item1 : edge2.Item2;
2167 int minNeighbour = Math.
Min(neighbour1, neighbour2);
2168 int maxNeighbour = Math.
Max(neighbour1, neighbour2);
2172 if (vertex - minNeighbour == 1 && maxNeighbour - vertex == 1)
2174 prev = minNeighbour;
2175 next = maxNeighbour;
2177 else if ((minNeighbour - vertex == 1 && maxNeighbour - vertex > 1) || vertex - maxNeighbour == 1 && vertex - minNeighbour > 1)
2179 prev = maxNeighbour;
2180 next = minNeighbour;
2184 throw new InvalidOperationException(
"Could not make sense of the ordering of the vertices!");
2187 nexts[vertex] = next;
2188 prevs[vertex] = prev;
2190 Point prevPoint = vertices[prev];
2191 Point nextPoint = vertices[next];
2193 double angle = Math.Atan2(prevPoint.
Y - pt.
Y, prevPoint.
X - pt.
X) - Math.Atan2(nextPoint.
Y - pt.
Y, nextPoint.
X - pt.
X);
2197 angle += 2 * Math.PI;
2200 VertexType vertexType;
2202 if (prevPoint.
Y >= pt.
Y && nextPoint.
Y >= pt.
Y && angle < Math.PI)
2204 vertexType = VertexType.Start;
2206 else if (prevPoint.
Y >= pt.
Y && nextPoint.
Y >= pt.
Y && angle > Math.PI)
2208 vertexType = VertexType.Split;
2210 else if (prevPoint.
Y <= pt.
Y && nextPoint.
Y <= pt.
Y && angle < Math.PI)
2212 vertexType = VertexType.End;
2214 else if (prevPoint.
Y <= pt.
Y && nextPoint.
Y <= pt.
Y && angle > Math.PI)
2216 vertexType = VertexType.Merge;
2220 vertexType = VertexType.Regular;
2223 vertexTypes[vertex] = vertexType;
2227 if (vertexType == VertexType.Start)
2229 exploredEdges.Add((prev, vertex));
2230 helpers.Add(vertex);
2234 else if (vertexType == VertexType.End)
2238 for (
int i = exploredEdges.Count - 1; i >= 0; i--)
2240 if (exploredEdges[i].Item1 == vertex && exploredEdges[i].Item2 == next)
2249 if (vertexTypes[helpers[eiM1]] == VertexType.Merge)
2251 diagonals.Add((helpers[eiM1], vertex));
2254 exploredEdges.RemoveAt(eiM1);
2255 helpers.RemoveAt(eiM1);
2258 else if (vertexType == VertexType.Split)
2260 (int, int) ej = (-1, -1);
2263 double xJ =
double.MinValue;
2265 for (
int i = 0; i < exploredEdges.Count; i++)
2267 if ((vertices[exploredEdges[i].Item1].Y <= pt.
Y && vertices[exploredEdges[i].Item2].Y >= pt.
Y) || (vertices[exploredEdges[i].Item1].Y >= pt.
Y && vertices[exploredEdges[i].Item2].Y <= pt.
Y))
2269 double dy = pt.
Y - vertices[exploredEdges[i].Item1].Y;
2270 double dx = dy * (vertices[exploredEdges[i].Item2].X - vertices[exploredEdges[i].Item1].X) / (vertices[exploredEdges[i].Item2].Y - vertices[exploredEdges[i].Item1].Y);
2272 double x = dx + vertices[exploredEdges[i].Item1].X;
2274 if (x < pt.X && x >= xJ)
2277 ej = exploredEdges[i];
2285 diagonals.Add((helpers[ejIndex], vertex));
2287 helpers[ejIndex] = vertex;
2289 exploredEdges.Add((prev, vertex));
2290 helpers.Add(vertex);
2349 else if (vertexType == VertexType.Merge)
2353 for (
int i = exploredEdges.Count - 1; i >= 0; i--)
2355 if (exploredEdges[i].Item1 == vertex && exploredEdges[i].Item2 == next)
2364 if (vertexTypes[helpers[eiM1]] == VertexType.Merge)
2366 diagonals.Add((helpers[eiM1], vertex));
2369 exploredEdges.RemoveAt(eiM1);
2370 helpers.RemoveAt(eiM1);
2373 (int, int) ej = (-1, -1);
2376 double xJ =
double.MinValue;
2378 for (
int i = 0; i < exploredEdges.Count; i++)
2380 if ((vertices[exploredEdges[i].Item1].Y <= pt.
Y && vertices[exploredEdges[i].Item2].Y >= pt.
Y) || (vertices[exploredEdges[i].Item1].Y >= pt.
Y && vertices[exploredEdges[i].Item2].Y <= pt.
Y))
2382 double dy = pt.
Y - vertices[exploredEdges[i].Item1].Y;
2383 double dx = dy * (vertices[exploredEdges[i].Item2].X - vertices[exploredEdges[i].Item1].X) / (vertices[exploredEdges[i].Item2].Y - vertices[exploredEdges[i].Item1].Y);
2385 double x = dx + vertices[exploredEdges[i].Item1].X;
2387 if (x < pt.X && x >= xJ)
2390 ej = exploredEdges[i];
2398 if (vertexTypes[helpers[ejIndex]] == VertexType.Merge)
2400 diagonals.Add((helpers[ejIndex], vertex));
2403 helpers[ejIndex] = vertex;
2463 else if (vertexType == VertexType.Regular)
2465 if ((isAntiClockwise && (prevPoint.
Y < pt.
Y || pt.
Y < nextPoint.
Y)) || (!isAntiClockwise && (prevPoint.
Y > pt.
Y || pt.
Y > nextPoint.
Y)))
2469 for (
int i = exploredEdges.Count - 1; i >= 0; i--)
2471 if (exploredEdges[i].Item1 == vertex && exploredEdges[i].Item2 == next)
2480 if (vertexTypes[helpers[eiM1]] == VertexType.Merge)
2482 diagonals.Add((helpers[eiM1], vertex));
2485 exploredEdges.RemoveAt(eiM1);
2486 helpers.RemoveAt(eiM1);
2489 exploredEdges.Add((prev, vertex));
2490 helpers.Add(vertex);
2494 (int, int) ej = (-1, -1);
2497 double xJ =
double.MinValue;
2499 for (
int i = 0; i < exploredEdges.Count; i++)
2501 if ((vertices[exploredEdges[i].Item1].Y <= pt.
Y && vertices[exploredEdges[i].Item2].Y >= pt.
Y) || (vertices[exploredEdges[i].Item1].Y >= pt.
Y && vertices[exploredEdges[i].Item2].Y <= pt.
Y))
2503 double dy = pt.
Y - vertices[exploredEdges[i].Item1].Y;
2504 double dx = dy * (vertices[exploredEdges[i].Item2].X - vertices[exploredEdges[i].Item1].X) / (vertices[exploredEdges[i].Item2].Y - vertices[exploredEdges[i].Item1].Y);
2506 double x = dx + vertices[exploredEdges[i].Item1].X;
2508 if (x < pt.X && x >= xJ)
2511 ej = exploredEdges[i];
2519 if (vertexTypes[helpers[ejIndex]] == VertexType.Merge)
2521 diagonals.Add((helpers[ejIndex], vertex));
2524 helpers[ejIndex] = vertex;
2530 for (
int i = diagonals.Count - 1; i >= 0; i--)
2532 for (
int j = 0; j < edges.Count; j++)
2534 if (CompareEdges(diagonals[i], edges[j]))
2536 diagonals.RemoveAt(i);
2542 List<List<(int, int)>> polygons = SplitPolygons(edges, diagonals, vertices, isAntiClockwise ? prevs : nexts);
2544 int[] directions =
new int[vertices.Count];
2548 foreach (List<(
int,
int)> polygon in polygons)
2550 foreach (
GraphicsPath pth
in TriangulateMonotone(vertices, polygon, directions, clockwise ? -1 : 1))
2559 private static bool CompareEdges((
int,
int) edge1, (
int,
int) edge2)
2561 return (edge1.Item1 == edge2.Item1 && edge1.Item2 == edge2.Item2) || (edge1.Item1 == edge2.Item2 && edge1.Item2 == edge2.Item1);
2564 private static List<List<(int, int)>> SplitPolygons(List<(
int,
int)> edges, List<(int, int)> diagonals, List<Point> vertices,
int[] nexts)
2566 List<List<(int, int)>> polygons =
new List<List<(
int,
int)>>();
2568 List<int>[] outPaths =
new List<int>[vertices.Count];
2570 for (
int i = 0; i < edges.Count; i++)
2572 if (outPaths[edges[i].Item1] ==
null)
2574 outPaths[edges[i].Item1] =
new List<int>();
2577 if (outPaths[edges[i].Item2] ==
null)
2579 outPaths[edges[i].Item2] =
new List<int>();
2582 outPaths[edges[i].Item1].Add(edges[i].Item2);
2583 outPaths[edges[i].Item2].Add(edges[i].Item1);
2586 for (
int i = 0; i < diagonals.Count; i++)
2588 if (outPaths[diagonals[i].Item1] ==
null)
2590 outPaths[diagonals[i].Item1] =
new List<int>();
2593 if (outPaths[diagonals[i].Item2] ==
null)
2595 outPaths[diagonals[i].Item2] =
new List<int>();
2598 outPaths[diagonals[i].Item1].Add(diagonals[i].Item2);
2599 outPaths[diagonals[i].Item1].Add(diagonals[i].Item2);
2600 outPaths[diagonals[i].Item2].Add(diagonals[i].Item1);
2601 outPaths[diagonals[i].Item2].Add(diagonals[i].Item1);
2604 List<int> activeVertices = (from el in Enumerable.Range(0, outPaths.Length) where outPaths[el] !=
null && outPaths[el].Count > 0 select el).ToList();
2606 int[] newNexts =
new int[nexts.Length];
2608 for (
int i = 0; i < nexts.Length; i++)
2610 if (activeVertices.Contains(i))
2612 int currNext = nexts[i];
2613 while (!outPaths[i].Contains(currNext))
2615 currNext = nexts[currNext];
2617 newNexts[i] = currNext;
2625 while (activeVertices.Count > 0)
2627 List<(int, int)> polygon =
new List<(
int,
int)>();
2629 int startPoint = activeVertices.Min();
2631 if (!outPaths[startPoint].Contains(newNexts[startPoint]))
2633 throw new InvalidOperationException(
"Missing edge!");
2636 int prevVertex = startPoint;
2637 int currVertex = newNexts[startPoint];
2639 outPaths[startPoint].Remove(currVertex);
2640 outPaths[currVertex].Remove(startPoint);
2641 polygon.Add((startPoint, currVertex));
2643 while (currVertex != startPoint)
2645 Point currPoint = vertices[currVertex];
2646 Point prevPoint = vertices[prevVertex];
2648 double angleIncoming = Math.Atan2(prevPoint.Y - currPoint.Y, prevPoint.X - currPoint.X);
2649 if (angleIncoming < 0)
2651 angleIncoming += 2 * Math.PI;
2654 double maxAngle =
double.MinValue;
2655 int candidateVertex = -1;
2657 for (
int i = 0; i < outPaths[currVertex].Count; i++)
2659 double angleI = Math.Atan2(vertices[outPaths[currVertex][i]].Y - currPoint.Y, vertices[outPaths[currVertex][i]].X - currPoint.X);
2662 angleI += 2 * Math.PI;
2664 angleI -= angleIncoming;
2667 angleI += 2 * Math.PI;
2670 if (angleI > maxAngle)
2672 candidateVertex = outPaths[currVertex][i];
2677 outPaths[currVertex].Remove(candidateVertex);
2678 outPaths[candidateVertex].Remove(currVertex);
2679 polygon.Add((currVertex, candidateVertex));
2681 prevVertex = currVertex;
2682 currVertex = candidateVertex;
2685 polygons.Add(polygon);
2686 activeVertices = (from el in Enumerable.Range(0, outPaths.Length) where outPaths[el] !=
null && outPaths[el].Count > 0 select el).ToList();
2688 if (activeVertices.Contains(currVertex))
2690 int currNext = newNexts[currVertex];
2691 while (!outPaths[currVertex].Contains(currNext))
2693 currNext = newNexts[currNext];
2695 newNexts[currVertex] = currNext;
2698 if (activeVertices.Contains(prevVertex))
2700 int currNext = newNexts[prevVertex];
2701 while (!outPaths[prevVertex].Contains(currNext))
2703 currNext = newNexts[currNext];
2705 newNexts[prevVertex] = currNext;
2712 private static IEnumerable<GraphicsPath> TriangulateMonotone(List<Point> vertices, List<(
int,
int)> edges,
int[] directions,
int targetSign)
2714 int getDirection((
int,
int) edge)
2716 if (vertices[edge.Item2].Y != vertices[edge.Item1].Y)
2718 return Math.Sign(vertices[edge.Item2].Y - vertices[edge.Item1].Y);
2722 for (
int i = 0; i < edges.Count; i++)
2724 if (edges[i].Item2 == edge.Item1)
2726 return getDirection(edges[i]);
2731 throw new InvalidOperationException(
"Unknown edge direction!");
2735 for (
int i = 0; i < edges.Count; i++)
2737 directions[edges[i].Item1] = getDirection(edges[i]);
2740 int[] sortedVertices = (from el in edges select el.Item1).OrderBy(a => a, Comparer<int>.Create((a, b) =>
2742 if (vertices[a].Y != vertices[b].Y)
2744 return Math.Sign(vertices[a].Y - vertices[b].Y);
2748 return Math.Sign(vertices[a].X - vertices[b].X);
2752 List<(int, int)> diagonals =
new List<(
int,
int)>();
2754 Stack<int> stack =
new Stack<int>();
2756 stack.Push(sortedVertices[0]);
2757 stack.Push(sortedVertices[1]);
2759 for (
int i = 2; i < sortedVertices.Length - 1; i++)
2761 int onTop = stack.Peek();
2763 if (directions[sortedVertices[i]] != directions[onTop])
2765 while (stack.Count > 1)
2767 int v = stack.Pop();
2769 diagonals.Add((v, sortedVertices[i]));
2774 stack.Push(sortedVertices[i - 1]);
2775 stack.Push(sortedVertices[i]);
2779 int lastPopped = stack.Pop();
2781 bool shouldContinue =
true;
2783 while (shouldContinue && stack.Count > 0)
2785 int currVert = stack.Peek();
2787 double areaSign = Math.Sign((vertices[currVert].X - vertices[lastPopped].X) * (vertices[sortedVertices[i]].Y - vertices[lastPopped].Y) - (vertices[currVert].Y - vertices[lastPopped].Y) * (vertices[sortedVertices[i]].X - vertices[lastPopped].X));
2789 double dirSign = Math.Sign(vertices[currVert].X - vertices[lastPopped].X);
2791 if (areaSign * dirSign > 0)
2793 lastPopped = stack.Pop();
2795 diagonals.Add((currVert, sortedVertices[i]));
2799 shouldContinue =
false;
2803 stack.Push(lastPopped);
2804 stack.Push(sortedVertices[i]);
2810 while (stack.Count > 1)
2812 int v = stack.Pop();
2814 diagonals.Add((v, sortedVertices[sortedVertices.Length - 1]));
2817 List<int>[] connections =
new List<int>[vertices.Count];
2819 for (
int i = 0; i < edges.Count; i++)
2821 connections[edges[i].Item1] =
new List<int>();
2824 for (
int i = 0; i < edges.Count; i++)
2826 connections[edges[i].Item1].Add(edges[i].Item2);
2827 connections[edges[i].Item2].Add(edges[i].Item1);
2830 for (
int i = 0; i < diagonals.Count; i++)
2832 connections[diagonals[i].Item1].Add(diagonals[i].Item2);
2833 connections[diagonals[i].Item1].Add(diagonals[i].Item2);
2835 connections[diagonals[i].Item2].Add(diagonals[i].Item1);
2836 connections[diagonals[i].Item2].Add(diagonals[i].Item1);
2839 int totalTriangles = (edges.Count + diagonals.Count * 2) / 3;
2841 List<List<(int, int)>> polygons =
new List<List<(
int,
int)>>();
2843 while (polygons.Count < totalTriangles)
2848 for (
int i = 0; i < connections.Length; i++)
2850 if (connections[i] !=
null && connections[i].Count > 0)
2853 p2 = connections[i][0];
2855 connections[i].Remove(p2);
2856 connections[p2].Remove(i);
2863 for (
int i = 0; i < connections[p1].Count; i++)
2865 if (connections[connections[p1][i]].Contains(p2))
2867 p3 = connections[p1][i];
2868 connections[p1].Remove(p3);
2869 connections[p2].Remove(p3);
2870 connections[p3].Remove(p1);
2871 connections[p3].Remove(p2);
2876 int sign = Math.Sign((vertices[p1].X - vertices[p2].X) * (vertices[p3].Y - vertices[p2].Y) - (vertices[p1].Y - vertices[p2].Y) * (vertices[p3].X - vertices[p2].X));
2878 if (sign == targetSign)
2880 polygons.Add(
new List<(
int,
int)>() { (p1, p2), (p2, p3), (p3, p1) });
2884 polygons.Add(
new List<(
int,
int)>() { (p1, p3), (p3, p2), (p2, p1) });
2888 foreach (List<(
int,
int)> polygon in polygons)
2890 GraphicsPath polygonPath =
new GraphicsPath();
2891 foreach ((
int,
int) edge in polygon)
2893 if (polygonPath.Segments.Count == 0)
2895 polygonPath.MoveTo(vertices[edge.Item1]);
2898 polygonPath.LineTo(vertices[edge.Item2]);
2901 yield
return polygonPath;
2916 tbr.Segments.AddRange(seg.
Transform(transformationFunction));
2933 Point min =
new Point(
double.MaxValue,
double.MaxValue);
2934 Point max =
new Point(
double.MinValue,
double.MinValue);
2939 for (
int i = 0; i < this.
Segments.Count; i++)
2944 currPoint = this.
Segments[i].Point;
2945 figureStartPoint = this.
Segments[i].Point;
2952 currPoint = this.
Segments[i].Point;
2956 currPoint = this.
Segments[i].Point;
2957 figureStartPoint = this.
Segments[i].Point;
2963 ArcSegment seg = (ArcSegment)this.
Segments[i];
2967 figureStartPoint =
new Point(seg.Points[0].X + Math.Cos(seg.StartAngle) * seg.Radius, seg.Points[0].Y + Math.Sin(seg.StartAngle) * seg.Radius);
2968 currPoint = figureStartPoint;
2974 double theta1 = seg.StartAngle;
2975 double theta2 = seg.EndAngle;
2977 if (theta1 > theta2)
2979 double temp = theta1;
2984 theta1 /= 2 * Math.PI;
2985 theta2 /= 2 * Math.PI;
2987 int minAngle = (int)Math.
Min(0, Math.Floor(theta1)) * 4;
2988 int maxAngle = (int)Math.
Max(1, Math.Ceiling(theta2)) * 4;
2994 bool bottom =
false;
2998 for (
int j = minAngle; j < maxAngle; j++)
3000 if (theta1 <= j && theta2 >= j)
3022 Point p =
new Point(seg.Points[0].X + seg.Radius, seg.Points[0].Y);
3029 Point p =
new Point(seg.Points[0].X, seg.Points[0].Y + seg.Radius);
3036 Point p =
new Point(seg.Points[0].X - seg.Radius, seg.Points[0].Y);
3043 Point p =
new Point(seg.Points[0].X, seg.Points[0].Y - seg.Radius);
3051 currPoint = this.
Segments[i].Point;
3054 currPoint = figureStartPoint;
3059 currPoint = this.
Segments[i].Points[0];
3060 figureStartPoint = this.
Segments[i].Points[0];
3067 double aX = -currPoint.
X + 3 * this.
Segments[i].Points[0].X - 3 * this.
Segments[i].Points[1].X + this.
Segments[i].Point.X;
3068 double bX = 2 * (currPoint.
X - 2 * this.
Segments[i].Points[0].X + this.
Segments[i].Points[1].X);
3069 double cX = this.
Segments[i].Points[0].X - currPoint.
X;
3074 if (Math.Abs(aX) < 1e-5)
3076 if (Math.Abs(bX) >= 1e-5)
3089 double delta = bX * bX - 4 * aX * cX;
3093 delta = Math.Max(delta, 0);
3095 delta = Math.Sqrt(delta);
3096 t1X = (-bX + delta) / (2 * aX);
3097 t2X = (-bX - delta) / (2 * aX);
3106 if (t1X >= 0 && t1X <= 1)
3108 Point p1 = ((CubicBezierSegment)this.
Segments[i]).GetBezierPointAt(currPoint, t1X);
3113 if (t2X >= 0 && t2X <= 1)
3115 Point p2 = ((CubicBezierSegment)this.
Segments[i]).GetBezierPointAt(currPoint, t2X);
3122 double aY = -currPoint.
Y + 3 * this.
Segments[i].Points[0].Y - 3 * this.
Segments[i].Points[1].Y + this.
Segments[i].Point.Y;
3123 double bY = 2 * (currPoint.
Y - 2 * this.
Segments[i].Points[0].Y + this.
Segments[i].Points[1].Y);
3124 double cY = this.
Segments[i].Points[0].Y - currPoint.
Y;
3129 if (Math.Abs(aY) < 1e-5)
3131 if (Math.Abs(bY) >= 1e-5)
3144 double delta = bY * bY - 4 * aY * cY;
3148 delta = Math.Max(delta, 0);
3150 delta = Math.Sqrt(delta);
3151 t1Y = (-bY + delta) / (2 * aY);
3152 t2Y = (-bY - delta) / (2 * aY);
3161 if (t1Y >= 0 && t1Y <= 1)
3163 Point p1 = ((CubicBezierSegment)this.
Segments[i]).GetBezierPointAt(currPoint, t1Y);
3168 if (t2Y >= 0 && t2Y <= 1)
3170 Point p2 = ((CubicBezierSegment)this.
Segments[i]).GetBezierPointAt(currPoint, t2Y);
3176 currPoint = this.
Segments[i].Point;
3184 return cachedBounds;