Pangolin
Header-only C++20 plane computational geometry library
Loading...
Searching...
No Matches
transformations.hpp
Go to the documentation of this file.
1#pragma once
2
3#include "implementation/io.hpp"
4
11
12
13namespace pgl {
14
15// -----------------------------------------------------------------------------
16// Point
17
18template <class Number, class Label>
22
23template <class Number, class Label>
24template<PointConcept OtherPoint>
25constexpr Point<Number, Label>& Point<Number, Label>::operator+=(const OtherPoint& other) {
26 coords_[0] += detail::asNumber<Number>(other[0]);
27 coords_[1] += detail::asNumber<Number>(other[1]);
28 return *this;
29}
30
31template <class Number, class Label>
32template<PointConcept OtherPoint>
33constexpr Point<Number, Label>& Point<Number, Label>::operator-=(const OtherPoint& other) {
34 coords_[0] -= detail::asNumber<Number>(other[0]);
35 coords_[1] -= detail::asNumber<Number>(other[1]);
36 return *this;
37}
38
39template <class Number, class Label>
40template <class OtherNumber>
41constexpr Point<Number, Label>& Point<Number, Label>::operator*=(const OtherNumber scalar) {
42 coords_[0] *= detail::asNumber<Number>(scalar);
43 coords_[1] *= detail::asNumber<Number>(scalar);
44 return *this;
45}
46
47template <class Number, class Label>
48template <class OtherNumber>
49constexpr Point<Number, Label>& Point<Number, Label>::operator/=(const OtherNumber scalar) {
50 coords_[0] /= detail::asNumber<Number>(scalar);
51 coords_[1] /= detail::asNumber<Number>(scalar);
52 return *this;
53}
54
55template <class Number, class Label>
59
60template <class Number, class Label>
61constexpr Point<Number, Label> Point<Number, Label>::rotated90(int k) const {
62 switch (((k % 4) + 4) % 4) {
63 case 1: return Point(-y(), x());
64 case 2: return Point(-x(), -y());
65 case 3: return Point( y(), -x());
66 default: return Point(x(), y());
67 }
68}
69
70template <class Number, class Label>
71constexpr void Point<Number, Label>::rotate90(int k) {
72 switch (((k % 4) + 4) % 4) {
73 case 1: { auto tmp = x(); x() = -y(); y() = tmp; break; }
74 case 2: { x() = -x(); y() = -y(); break; }
75 case 3: { auto tmp = x(); x() = y(); y() = -tmp; break; }
76 }
77}
78
79template <class Number, class Label>
80template <class OtherNumber>
81constexpr Point<Number, Label> Point<Number, Label>::scaledUpX(const OtherNumber scalar) const {
82 return Point<Number, Label>(x() * scalar, y());
83}
84
85template <class Number, class Label>
86template <class OtherNumber>
87constexpr void Point<Number, Label>::scaleUpX(const OtherNumber scalar) {
88 coords_[0] *= detail::asNumber<Number>(scalar);
89}
90
91template <class Number, class Label>
92template <class OtherNumber>
93constexpr Point<Number, Label> Point<Number, Label>::scaledUpY(const OtherNumber scalar) const {
94 return Point<Number, Label>(x(), y() * scalar);
95}
96
97template <class Number, class Label>
98template <class OtherNumber>
99constexpr void Point<Number, Label>::scaleUpY(const OtherNumber scalar) {
100 coords_[1] *= detail::asNumber<Number>(scalar);
101}
102
103template <class Number, class Label>
104template <class OtherNumber>
105constexpr Point<Number, Label> Point<Number, Label>::scaledDownX(const OtherNumber scalar) const {
106 return Point<Number, Label>(x() / scalar, y());
107}
108
109template <class Number, class Label>
110template <class OtherNumber>
111constexpr void Point<Number, Label>::scaleDownX(const OtherNumber scalar) {
112 coords_[0] /= detail::asNumber<Number>(scalar);
113}
114
115template <class Number, class Label>
116template <class OtherNumber>
117constexpr Point<Number, Label> Point<Number, Label>::scaledDownY(const OtherNumber scalar) const {
118 return Point<Number, Label>(x(), y() / scalar);
119}
120
121template <class Number, class Label>
122template <class OtherNumber>
123constexpr void Point<Number, Label>::scaleDownY(const OtherNumber scalar) {
124 coords_[1] /= detail::asNumber<Number>(scalar);
125}
126
127// operator+ is the Minkowski sum; see implementation/minkowski.hpp.
128
129template <class LeftNumber, class LeftLabel, class RightNumber, class RightLabel>
130constexpr auto operator-(const Point<LeftNumber, LeftLabel>& left, const Point<RightNumber, RightLabel>& right) {
131 using ResultNumber = std::common_type_t<LeftNumber, RightNumber>;
132 return Point<ResultNumber, LeftLabel>(
133 detail::asNumber<ResultNumber>(left.x()) - detail::asNumber<ResultNumber>(right.x()),
134 detail::asNumber<ResultNumber>(left.y()) - detail::asNumber<ResultNumber>(right.y()));
135}
136
137template <class Number, class Label, class Scalar>
138 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
139constexpr auto operator*(const Point<Number, Label>& point, const Scalar& scalar) {
140 using ResultNumber = std::common_type_t<Number, Scalar>;
141 return Point<ResultNumber, Label>(
142 detail::asNumber<ResultNumber>(point.x()) * detail::asNumber<ResultNumber>(scalar),
143 detail::asNumber<ResultNumber>(point.y()) * detail::asNumber<ResultNumber>(scalar));
144}
145
146template <class Scalar, class Number, class Label>
147 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
148constexpr auto operator*(const Scalar& scalar, const Point<Number, Label>& point) {
149 return point * scalar;
150}
151
152template <class Number, class Label, class Scalar>
153 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
154constexpr auto operator/(const Point<Number, Label>& point, const Scalar& scalar) {
155 using ResultNumber = std::common_type_t<Number, Scalar>;
156 return Point<ResultNumber, Label>(
157 detail::asNumber<ResultNumber>(point.x()) / detail::asNumber<ResultNumber>(scalar),
158 detail::asNumber<ResultNumber>(point.y()) / detail::asNumber<ResultNumber>(scalar));
159}
160
161// -----------------------------------------------------------------------------
162// Segment
163
164template <class PointType, class LabelType>
165template<PointConcept OtherPoint>
166constexpr Segment<PointType, LabelType>& Segment<PointType, LabelType>::operator+=(const OtherPoint& translation) {
167 points_[0] += translation;
168 points_[1] += translation;
169 return *this;
170}
171
172template <class PointType, class LabelType>
173template<PointConcept OtherPoint>
174constexpr Segment<PointType, LabelType>& Segment<PointType, LabelType>::operator-=(const OtherPoint& translation) {
175 points_[0] -= translation;
176 points_[1] -= translation;
177 return *this;
178}
179
180template <class PointType, class LabelType>
181template <class Scalar>
182 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
183constexpr Segment<PointType, LabelType>& Segment<PointType, LabelType>::operator*=(const Scalar& scalar) {
184 points_[0] *= scalar;
185 points_[1] *= scalar;
186 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
187 return *this;
188}
189
190template <class PointType, class LabelType>
191template <class Scalar>
192 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
193constexpr Segment<PointType, LabelType>& Segment<PointType, LabelType>::operator/=(const Scalar& scalar) {
194 points_[0] /= scalar;
195 points_[1] /= scalar;
196 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
197 return *this;
198}
199
200template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
201constexpr auto operator-(const Segment<PointType, LabelType>& segment, const Point<TranslationNumber, TranslationLabel>& translation) {
202 const auto first = segment.min() - translation;
203 const auto second = segment.max() - translation;
204 return Segment<std::decay_t<decltype(first)>, LabelType>(first, second);
205}
206
207template <class PointType, class LabelType, class Scalar>
208 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
209constexpr auto operator*(const Segment<PointType, LabelType>& segment, const Scalar& scalar) {
210 const auto first = segment.min() * scalar;
211 const auto second = segment.max() * scalar;
212 return Segment<std::decay_t<decltype(first)>, LabelType>(first, second);
213}
214
215template <class Scalar, class PointType, class LabelType>
216 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
217constexpr auto operator*(const Scalar& scalar, const Segment<PointType, LabelType>& segment) {
218 return segment * scalar;
219}
220
221template <class PointType, class LabelType, class Scalar>
222 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
223constexpr auto operator/(const Segment<PointType, LabelType>& segment, const Scalar& scalar) {
224 const auto first = segment.min() / scalar;
225 const auto second = segment.max() / scalar;
226 return Segment<std::decay_t<decltype(first)>, LabelType>(first, second);
227}
228
229template <class PointType, class LabelType>
233
234template <class PointType, class LabelType>
235constexpr void Segment<PointType, LabelType>::rotate90(int k) {
236 points_[0].rotate90(k);
237 points_[1].rotate90(k);
238 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
239}
240
241template <class PointType, class LabelType>
242template <class OtherNumber>
243constexpr Segment<PointType, LabelType> Segment<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
244 return Segment(min().scaledUpX(scalar), max().scaledUpX(scalar));
245}
246
247template <class PointType, class LabelType>
248template <class OtherNumber>
249constexpr void Segment<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
250 points_[0].scaleUpX(scalar);
251 points_[1].scaleUpX(scalar);
252 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
253}
254
255template <class PointType, class LabelType>
256template <class OtherNumber>
257constexpr Segment<PointType, LabelType> Segment<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
258 return Segment(min().scaledUpY(scalar), max().scaledUpY(scalar));
259}
260
261template <class PointType, class LabelType>
262template <class OtherNumber>
263constexpr void Segment<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
264 points_[0].scaleUpY(scalar);
265 points_[1].scaleUpY(scalar);
266 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
267}
268
269template <class PointType, class LabelType>
270template <class OtherNumber>
271constexpr Segment<PointType, LabelType> Segment<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
272 return Segment(min().scaledDownX(scalar), max().scaledDownX(scalar));
273}
274
275template <class PointType, class LabelType>
276template <class OtherNumber>
277constexpr void Segment<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
278 points_[0].scaleDownX(scalar);
279 points_[1].scaleDownX(scalar);
280 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
281}
282
283template <class PointType, class LabelType>
284template <class OtherNumber>
285constexpr Segment<PointType, LabelType> Segment<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
286 return Segment(min().scaledDownY(scalar), max().scaledDownY(scalar));
287}
288
289template <class PointType, class LabelType>
290template <class OtherNumber>
291constexpr void Segment<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
292 points_[0].scaleDownY(scalar);
293 points_[1].scaleDownY(scalar);
294 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
295}
296
297// -----------------------------------------------------------------------------
298// OrientedSegment
299
300template <class PointType, class LabelType>
301template<PointConcept OtherPoint>
302constexpr OrientedSegment<PointType, LabelType>& OrientedSegment<PointType, LabelType>::operator+=(const OtherPoint& translation) {
303 points_[0] += translation;
304 points_[1] += translation;
305 return *this;
306}
307
308template <class PointType, class LabelType>
309template<PointConcept OtherPoint>
310constexpr OrientedSegment<PointType, LabelType>& OrientedSegment<PointType, LabelType>::operator-=(const OtherPoint& translation) {
311 points_[0] -= translation;
312 points_[1] -= translation;
313 return *this;
314}
315
316template <class PointType, class LabelType>
317template <class Scalar>
318 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
319constexpr OrientedSegment<PointType, LabelType>& OrientedSegment<PointType, LabelType>::operator*=(const Scalar& scalar) {
320 points_[0] *= scalar;
321 points_[1] *= scalar;
322 return *this;
323}
324
325template <class PointType, class LabelType>
326template <class Scalar>
327 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
328constexpr OrientedSegment<PointType, LabelType>& OrientedSegment<PointType, LabelType>::operator/=(const Scalar& scalar) {
329 points_[0] /= scalar;
330 points_[1] /= scalar;
331 return *this;
332}
333
334template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
335constexpr auto operator-(const OrientedSegment<PointType, LabelType>& segment, const Point<TranslationNumber, TranslationLabel>& translation) {
336 const auto first = segment.source() - translation;
337 const auto second = segment.target() - translation;
338 return OrientedSegment<std::decay_t<decltype(first)>, LabelType>(first, second);
339}
340
341template <class PointType, class LabelType, class Scalar>
342 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
343constexpr auto operator*(const OrientedSegment<PointType, LabelType>& segment, const Scalar& scalar) {
344 const auto first = segment.source() * scalar;
345 const auto second = segment.target() * scalar;
346 return OrientedSegment<std::decay_t<decltype(first)>, LabelType>(first, second);
347}
348
349template <class Scalar, class PointType, class LabelType>
350 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
351constexpr auto operator*(const Scalar& scalar, const OrientedSegment<PointType, LabelType>& segment) {
352 return segment * scalar;
353}
354
355template <class PointType, class LabelType, class Scalar>
356 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
357constexpr auto operator/(const OrientedSegment<PointType, LabelType>& segment, const Scalar& scalar) {
358 const auto first = segment.source() / scalar;
359 const auto second = segment.target() / scalar;
360 return OrientedSegment<std::decay_t<decltype(first)>, LabelType>(first, second);
361}
362
363template <class PointType, class LabelType>
367
368template <class PointType, class LabelType>
369constexpr void OrientedSegment<PointType, LabelType>::rotate90(int k) {
370 points_[0].rotate90(k);
371 points_[1].rotate90(k);
372}
373
374template <class PointType, class LabelType>
375template <class OtherNumber>
376constexpr OrientedSegment<PointType, LabelType> OrientedSegment<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
377 return OrientedSegment(source().scaledUpX(scalar), target().scaledUpX(scalar));
378}
379
380template <class PointType, class LabelType>
381template <class OtherNumber>
382constexpr void OrientedSegment<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
383 points_[0].scaleUpX(scalar);
384 points_[1].scaleUpX(scalar);
385}
386
387template <class PointType, class LabelType>
388template <class OtherNumber>
389constexpr OrientedSegment<PointType, LabelType> OrientedSegment<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
390 return OrientedSegment(source().scaledUpY(scalar), target().scaledUpY(scalar));
391}
392
393template <class PointType, class LabelType>
394template <class OtherNumber>
395constexpr void OrientedSegment<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
396 points_[0].scaleUpY(scalar);
397 points_[1].scaleUpY(scalar);
398}
399
400template <class PointType, class LabelType>
401template <class OtherNumber>
405
406template <class PointType, class LabelType>
407template <class OtherNumber>
408constexpr void OrientedSegment<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
409 points_[0].scaleDownX(scalar);
410 points_[1].scaleDownX(scalar);
411}
412
413template <class PointType, class LabelType>
414template <class OtherNumber>
418
419template <class PointType, class LabelType>
420template <class OtherNumber>
421constexpr void OrientedSegment<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
422 points_[0].scaleDownY(scalar);
423 points_[1].scaleDownY(scalar);
424}
425
426// -----------------------------------------------------------------------------
427// Line
428
429template <class PointType, class LabelType>
430template<PointConcept OtherPoint>
431constexpr Line<PointType, LabelType>& Line<PointType, LabelType>::operator+=(const OtherPoint& translation) {
432 points_[0] += translation;
433 points_[1] += translation;
434 return *this;
435}
436
437template <class PointType, class LabelType>
438template<PointConcept OtherPoint>
439constexpr Line<PointType, LabelType>& Line<PointType, LabelType>::operator-=(const OtherPoint& translation) {
440 points_[0] -= translation;
441 points_[1] -= translation;
442 return *this;
443}
444
445template <class PointType, class LabelType>
446template <class Scalar>
447 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
448constexpr Line<PointType, LabelType>& Line<PointType, LabelType>::operator*=(const Scalar& scalar) {
449 points_[0] *= scalar;
450 points_[1] *= scalar;
451 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
452 return *this;
453}
454
455template <class PointType, class LabelType>
456template <class Scalar>
457 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
458constexpr Line<PointType, LabelType>& Line<PointType, LabelType>::operator/=(const Scalar& scalar) {
459 points_[0] /= scalar;
460 points_[1] /= scalar;
461 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
462 return *this;
463}
464
465template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
466constexpr auto operator-(const Line<PointType, LabelType>& line, const Point<TranslationNumber, TranslationLabel>& translation) {
467 const auto first = line.min() - translation;
468 const auto second = line.max() - translation;
469 return Line<std::decay_t<decltype(first)>, LabelType>(first, second);
470}
471
472template <class PointType, class LabelType, class Scalar>
473 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
474constexpr auto operator*(const Line<PointType, LabelType>& line, const Scalar& scalar) {
475 const auto first = line.min() * scalar;
476 const auto second = line.max() * scalar;
477 return Line<std::decay_t<decltype(first)>, LabelType>(first, second);
478}
479
480template <class Scalar, class PointType, class LabelType>
481 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
482constexpr auto operator*(const Scalar& scalar, const Line<PointType, LabelType>& line) {
483 return line * scalar;
484}
485
486template <class PointType, class LabelType, class Scalar>
487 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
488constexpr auto operator/(const Line<PointType, LabelType>& line, const Scalar& scalar) {
489 const auto first = line.min() / scalar;
490 const auto second = line.max() / scalar;
491 return Line<std::decay_t<decltype(first)>, LabelType>(first, second);
492}
493
494template <class PointType, class LabelType>
498
499template <class PointType, class LabelType>
503
504template <class PointType, class LabelType>
508
509template <class PointType, class LabelType>
510constexpr void Line<PointType, LabelType>::rotate90(int k) {
511 points_[0].rotate90(k);
512 points_[1].rotate90(k);
513 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
514}
515
516template <class PointType, class LabelType>
517template <class OtherNumber>
518constexpr Line<PointType, LabelType> Line<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
519 return Line(min().scaledUpX(scalar), max().scaledUpX(scalar));
520}
521
522template <class PointType, class LabelType>
523template <class OtherNumber>
524constexpr void Line<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
525 points_[0].scaleUpX(scalar);
526 points_[1].scaleUpX(scalar);
527 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
528}
529
530template <class PointType, class LabelType>
531template <class OtherNumber>
532constexpr Line<PointType, LabelType> Line<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
533 return Line(min().scaledUpY(scalar), max().scaledUpY(scalar));
534}
535
536template <class PointType, class LabelType>
537template <class OtherNumber>
538constexpr void Line<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
539 points_[0].scaleUpY(scalar);
540 points_[1].scaleUpY(scalar);
541 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
542}
543
544template <class PointType, class LabelType>
545template <class OtherNumber>
546constexpr Line<PointType, LabelType> Line<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
547 return Line(min().scaledDownX(scalar), max().scaledDownX(scalar));
548}
549
550template <class PointType, class LabelType>
551template <class OtherNumber>
552constexpr void Line<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
553 points_[0].scaleDownX(scalar);
554 points_[1].scaleDownX(scalar);
555 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
556}
557
558template <class PointType, class LabelType>
559template <class OtherNumber>
560constexpr Line<PointType, LabelType> Line<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
561 return Line(min().scaledDownY(scalar), max().scaledDownY(scalar));
562}
563
564template <class PointType, class LabelType>
565template <class OtherNumber>
566constexpr void Line<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
567 points_[0].scaleDownY(scalar);
568 points_[1].scaleDownY(scalar);
569 if (points_[1] < points_[0]) std::swap(points_[0], points_[1]);
570}
571
572// -----------------------------------------------------------------------------
573// OrientedLine
574
575template <class PointType, class LabelType>
579
580template <class PointType, class LabelType>
581template<PointConcept OtherPoint>
582constexpr OrientedLine<PointType, LabelType>& OrientedLine<PointType, LabelType>::operator+=(const OtherPoint& translation) {
583 points_[0] += translation;
584 points_[1] += translation;
585 return *this;
586}
587
588template <class PointType, class LabelType>
589template<PointConcept OtherPoint>
590constexpr OrientedLine<PointType, LabelType>& OrientedLine<PointType, LabelType>::operator-=(const OtherPoint& translation) {
591 points_[0] -= translation;
592 points_[1] -= translation;
593 return *this;
594}
595
596template <class PointType, class LabelType>
597template <class Scalar>
598 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
599constexpr OrientedLine<PointType, LabelType>& OrientedLine<PointType, LabelType>::operator*=(const Scalar& scalar) {
600 points_[0] *= scalar;
601 points_[1] *= scalar;
602 return *this;
603}
604
605template <class PointType, class LabelType>
606template <class Scalar>
607 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
608constexpr OrientedLine<PointType, LabelType>& OrientedLine<PointType, LabelType>::operator/=(const Scalar& scalar) {
609 points_[0] /= scalar;
610 points_[1] /= scalar;
611 return *this;
612}
613
614template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
615constexpr auto operator-(const OrientedLine<PointType, LabelType>& line, const Point<TranslationNumber, TranslationLabel>& translation) {
616 const auto first = line.source() - translation;
617 const auto second = line.target() - translation;
618 return OrientedLine<std::decay_t<decltype(first)>, LabelType>(first, second);
619}
620
621template <class PointType, class LabelType, class Scalar>
622 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
623constexpr auto operator*(const OrientedLine<PointType, LabelType>& line, const Scalar& scalar) {
624 const auto first = line.source() * scalar;
625 const auto second = line.target() * scalar;
626 return OrientedLine<std::decay_t<decltype(first)>, LabelType>(first, second);
627}
628
629template <class Scalar, class PointType, class LabelType>
630 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
631constexpr auto operator*(const Scalar& scalar, const OrientedLine<PointType, LabelType>& line) {
632 return line * scalar;
633}
634
635template <class PointType, class LabelType, class Scalar>
636 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
637constexpr auto operator/(const OrientedLine<PointType, LabelType>& line, const Scalar& scalar) {
638 const auto first = line.source() / scalar;
639 const auto second = line.target() / scalar;
640 return OrientedLine<std::decay_t<decltype(first)>, LabelType>(first, second);
641}
642
643template <class PointType, class LabelType>
647
648template <class PointType, class LabelType>
652
653template <class PointType, class LabelType>
657
658template <class PointType, class LabelType>
659constexpr void OrientedLine<PointType, LabelType>::rotate90(int k) {
660 points_[0].rotate90(k);
661 points_[1].rotate90(k);
662}
663
664template <class PointType, class LabelType>
665template <class OtherNumber>
666constexpr OrientedLine<PointType, LabelType> OrientedLine<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
667 return OrientedLine(source().scaledUpX(scalar), target().scaledUpX(scalar));
668}
669
670template <class PointType, class LabelType>
671template <class OtherNumber>
672constexpr void OrientedLine<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
673 points_[0].scaleUpX(scalar);
674 points_[1].scaleUpX(scalar);
675}
676
677template <class PointType, class LabelType>
678template <class OtherNumber>
679constexpr OrientedLine<PointType, LabelType> OrientedLine<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
680 return OrientedLine(source().scaledUpY(scalar), target().scaledUpY(scalar));
681}
682
683template <class PointType, class LabelType>
684template <class OtherNumber>
685constexpr void OrientedLine<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
686 points_[0].scaleUpY(scalar);
687 points_[1].scaleUpY(scalar);
688}
689
690template <class PointType, class LabelType>
691template <class OtherNumber>
692constexpr OrientedLine<PointType, LabelType> OrientedLine<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
693 return OrientedLine(source().scaledDownX(scalar), target().scaledDownX(scalar));
694}
695
696template <class PointType, class LabelType>
697template <class OtherNumber>
698constexpr void OrientedLine<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
699 points_[0].scaleDownX(scalar);
700 points_[1].scaleDownX(scalar);
701}
702
703template <class PointType, class LabelType>
704template <class OtherNumber>
705constexpr OrientedLine<PointType, LabelType> OrientedLine<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
706 return OrientedLine(source().scaledDownY(scalar), target().scaledDownY(scalar));
707}
708
709template <class PointType, class LabelType>
710template <class OtherNumber>
711constexpr void OrientedLine<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
712 points_[0].scaleDownY(scalar);
713 points_[1].scaleDownY(scalar);
714}
715
716namespace detail {
717
730inline constexpr int integralLinePartBits = 12;
731
743template <class Working>
744std::optional<std::array<Working, 4>> integralLinePoints(const std::array<Working, 8>& parts) {
745 const auto& [sourceXNum, sourceXDen, sourceYNum, sourceYDen,
746 targetXNum, targetXDen, targetYNum, targetYDen] = parts;
747
748 // The direction, cleared of denominators and reduced to a primitive integer
749 // vector. Every factor taken out is positive — denominators are, and so is
750 // the gcd — so the direction, hence the orientation, is preserved exactly.
751 //
752 // With both differences in lowest terms the gcd below would factor as
753 // gcd(dxNum, dyNum) * gcd(dxDen, dyDen), which builds the same primitive
754 // components out of two gcds of narrow parts rather than one of the
755 // double-width products. Measured, that is a 1.5x loss, not a win: reducing
756 // the two differences first costs two more gcds, and a gcd here is priced by
757 // how many divisions it runs, not by how wide they are.
758 const Working deltaXNum = targetXNum * sourceXDen - sourceXNum * targetXDen;
759 const Working deltaXDen = targetXDen * sourceXDen;
760 const Working deltaYNum = targetYNum * sourceYDen - sourceYNum * targetYDen;
761 const Working deltaYDen = targetYDen * sourceYDen;
762 Working directionX = deltaXNum * deltaYDen;
763 Working directionY = deltaYNum * deltaXDen;
764 const Working scale = gcd(abs(directionX), abs(directionY));
765 if (scale == Working(0)) {
766 return {}; // degenerate, so undefined: no direction to build a line on
767 }
768 directionX = directionX / scale;
769 directionY = directionY / scale;
770
771 // With (directionX, directionY) primitive, the line is exactly the solution
772 // set of directionY*x - directionX*y == offset, and x |-> directionY*x -
773 // directionX*y maps the integer grid onto all of Z. So the line meets the
774 // grid iff this offset is a whole number, and when it is not, no lattice
775 // point exists at all — scaling the equation cannot change that, since it
776 // scales gcd(a, b) and c alike.
777 const Working offsetNum = directionY * sourceXNum * sourceYDen
778 - directionX * sourceYNum * sourceXDen;
779 const Working offsetDen = sourceXDen * sourceYDen; // positive
780 if (offsetNum % offsetDen != Working(0)) {
781 return {};
782 }
783 const Working offset = offsetNum / offsetDen;
784
785 // Bezout gives one lattice point. Its gcd is 1 — the direction is primitive,
786 // which is exactly what makes the equation solvable — so the coefficients
787 // scaled by the offset already solve it.
788 const auto bezout = extendedGcd(directionY, -directionX);
789 Working x = bezout[1] * offset;
790 Working y = bezout[2] * offset;
791
792 // That point is as far out as the offset is large, while the answer is not,
793 // so bring it back into one period of the direction before anything else
794 // multiplies it. Reducing along the wider component keeps the exact division
795 // that rebuilds the other one small, and is what bounds every term below.
796 if (abs(directionX) >= abs(directionY)) { // directionX != 0 here
797 x = x % directionX;
798 y = (directionY * x - offset) / directionX;
799 } else {
800 y = y % directionY;
801 x = (directionX * y + offset) / directionY;
802 }
803
804 // Slide along the direction to the lattice point closest to the origin: it
805 // is the smallest one available, which is what gives a fixed-width result
806 // type its best chance of holding the answer.
807 const Working steps = nearestQuotient(
808 -(x * directionX + y * directionY),
809 directionX * directionX + directionY * directionY);
810 x = x + steps * directionX;
811 y = y + steps * directionY;
812
813 // Two lattice points tie for closest whenever the origin projects exactly
814 // between them, and rounding halves up picked the one further along the
815 // direction. Breaking that tie by lexicographic order instead makes the
816 // choice a property of the point set alone: every oriented line on it, in
817 // either direction and whatever points define it, reports this same source.
818 const Working previousX = x - directionX;
819 const Working previousY = y - directionY;
820 if (previousX * previousX + previousY * previousY == x * x + y * y
821 && (previousX < x || (previousX == x && previousY < y))) {
822 x = previousX;
823 y = previousY;
824 }
825
826 return std::array<Working, 4>{x, y, x + directionX, y + directionY};
827}
828
829} // namespace detail
830
831// The parameters are named as OrientedLine itself names them, unlike the rest
832// of this file: the return type reaches through one of them for a nested type,
833// and MSVC matches such a definition to its declaration by spelling, not by
834// parameter position, so any other name here is C2244.
835template <class PointType_, class TLabel>
836template <class ResultNumber>
837 requires(is_Rational_v<typename PointType_::NumberType>
838 && (detail::extended_integral<ResultNumber> || std::same_as<ResultNumber, BigInt>))
839std::optional<OrientedLine<Point<ResultNumber, typename PointType_::LabelType>, TLabel>>
840OrientedLine<PointType_, TLabel>::integralLine() const {
841 using ResultPoint = Point<ResultNumber, typename PointType::LabelType>;
842 using Result = OrientedLine<ResultPoint, LabelType>;
843 using Integer = rational_int_t<NumberType>;
844
845 // Both parts of every coordinate are read, and a deferred fraction reduces
846 // itself anew on each read, so reduce once here and take the fast path
847 // twice. Lowest terms also keep the products below as narrow as they can be.
848 const NumberType sourceX = source().x().simplified();
849 const NumberType sourceY = source().y().simplified();
850 const NumberType targetX = target().x().simplified();
851 const NumberType targetY = target().y().simplified();
852 const std::array<Integer, 8> parts{sourceX.numerator(), sourceX.denominator(),
853 sourceY.numerator(), sourceY.denominator(),
854 targetX.numerator(), targetX.denominator(),
855 targetY.numerator(), targetY.denominator()};
856
857 // Whether the parts are narrow enough that detail::integralLinePartBits
858 // guarantees a ::pgl::int128 holds every intermediate. A coordinate type too
859 // narrow to even represent the bound clears it by construction.
860 const auto partsFitNarrow = [&] {
861 if constexpr (detail::numeric_limits<Integer>::digits <= detail::integralLinePartBits) {
862 return true;
863 } else {
864 const Integer bound = Integer(1) << detail::integralLinePartBits;
865 for (const Integer& part : parts) {
866 if (part >= bound || part <= -bound) {
867 return false;
868 }
869 }
870 return true;
871 }
872 };
873
874 const auto widened = [&]<class Working>(std::type_identity<Working>) {
875 std::array<Working, 8> result;
876 for (std::size_t i = 0; i < parts.size(); ++i) {
877 result[i] = Working(parts[i]);
878 }
879 return result;
880 };
881
882 // Both defining points must land in the result type. A line can hit the
883 // integer grid arbitrarily far out, so this is a real answer, not a
884 // formality — and it is only meaningful because the arithmetic above cannot
885 // wrap: a wrapped intermediate would sail through it with a wrong line.
886 const auto asLineOverResult = [&](const auto& points) -> std::optional<Result> {
887 using Working = typename std::remove_cvref_t<decltype(points)>::value_type;
888 for (const Working& coordinate : points) {
889 if (!detail::representableAs<ResultNumber>(coordinate)) {
890 return {};
891 }
892 }
893 Result line(ResultPoint(detail::narrowTo<ResultNumber>(points[0]),
894 detail::narrowTo<ResultNumber>(points[1])),
895 ResultPoint(detail::narrowTo<ResultNumber>(points[2]),
896 detail::narrowTo<ResultNumber>(points[3])));
897 if constexpr (detail::has_label_v<LabelType>) {
898 line.label() = label();
899 }
900 return line;
901 };
902
903 // Clearing denominators multiplies the coordinates together several times
904 // over, so the arithmetic runs in a type that provably holds the result: a
905 // ::pgl::int128 while the parts are narrow enough to guarantee it, and
906 // BigInt beyond that, where nothing can overflow at all. Coordinates already
907 // built on an arbitrary-precision integer compute in their own type.
908 if constexpr (detail::arbitraryPrecision<Integer>) {
909 const auto points = detail::integralLinePoints(parts);
910 return points ? asLineOverResult(*points) : std::nullopt;
911 } else {
912 if (partsFitNarrow()) {
913 const auto points = detail::integralLinePoints(widened(std::type_identity<pgl::int128>{}));
914 return points ? asLineOverResult(*points) : std::nullopt;
915 }
916 const auto points = detail::integralLinePoints(widened(std::type_identity<BigInt>{}));
917 return points ? asLineOverResult(*points) : std::nullopt;
918 }
919}
920
921// -----------------------------------------------------------------------------
922// Ray
923
924template <class PointType, class LabelType>
928
929template <class PointType, class LabelType>
933
934template <class PointType, class LabelType>
935template<PointConcept OtherPoint>
936constexpr Ray<PointType, LabelType>& Ray<PointType, LabelType>::operator+=(const OtherPoint& translation) {
937 points_[0] += translation;
938 points_[1] += translation;
939 return *this;
940}
941
942template <class PointType, class LabelType>
943template<PointConcept OtherPoint>
944constexpr Ray<PointType, LabelType>& Ray<PointType, LabelType>::operator-=(const OtherPoint& translation) {
945 points_[0] -= translation;
946 points_[1] -= translation;
947 return *this;
948}
949
950template <class PointType, class LabelType>
951template <class Scalar>
952 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
953constexpr Ray<PointType, LabelType>& Ray<PointType, LabelType>::operator*=(const Scalar& scalar) {
954 points_[0] *= scalar;
955 points_[1] *= scalar;
956 return *this;
957}
958
959template <class PointType, class LabelType>
960template <class Scalar>
961 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
962constexpr Ray<PointType, LabelType>& Ray<PointType, LabelType>::operator/=(const Scalar& scalar) {
963 points_[0] /= scalar;
964 points_[1] /= scalar;
965 return *this;
966}
967
968template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
969constexpr auto operator-(const Ray<PointType, LabelType>& ray, const Point<TranslationNumber, TranslationLabel>& translation) {
970 const auto first = ray.source() - translation;
971 const auto second = ray.target() - translation;
972 return Ray<std::decay_t<decltype(first)>, LabelType>(first, second);
973}
974
975template <class PointType, class LabelType, class Scalar>
976 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
977constexpr auto operator*(const Ray<PointType, LabelType>& ray, const Scalar& scalar) {
978 const auto first = ray.source() * scalar;
979 const auto second = ray.target() * scalar;
980 return Ray<std::decay_t<decltype(first)>, LabelType>(first, second);
981}
982
983template <class Scalar, class PointType, class LabelType>
984 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
985constexpr auto operator*(const Scalar& scalar, const Ray<PointType, LabelType>& ray) {
986 return ray * scalar;
987}
988
989template <class PointType, class LabelType, class Scalar>
990 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
991constexpr auto operator/(const Ray<PointType, LabelType>& ray, const Scalar& scalar) {
992 const auto first = ray.source() / scalar;
993 const auto second = ray.target() / scalar;
994 return Ray<std::decay_t<decltype(first)>, LabelType>(first, second);
995}
996
997template <class PointType, class LabelType>
1001
1002template <class PointType, class LabelType>
1006
1007template <class PointType, class LabelType>
1008constexpr void Ray<PointType, LabelType>::rotate90(int k) {
1009 points_[0].rotate90(k);
1010 points_[1].rotate90(k);
1011}
1012
1013template <class PointType, class LabelType>
1014template <class OtherNumber>
1015constexpr Ray<PointType, LabelType> Ray<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
1016 return Ray(source().scaledUpX(scalar), target().scaledUpX(scalar));
1017}
1018
1019template <class PointType, class LabelType>
1020template <class OtherNumber>
1021constexpr void Ray<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
1022 points_[0].scaleUpX(scalar);
1023 points_[1].scaleUpX(scalar);
1024}
1025
1026template <class PointType, class LabelType>
1027template <class OtherNumber>
1028constexpr Ray<PointType, LabelType> Ray<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
1029 return Ray(source().scaledUpY(scalar), target().scaledUpY(scalar));
1030}
1031
1032template <class PointType, class LabelType>
1033template <class OtherNumber>
1034constexpr void Ray<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
1035 points_[0].scaleUpY(scalar);
1036 points_[1].scaleUpY(scalar);
1037}
1038
1039template <class PointType, class LabelType>
1040template <class OtherNumber>
1041constexpr Ray<PointType, LabelType> Ray<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
1042 return Ray(source().scaledDownX(scalar), target().scaledDownX(scalar));
1043}
1044
1045template <class PointType, class LabelType>
1046template <class OtherNumber>
1047constexpr void Ray<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
1048 points_[0].scaleDownX(scalar);
1049 points_[1].scaleDownX(scalar);
1050}
1051
1052template <class PointType, class LabelType>
1053template <class OtherNumber>
1054constexpr Ray<PointType, LabelType> Ray<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
1055 return Ray(source().scaledDownY(scalar), target().scaledDownY(scalar));
1056}
1057
1058template <class PointType, class LabelType>
1059template <class OtherNumber>
1060constexpr void Ray<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
1061 points_[0].scaleDownY(scalar);
1062 points_[1].scaleDownY(scalar);
1063}
1064
1065// -----------------------------------------------------------------------------
1066// Rectangle
1067
1068template <class PointType, class LabelType>
1069template<PointConcept OtherPoint>
1070constexpr Rectangle<PointType, LabelType>& Rectangle<PointType, LabelType>::operator+=(const OtherPoint& translation) {
1071 if (empty()) {
1072 // The empty set has no points to move.
1073 return *this;
1074 }
1075 points_[0] += translation;
1076 points_[1] += translation;
1077 return *this;
1078}
1079
1080template <class PointType, class LabelType>
1081template<PointConcept OtherPoint>
1082constexpr Rectangle<PointType, LabelType>& Rectangle<PointType, LabelType>::operator-=(const OtherPoint& translation) {
1083 if (empty()) {
1084 // The empty set has no points to move.
1085 return *this;
1086 }
1087 points_[0] -= translation;
1088 points_[1] -= translation;
1089 return *this;
1090}
1091
1092template <class PointType, class LabelType>
1093template <class Scalar>
1094 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1095constexpr Rectangle<PointType, LabelType>& Rectangle<PointType, LabelType>::operator*=(const Scalar& scalar) {
1096 auto saved = label_;
1097 *this = *this * scalar;
1098 label_ = std::move(saved);
1099 return *this;
1100}
1101
1102template <class PointType, class LabelType>
1103template <class Scalar>
1104 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1105constexpr Rectangle<PointType, LabelType>& Rectangle<PointType, LabelType>::operator/=(const Scalar& scalar) {
1106 auto saved = label_;
1107 *this = *this / scalar;
1108 label_ = std::move(saved);
1109 return *this;
1110}
1111
1112template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
1113constexpr auto operator-(const Rectangle<PointType, LabelType>& rectangle, const Point<TranslationNumber, TranslationLabel>& translation) {
1114 const auto first = rectangle.min() - translation;
1115 using ResultRectangle = Rectangle<std::decay_t<decltype(first)>, LabelType>;
1116 if (rectangle.empty()) {
1117 // The empty set has no points to transform.
1118 return ResultRectangle();
1119 }
1120 const auto second = rectangle.max() - translation;
1121 return ResultRectangle(first, second);
1122}
1123
1124template <class PointType, class LabelType, class Scalar>
1125 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1126constexpr auto operator*(const Rectangle<PointType, LabelType>& rectangle, const Scalar& scalar) {
1127 const auto first = rectangle.min() * scalar;
1128 using ResultRectangle = Rectangle<std::decay_t<decltype(first)>, LabelType>;
1129 if (rectangle.empty()) {
1130 // The empty set has no points to transform.
1131 return ResultRectangle();
1132 }
1133 const auto second = rectangle.max() * scalar;
1134 return ResultRectangle(first, second);
1135}
1136
1137template <class Scalar, class PointType, class LabelType>
1138 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1139constexpr auto operator*(const Scalar& scalar, const Rectangle<PointType, LabelType>& rectangle) {
1140 return rectangle * scalar;
1141}
1142
1143template <class PointType, class LabelType, class Scalar>
1144 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1145constexpr auto operator/(const Rectangle<PointType, LabelType>& rectangle, const Scalar& scalar) {
1146 const auto first = rectangle.min() / scalar;
1147 using ResultRectangle = Rectangle<std::decay_t<decltype(first)>, LabelType>;
1148 if (rectangle.empty()) {
1149 // The empty set has no points to transform.
1150 return ResultRectangle();
1151 }
1152 const auto second = rectangle.max() / scalar;
1153 return ResultRectangle(first, second);
1154}
1155
1156template <class PointType, class LabelType>
1157constexpr Rectangle<PointType, LabelType> Rectangle<PointType, LabelType>::rotated90(int k) const {
1158 if (empty()) {
1159 // The empty set has no points to transform.
1160 return Rectangle();
1161 }
1162 return Rectangle(min().rotated90(k), max().rotated90(k));
1163}
1164
1165template <class PointType, class LabelType>
1166constexpr void Rectangle<PointType, LabelType>::rotate90(int k) {
1167 auto saved = label_;
1168 *this = rotated90(k);
1169 label_ = std::move(saved);
1170}
1171
1172template <class PointType, class LabelType>
1173template <class OtherNumber>
1174constexpr Rectangle<PointType, LabelType> Rectangle<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
1175 if (empty()) {
1176 // The empty set has no points to transform.
1177 return Rectangle();
1178 }
1179 return Rectangle(min().scaledUpX(scalar), max().scaledUpX(scalar));
1180}
1181
1182template <class PointType, class LabelType>
1183template <class OtherNumber>
1184constexpr void Rectangle<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
1185 auto saved = label_;
1186 *this = scaledUpX(scalar);
1187 label_ = std::move(saved);
1188}
1189
1190template <class PointType, class LabelType>
1191template <class OtherNumber>
1192constexpr Rectangle<PointType, LabelType> Rectangle<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
1193 if (empty()) {
1194 // The empty set has no points to transform.
1195 return Rectangle();
1196 }
1197 return Rectangle(min().scaledUpY(scalar), max().scaledUpY(scalar));
1198}
1199
1200template <class PointType, class LabelType>
1201template <class OtherNumber>
1202constexpr void Rectangle<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
1203 auto saved = label_;
1204 *this = scaledUpY(scalar);
1205 label_ = std::move(saved);
1206}
1207
1208template <class PointType, class LabelType>
1209template <class OtherNumber>
1210constexpr Rectangle<PointType, LabelType> Rectangle<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
1211 if (empty()) {
1212 // The empty set has no points to transform.
1213 return Rectangle();
1214 }
1215 return Rectangle(min().scaledDownX(scalar), max().scaledDownX(scalar));
1216}
1217
1218template <class PointType, class LabelType>
1219template <class OtherNumber>
1220constexpr void Rectangle<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
1221 auto saved = label_;
1222 *this = scaledDownX(scalar);
1223 label_ = std::move(saved);
1224}
1225
1226template <class PointType, class LabelType>
1227template <class OtherNumber>
1228constexpr Rectangle<PointType, LabelType> Rectangle<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
1229 if (empty()) {
1230 // The empty set has no points to transform.
1231 return Rectangle();
1232 }
1233 return Rectangle(min().scaledDownY(scalar), max().scaledDownY(scalar));
1234}
1235
1236template <class PointType, class LabelType>
1237template <class OtherNumber>
1238constexpr void Rectangle<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
1239 auto saved = label_;
1240 *this = scaledDownY(scalar);
1241 label_ = std::move(saved);
1242}
1243
1244// -----------------------------------------------------------------------------
1245// Triangle
1246
1247template <class PointType, class LabelType>
1248template<PointConcept OtherPoint>
1249constexpr Triangle<PointType, LabelType>& Triangle<PointType, LabelType>::operator+=(const OtherPoint& translation) {
1250 points_[0] += translation;
1251 points_[1] += translation;
1252 points_[2] += translation;
1253 normalize();
1254 return *this;
1255}
1256
1257template <class PointType, class LabelType>
1258template<PointConcept OtherPoint>
1259constexpr Triangle<PointType, LabelType>& Triangle<PointType, LabelType>::operator-=(const OtherPoint& translation) {
1260 points_[0] -= translation;
1261 points_[1] -= translation;
1262 points_[2] -= translation;
1263 normalize();
1264 return *this;
1265}
1266
1267template <class PointType, class LabelType>
1268template <class Scalar>
1269 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1270constexpr Triangle<PointType, LabelType>& Triangle<PointType, LabelType>::operator*=(const Scalar& scalar) {
1271 points_[0] *= scalar;
1272 points_[1] *= scalar;
1273 points_[2] *= scalar;
1274 normalize();
1275 return *this;
1276}
1277
1278template <class PointType, class LabelType>
1279template <class Scalar>
1280 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1281constexpr Triangle<PointType, LabelType>& Triangle<PointType, LabelType>::operator/=(const Scalar& scalar) {
1282 points_[0] /= scalar;
1283 points_[1] /= scalar;
1284 points_[2] /= scalar;
1285 normalize();
1286 return *this;
1287}
1288
1289template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
1290constexpr auto operator-(const Triangle<PointType, LabelType>& triangle, const Point<TranslationNumber, TranslationLabel>& translation) {
1291 const auto first = triangle.a() - translation;
1292 const auto second = triangle.b() - translation;
1293 const auto third = triangle.c() - translation;
1294 return Triangle<std::decay_t<decltype(first)>, LabelType>(first, second, third);
1295}
1296
1297template <class PointType, class LabelType, class Scalar>
1298 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1299constexpr auto operator*(const Triangle<PointType, LabelType>& triangle, const Scalar& scalar) {
1300 const auto first = triangle.a() * scalar;
1301 const auto second = triangle.b() * scalar;
1302 const auto third = triangle.c() * scalar;
1303 return Triangle<std::decay_t<decltype(first)>, LabelType>(first, second, third);
1304}
1305
1306template <class Scalar, class PointType, class LabelType>
1307 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1308constexpr auto operator*(const Scalar& scalar, const Triangle<PointType, LabelType>& triangle) {
1309 return triangle * scalar;
1310}
1311
1312template <class PointType, class LabelType, class Scalar>
1313 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1314constexpr auto operator/(const Triangle<PointType, LabelType>& triangle, const Scalar& scalar) {
1315 const auto first = triangle.a() / scalar;
1316 const auto second = triangle.b() / scalar;
1317 const auto third = triangle.c() / scalar;
1318 return Triangle<std::decay_t<decltype(first)>, LabelType>(first, second, third);
1319}
1320
1321template <class PointType, class LabelType>
1325
1326template <class PointType, class LabelType>
1327constexpr void Triangle<PointType, LabelType>::rotate90(int k) {
1328 auto saved = label_;
1329 *this = rotated90(k);
1330 label_ = std::move(saved);
1331}
1332
1333template <class PointType, class LabelType>
1334template <class OtherNumber>
1335constexpr Triangle<PointType, LabelType> Triangle<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
1336 return Triangle(a().scaledUpX(scalar), b().scaledUpX(scalar), c().scaledUpX(scalar));
1337}
1338
1339template <class PointType, class LabelType>
1340template <class OtherNumber>
1341constexpr void Triangle<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
1342 auto saved = label_;
1343 *this = scaledUpX(scalar);
1344 label_ = std::move(saved);
1345}
1346
1347template <class PointType, class LabelType>
1348template <class OtherNumber>
1349constexpr Triangle<PointType, LabelType> Triangle<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
1350 return Triangle(a().scaledUpY(scalar), b().scaledUpY(scalar), c().scaledUpY(scalar));
1351}
1352
1353template <class PointType, class LabelType>
1354template <class OtherNumber>
1355constexpr void Triangle<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
1356 auto saved = label_;
1357 *this = scaledUpY(scalar);
1358 label_ = std::move(saved);
1359}
1360
1361template <class PointType, class LabelType>
1362template <class OtherNumber>
1363constexpr Triangle<PointType, LabelType> Triangle<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
1364 return Triangle(a().scaledDownX(scalar), b().scaledDownX(scalar), c().scaledDownX(scalar));
1365}
1366
1367template <class PointType, class LabelType>
1368template <class OtherNumber>
1369constexpr void Triangle<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
1370 auto saved = label_;
1371 *this = scaledDownX(scalar);
1372 label_ = std::move(saved);
1373}
1374
1375template <class PointType, class LabelType>
1376template <class OtherNumber>
1377constexpr Triangle<PointType, LabelType> Triangle<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
1378 return Triangle(a().scaledDownY(scalar), b().scaledDownY(scalar), c().scaledDownY(scalar));
1379}
1380
1381template <class PointType, class LabelType>
1382template <class OtherNumber>
1383constexpr void Triangle<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
1384 auto saved = label_;
1385 *this = scaledDownY(scalar);
1386 label_ = std::move(saved);
1387}
1388
1389// -----------------------------------------------------------------------------
1390// Halfplane
1391
1392template <class PointType, class LabelType>
1393template<PointConcept OtherPoint>
1394constexpr Halfplane<PointType, LabelType>& Halfplane<PointType, LabelType>::operator+=(const OtherPoint& translation) {
1395 points_[0] += translation;
1396 points_[1] += translation;
1397 return *this;
1398}
1399
1400template <class PointType, class LabelType>
1401template<PointConcept OtherPoint>
1402constexpr Halfplane<PointType, LabelType>& Halfplane<PointType, LabelType>::operator-=(const OtherPoint& translation) {
1403 points_[0] -= translation;
1404 points_[1] -= translation;
1405 return *this;
1406}
1407
1408template <class PointType, class LabelType>
1409template <class Scalar>
1410 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1411constexpr Halfplane<PointType, LabelType>& Halfplane<PointType, LabelType>::operator*=(const Scalar& scalar) {
1412 points_[0] *= scalar;
1413 points_[1] *= scalar;
1414 return *this;
1415}
1416
1417template <class PointType, class LabelType>
1418template <class Scalar>
1419 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1420constexpr Halfplane<PointType, LabelType>& Halfplane<PointType, LabelType>::operator/=(const Scalar& scalar) {
1421 points_[0] /= scalar;
1422 points_[1] /= scalar;
1423 return *this;
1424}
1425
1426template <class PointType, class LabelType, class TranslationNumber, class TranslationLabel>
1427constexpr auto operator-(const Halfplane<PointType, LabelType>& halfplane, const Point<TranslationNumber, TranslationLabel>& translation) {
1428 const auto first = halfplane.source() - translation;
1429 const auto second = halfplane.target() - translation;
1430 return Halfplane<std::decay_t<decltype(first)>, LabelType>(first, second);
1431}
1432
1433template <class PointType, class LabelType, class Scalar>
1434 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1435constexpr auto operator*(const Halfplane<PointType, LabelType>& halfplane, const Scalar& scalar) {
1436 const auto first = halfplane.source() * scalar;
1437 const auto second = halfplane.target() * scalar;
1438 return Halfplane<std::decay_t<decltype(first)>, LabelType>(first, second);
1439}
1440
1441template <class Scalar, class PointType, class LabelType>
1442 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1443constexpr auto operator*(const Scalar& scalar, const Halfplane<PointType, LabelType>& halfplane) {
1444 return halfplane * scalar;
1445}
1446
1447template <class PointType, class LabelType, class Scalar>
1448 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1449constexpr auto operator/(const Halfplane<PointType, LabelType>& halfplane, const Scalar& scalar) {
1450 const auto first = halfplane.source() / scalar;
1451 const auto second = halfplane.target() / scalar;
1452 return Halfplane<std::decay_t<decltype(first)>, LabelType>(first, second);
1453}
1454
1455
1456template <class PointType, class LabelType>
1460
1461template <class PointType, class LabelType>
1462constexpr void Halfplane<PointType, LabelType>::rotate90(int k) {
1463 auto saved = label_;
1464 *this = rotated90(k);
1465 label_ = std::move(saved);
1466}
1467
1468template <class PointType, class LabelType>
1469template <class OtherNumber>
1470constexpr Halfplane<PointType, LabelType> Halfplane<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
1471 // A negative factor reflects the plane, flipping the inside side; swap
1472 // source and target so the oriented boundary keeps the correct side.
1473 if (scalar < OtherNumber{})
1474 return Halfplane(target().scaledUpX(scalar), source().scaledUpX(scalar));
1475 return Halfplane(source().scaledUpX(scalar), target().scaledUpX(scalar));
1476}
1477
1478template <class PointType, class LabelType>
1479template <class OtherNumber>
1480constexpr void Halfplane<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
1481 auto saved = label_;
1482 *this = scaledUpX(scalar);
1483 label_ = std::move(saved);
1484}
1485
1486template <class PointType, class LabelType>
1487template <class OtherNumber>
1488constexpr Halfplane<PointType, LabelType> Halfplane<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
1489 // A negative factor reflects the plane, flipping the inside side; swap
1490 // source and target so the oriented boundary keeps the correct side.
1491 if (scalar < OtherNumber{})
1492 return Halfplane(target().scaledUpY(scalar), source().scaledUpY(scalar));
1493 return Halfplane(source().scaledUpY(scalar), target().scaledUpY(scalar));
1494}
1495
1496template <class PointType, class LabelType>
1497template <class OtherNumber>
1498constexpr void Halfplane<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
1499 auto saved = label_;
1500 *this = scaledUpY(scalar);
1501 label_ = std::move(saved);
1502}
1503
1504template <class PointType, class LabelType>
1505template <class OtherNumber>
1506constexpr Halfplane<PointType, LabelType> Halfplane<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
1507 // A negative factor reflects the plane, flipping the inside side; swap
1508 // source and target so the oriented boundary keeps the correct side.
1509 if (scalar < OtherNumber{})
1510 return Halfplane(target().scaledDownX(scalar), source().scaledDownX(scalar));
1511 return Halfplane(source().scaledDownX(scalar), target().scaledDownX(scalar));
1512}
1513
1514template <class PointType, class LabelType>
1515template <class OtherNumber>
1516constexpr void Halfplane<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
1517 auto saved = label_;
1518 *this = scaledDownX(scalar);
1519 label_ = std::move(saved);
1520}
1521
1522template <class PointType, class LabelType>
1523template <class OtherNumber>
1524constexpr Halfplane<PointType, LabelType> Halfplane<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
1525 // A negative factor reflects the plane, flipping the inside side; swap
1526 // source and target so the oriented boundary keeps the correct side.
1527 if (scalar < OtherNumber{})
1528 return Halfplane(target().scaledDownY(scalar), source().scaledDownY(scalar));
1529 return Halfplane(source().scaledDownY(scalar), target().scaledDownY(scalar));
1530}
1531
1532template <class PointType, class LabelType>
1533template <class OtherNumber>
1534constexpr void Halfplane<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
1535 auto saved = label_;
1536 *this = scaledDownY(scalar);
1537 label_ = std::move(saved);
1538}
1539
1540// ---------------------------------------------------------------------------
1541// Convex
1542
1543template <class PointType, class LabelType>
1544template<PointConcept OtherPoint>
1545constexpr Convex<PointType, LabelType>& Convex<PointType, LabelType>::operator+=(const OtherPoint& translation) {
1546 translation_ += translation;
1547 // A pure translation leaves maxIndex_ valid (the extreme vertex index is
1548 // translation-invariant) and merely shifts the bounding box, so update the
1549 // cached bbox in place rather than discarding it. The hash, however, depends
1550 // on the absolute vertex positions, so it must be invalidated.
1551 if (!bbox_.empty()) {
1552 bbox_ += translation;
1553 }
1554 hash_ = hashUnset_;
1555 return *this;
1556}
1557
1558template <class PointType, class LabelType>
1559template<PointConcept OtherPoint>
1560constexpr Convex<PointType, LabelType>& Convex<PointType, LabelType>::operator-=(const OtherPoint& translation) {
1561 translation_ -= translation;
1562 if (!bbox_.empty()) {
1563 bbox_ -= translation;
1564 }
1565 hash_ = hashUnset_;
1566 return *this;
1567}
1568
1569// Scaling in place cannot keep the stored vertices canonical on its own, so it
1570// rebuilds through the normalizing constructor -- as rotate90 and the four
1571// scaleUp/scaleDown mutators beside it already do. A positive factor would be
1572// safe to apply vertex by vertex, but the other two cases are not: a negative
1573// factor is a point reflection, which preserves the counterclockwise cycle but
1574// reverses the lexicographic order, so the canonical lex-min-first rotation no
1575// longer starts where it must; and a zero factor collapses every vertex onto the
1576// origin, which has to come back as the one-vertex hull rather than as n copies
1577// of it. A Convex whose rotation is wrong is not merely untidy: the convex
1578// predicates binary-search the vertex cycle from that starting point, so such a
1579// value answers `contains` incorrectly.
1580template <class PointType, class LabelType>
1581template <class Scalar>
1582requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1583constexpr Convex<PointType, LabelType>& Convex<PointType, LabelType>::operator*=(const Scalar& scalar) {
1584 std::vector<PointType> scaled;
1585 scaled.reserve(size());
1586 for (const PointType& vertex : *this) {
1587 PointType moved = vertex;
1588 moved *= scalar;
1589 scaled.push_back(std::move(moved));
1590 }
1591 auto saved = label_;
1592 *this = Convex(std::move(scaled));
1593 label_ = std::move(saved);
1594 return *this;
1595}
1596
1597// Rebuilt for the same reason as operator*=: a negative divisor reverses the
1598// lexicographic order and leaves the canonical rotation starting in the wrong
1599// place.
1600template <class PointType, class LabelType>
1601template <class Scalar>
1602requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
1603constexpr Convex<PointType, LabelType>& Convex<PointType, LabelType>::operator/=(const Scalar& scalar) {
1604 std::vector<PointType> scaled;
1605 scaled.reserve(size());
1606 for (const PointType& vertex : *this) {
1607 PointType moved = vertex;
1608 moved /= scalar;
1609 scaled.push_back(std::move(moved));
1610 }
1611 auto saved = label_;
1612 *this = Convex(std::move(scaled));
1613 label_ = std::move(saved);
1614 return *this;
1615}
1616
1617template <class PointType, class LabelType>
1618constexpr Convex<PointType, LabelType> Convex<PointType, LabelType>::rotated90(int k) const {
1619 std::vector<PointType> pts;
1620 pts.reserve(size());
1621 for (const auto& p : *this) {
1622 pts.push_back(p.rotated90(k));
1623 }
1624 return Convex(std::move(pts));
1625}
1626
1627template <class PointType, class LabelType>
1628constexpr void Convex<PointType, LabelType>::rotate90(int k) {
1629 auto saved = label_;
1630 *this = rotated90(k);
1631 label_ = std::move(saved);
1632}
1633
1634template <class PointType, class LabelType>
1635template <class OtherNumber>
1636constexpr Convex<PointType, LabelType> Convex<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
1637 std::vector<PointType> pts;
1638 pts.reserve(size());
1639 for (const auto& p : *this) {
1640 pts.push_back(p.scaledUpX(scalar));
1641 }
1642 return Convex(std::move(pts));
1643}
1644
1645template <class PointType, class LabelType>
1646template <class OtherNumber>
1647constexpr void Convex<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
1648 auto saved = label_;
1649 *this = scaledUpX(scalar);
1650 label_ = std::move(saved);
1651}
1652
1653template <class PointType, class LabelType>
1654template <class OtherNumber>
1655constexpr Convex<PointType, LabelType> Convex<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
1656 std::vector<PointType> pts;
1657 pts.reserve(size());
1658 for (const auto& p : *this) {
1659 pts.push_back(p.scaledUpY(scalar));
1660 }
1661 return Convex(std::move(pts));
1662}
1663
1664template <class PointType, class LabelType>
1665template <class OtherNumber>
1666constexpr void Convex<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
1667 auto saved = label_;
1668 *this = scaledUpY(scalar);
1669 label_ = std::move(saved);
1670}
1671
1672template <class PointType, class LabelType>
1673template <class OtherNumber>
1674constexpr Convex<PointType, LabelType> Convex<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
1675 std::vector<PointType> pts;
1676 pts.reserve(size());
1677 for (const auto& p : *this) {
1678 pts.push_back(p.scaledDownX(scalar));
1679 }
1680 return Convex(std::move(pts));
1681}
1682
1683template <class PointType, class LabelType>
1684template <class OtherNumber>
1685constexpr void Convex<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
1686 auto saved = label_;
1687 *this = scaledDownX(scalar);
1688 label_ = std::move(saved);
1689}
1690
1691template <class PointType, class LabelType>
1692template <class OtherNumber>
1693constexpr Convex<PointType, LabelType> Convex<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
1694 std::vector<PointType> pts;
1695 pts.reserve(size());
1696 for (const auto& p : *this) {
1697 pts.push_back(p.scaledDownY(scalar));
1698 }
1699 return Convex(std::move(pts));
1700}
1701
1702template <class PointType, class LabelType>
1703template <class OtherNumber>
1704constexpr void Convex<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
1705 auto saved = label_;
1706 *this = scaledDownY(scalar);
1707 label_ = std::move(saved);
1708}
1709
1710// ---------------------------------------------------------------------------
1711// Polygon
1712
1713template <class PointType, class LabelType>
1714constexpr Polygon<PointType, LabelType> Polygon<PointType, LabelType>::rotated90(int k) const {
1715 std::vector<PointType> pts;
1716 pts.reserve(size());
1717 for (const auto& p : *this) {
1718 pts.push_back(p.rotated90(k));
1719 }
1720 return Polygon(std::move(pts));
1721}
1722
1723template <class PointType, class LabelType>
1724constexpr void Polygon<PointType, LabelType>::rotate90(int k) {
1725 auto saved = label_;
1726 *this = rotated90(k);
1727 label_ = std::move(saved);
1728}
1729
1730template <class PointType, class LabelType>
1731constexpr void Polygon<PointType, LabelType>::untangle() {
1732 if (!std::is_constant_evaluated()) {
1733 untangleRuntime();
1734 return;
1735 }
1736
1737 // Work directly on the stored (untranslated) vertices: a uniform translation
1738 // preserves every crossing/containment relation used below, so indices stay
1739 // meaningful without applying translation_. This pairwise path is retained
1740 // for constant evaluation; runtime calls use the interval-tree implementation.
1741 const auto edge = [this](std::ptrdiff_t a) {
1742 const std::ptrdiff_t n = static_cast<std::ptrdiff_t>(points_.size());
1743 return Segment<PointType>(points_[static_cast<std::size_t>(a)],
1744 points_[static_cast<std::size_t>((a + 1) % n)]);
1745 };
1746
1747 while (points_.size() >= 3) {
1748 const std::ptrdiff_t n = static_cast<std::ptrdiff_t>(points_.size());
1749
1750 // 1) Uncross a transversally crossing pair of non-adjacent edges. The
1751 // reversal of the sub-path v[i+1..j] strictly shortens the perimeter,
1752 // so this can happen only finitely often for a fixed vertex count.
1753 bool flipped = false;
1754 for (std::ptrdiff_t i = 0; i < n && !flipped; ++i) {
1755 for (std::ptrdiff_t j = i + 1; j < n; ++j) {
1756 const bool adjacent = (j == i + 1) || (i == 0 && j == n - 1);
1757 if (adjacent) {
1758 continue;
1759 }
1760 if (edge(i).crosses(edge(j))) {
1761 std::reverse(points_.begin() + (i + 1), points_.begin() + (j + 1));
1762 flipped = true;
1763 break;
1764 }
1765 }
1766 }
1767 if (flipped) {
1768 continue;
1769 }
1770
1771 // 2) No transversal crossing remains, so any residual self-contact is a
1772 // collinear touch/overlap, a coincident vertex, or a zero-length edge.
1773 // In each case a vertex lies on a non-incident edge; deleting it clears
1774 // the contact and strictly decreases the vertex count.
1775 bool removed = false;
1776 for (std::ptrdiff_t k = 0; k < n && !removed; ++k) {
1777 if (points_[static_cast<std::size_t>(k)] ==
1778 points_[static_cast<std::size_t>((k + 1) % n)]) {
1779 points_.erase(points_.begin() + k); // zero-length edge
1780 removed = true;
1781 break;
1782 }
1783 for (std::ptrdiff_t e = 0; e < n; ++e) {
1784 if (e == k || e == (k - 1 + n) % n) {
1785 continue; // edges incident to vertex k always contain it
1786 }
1787 if (edge(e).contains(points_[static_cast<std::size_t>(k)])) {
1788 points_.erase(points_.begin() + k);
1789 removed = true;
1790 break;
1791 }
1792 }
1793 }
1794 if (!removed) {
1795 break; // no crossing and no self-contact: the polygon is simple
1796 }
1797 }
1798
1799 normalize();
1800 resetCache();
1801}
1802
1803template <class PointType, class LabelType>
1804template <class OtherNumber>
1805constexpr Polygon<PointType, LabelType> Polygon<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
1806 std::vector<PointType> pts;
1807 pts.reserve(size());
1808 for (const auto& p : *this) {
1809 pts.push_back(p.scaledUpX(scalar));
1810 }
1811 return Polygon(std::move(pts));
1812}
1813
1814template <class PointType, class LabelType>
1815template <class OtherNumber>
1816constexpr void Polygon<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
1817 auto saved = label_;
1818 *this = scaledUpX(scalar);
1819 label_ = std::move(saved);
1820}
1821
1822template <class PointType, class LabelType>
1823template <class OtherNumber>
1824constexpr Polygon<PointType, LabelType> Polygon<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
1825 std::vector<PointType> pts;
1826 pts.reserve(size());
1827 for (const auto& p : *this) {
1828 pts.push_back(p.scaledUpY(scalar));
1829 }
1830 return Polygon(std::move(pts));
1831}
1832
1833template <class PointType, class LabelType>
1834template <class OtherNumber>
1835constexpr void Polygon<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
1836 auto saved = label_;
1837 *this = scaledUpY(scalar);
1838 label_ = std::move(saved);
1839}
1840
1841template <class PointType, class LabelType>
1842template <class OtherNumber>
1843constexpr Polygon<PointType, LabelType> Polygon<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
1844 std::vector<PointType> pts;
1845 pts.reserve(size());
1846 for (const auto& p : *this) {
1847 pts.push_back(p.scaledDownX(scalar));
1848 }
1849 return Polygon(std::move(pts));
1850}
1851
1852template <class PointType, class LabelType>
1853template <class OtherNumber>
1854constexpr void Polygon<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
1855 auto saved = label_;
1856 *this = scaledDownX(scalar);
1857 label_ = std::move(saved);
1858}
1859
1860template <class PointType, class LabelType>
1861template <class OtherNumber>
1862constexpr Polygon<PointType, LabelType> Polygon<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
1863 std::vector<PointType> pts;
1864 pts.reserve(size());
1865 for (const auto& p : *this) {
1866 pts.push_back(p.scaledDownY(scalar));
1867 }
1868 return Polygon(std::move(pts));
1869}
1870
1871template <class PointType, class LabelType>
1872template <class OtherNumber>
1873constexpr void Polygon<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
1874 auto saved = label_;
1875 *this = scaledDownY(scalar);
1876 label_ = std::move(saved);
1877}
1878
1879// ---------------------------------------------------------------------------
1880// MonotoneChain
1881//
1882// Every transformed result goes through the non-trusted constructor: a
1883// 90-degree rotation swaps the monotone axis, and a negative or zero scale
1884// factor reverses or collapses the lexicographic order, so the vertex set is
1885// re-sorted into the canonical chain on the transformed points.
1886
1887template <class PointType, class LabelType, class Storage>
1888constexpr MonotoneChain<PointType, LabelType> MonotoneChain<PointType, LabelType, Storage>::rotated90(int k) const {
1889 std::vector<PointType> pts;
1890 pts.reserve(size());
1891 for (const auto& p : *this) {
1892 pts.push_back(p.rotated90(k));
1893 }
1894 return MonotoneChain<PointType, LabelType>(std::move(pts));
1895}
1896
1897template <class PointType, class LabelType, class Storage>
1898constexpr void MonotoneChain<PointType, LabelType, Storage>::rotate90(int k)
1899 requires detail::ownsChainStorage<Storage, PointType> {
1900 auto saved = label_;
1901 *this = rotated90(k);
1902 label_ = std::move(saved);
1903}
1904
1905template <class PointType, class LabelType, class Storage>
1906template <class OtherNumber>
1907constexpr MonotoneChain<PointType, LabelType> MonotoneChain<PointType, LabelType, Storage>::scaledUpX(const OtherNumber scalar) const {
1908 std::vector<PointType> pts;
1909 pts.reserve(size());
1910 for (const auto& p : *this) {
1911 pts.push_back(p.scaledUpX(scalar));
1912 }
1913 return MonotoneChain<PointType, LabelType>(std::move(pts));
1914}
1915
1916template <class PointType, class LabelType, class Storage>
1917template <class OtherNumber>
1918constexpr void MonotoneChain<PointType, LabelType, Storage>::scaleUpX(const OtherNumber scalar)
1919 requires detail::ownsChainStorage<Storage, PointType> {
1920 auto saved = label_;
1921 *this = scaledUpX(scalar);
1922 label_ = std::move(saved);
1923}
1924
1925template <class PointType, class LabelType, class Storage>
1926template <class OtherNumber>
1927constexpr MonotoneChain<PointType, LabelType> MonotoneChain<PointType, LabelType, Storage>::scaledUpY(const OtherNumber scalar) const {
1928 std::vector<PointType> pts;
1929 pts.reserve(size());
1930 for (const auto& p : *this) {
1931 pts.push_back(p.scaledUpY(scalar));
1932 }
1933 return MonotoneChain<PointType, LabelType>(std::move(pts));
1934}
1935
1936template <class PointType, class LabelType, class Storage>
1937template <class OtherNumber>
1938constexpr void MonotoneChain<PointType, LabelType, Storage>::scaleUpY(const OtherNumber scalar)
1939 requires detail::ownsChainStorage<Storage, PointType> {
1940 auto saved = label_;
1941 *this = scaledUpY(scalar);
1942 label_ = std::move(saved);
1943}
1944
1945template <class PointType, class LabelType, class Storage>
1946template <class OtherNumber>
1947constexpr MonotoneChain<PointType, LabelType> MonotoneChain<PointType, LabelType, Storage>::scaledDownX(const OtherNumber scalar) const {
1948 std::vector<PointType> pts;
1949 pts.reserve(size());
1950 for (const auto& p : *this) {
1951 pts.push_back(p.scaledDownX(scalar));
1952 }
1953 return MonotoneChain<PointType, LabelType>(std::move(pts));
1954}
1955
1956template <class PointType, class LabelType, class Storage>
1957template <class OtherNumber>
1958constexpr void MonotoneChain<PointType, LabelType, Storage>::scaleDownX(const OtherNumber scalar)
1959 requires detail::ownsChainStorage<Storage, PointType> {
1960 auto saved = label_;
1961 *this = scaledDownX(scalar);
1962 label_ = std::move(saved);
1963}
1964
1965template <class PointType, class LabelType, class Storage>
1966template <class OtherNumber>
1967constexpr MonotoneChain<PointType, LabelType> MonotoneChain<PointType, LabelType, Storage>::scaledDownY(const OtherNumber scalar) const {
1968 std::vector<PointType> pts;
1969 pts.reserve(size());
1970 for (const auto& p : *this) {
1971 pts.push_back(p.scaledDownY(scalar));
1972 }
1973 return MonotoneChain<PointType, LabelType>(std::move(pts));
1974}
1975
1976template <class PointType, class LabelType, class Storage>
1977template <class OtherNumber>
1978constexpr void MonotoneChain<PointType, LabelType, Storage>::scaleDownY(const OtherNumber scalar)
1979 requires detail::ownsChainStorage<Storage, PointType> {
1980 auto saved = label_;
1981 *this = scaledDownY(scalar);
1982 label_ = std::move(saved);
1983}
1984
1985// ---------------------------------------------------------------------------
1986// Polyline
1987//
1988// Every transformed result goes through the non-trusted constructor, which
1989// preserves the vertex sequence and only fixes the direction canonicalization:
1990// a rotation or a negative scale factor can reverse the lexicographic order of
1991// the extreme vertices.
1992
1993template <class PointType, class LabelType>
1994constexpr Polyline<PointType, LabelType> Polyline<PointType, LabelType>::rotated90(int k) const {
1995 std::vector<PointType> pts;
1996 pts.reserve(size());
1997 for (const auto& p : *this) {
1998 pts.push_back(p.rotated90(k));
1999 }
2000 return Polyline<PointType, LabelType>(std::move(pts));
2001}
2002
2003template <class PointType, class LabelType>
2004constexpr void Polyline<PointType, LabelType>::rotate90(int k) {
2005 auto saved = label_;
2006 *this = rotated90(k);
2007 label_ = std::move(saved);
2008}
2009
2010template <class PointType, class LabelType>
2011template <class OtherNumber>
2012constexpr Polyline<PointType, LabelType> Polyline<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
2013 std::vector<PointType> pts;
2014 pts.reserve(size());
2015 for (const auto& p : *this) {
2016 pts.push_back(p.scaledUpX(scalar));
2017 }
2018 return Polyline<PointType, LabelType>(std::move(pts));
2019}
2020
2021template <class PointType, class LabelType>
2022template <class OtherNumber>
2023constexpr void Polyline<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
2024 auto saved = label_;
2025 *this = scaledUpX(scalar);
2026 label_ = std::move(saved);
2027}
2028
2029template <class PointType, class LabelType>
2030template <class OtherNumber>
2031constexpr Polyline<PointType, LabelType> Polyline<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
2032 std::vector<PointType> pts;
2033 pts.reserve(size());
2034 for (const auto& p : *this) {
2035 pts.push_back(p.scaledUpY(scalar));
2036 }
2037 return Polyline<PointType, LabelType>(std::move(pts));
2038}
2039
2040template <class PointType, class LabelType>
2041template <class OtherNumber>
2042constexpr void Polyline<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
2043 auto saved = label_;
2044 *this = scaledUpY(scalar);
2045 label_ = std::move(saved);
2046}
2047
2048template <class PointType, class LabelType>
2049template <class OtherNumber>
2050constexpr Polyline<PointType, LabelType> Polyline<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
2051 std::vector<PointType> pts;
2052 pts.reserve(size());
2053 for (const auto& p : *this) {
2054 pts.push_back(p.scaledDownX(scalar));
2055 }
2056 return Polyline<PointType, LabelType>(std::move(pts));
2057}
2058
2059template <class PointType, class LabelType>
2060template <class OtherNumber>
2061constexpr void Polyline<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
2062 auto saved = label_;
2063 *this = scaledDownX(scalar);
2064 label_ = std::move(saved);
2065}
2066
2067template <class PointType, class LabelType>
2068template <class OtherNumber>
2069constexpr Polyline<PointType, LabelType> Polyline<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
2070 std::vector<PointType> pts;
2071 pts.reserve(size());
2072 for (const auto& p : *this) {
2073 pts.push_back(p.scaledDownY(scalar));
2074 }
2075 return Polyline<PointType, LabelType>(std::move(pts));
2076}
2077
2078template <class PointType, class LabelType>
2079template <class OtherNumber>
2080constexpr void Polyline<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
2081 auto saved = label_;
2082 *this = scaledDownY(scalar);
2083 label_ = std::move(saved);
2084}
2085
2086template <class PointType, class LabelType>
2087template <SegmentConcept OldSegment, SegmentConcept NewSegment>
2088constexpr std::optional<std::vector<PointType>>
2089Polyline<PointType, LabelType>::flipVertices(const OldSegment& oldEdge,
2090 const NewSegment& newEdge) const {
2091 const std::size_t n = size();
2092 if (n < 2) {
2093 return std::nullopt; // no edge to remove
2094 }
2095
2096 const PointType o0 = oldEdge[0];
2097 const PointType o1 = oldEdge[1];
2098 const PointType m0 = newEdge[0];
2099 const PointType m1 = newEdge[1];
2100
2101 // The added edge must be a real, distinct edge.
2102 if (m0 == m1) {
2103 return std::nullopt; // degenerate added edge
2104 }
2105 const auto sameSet = [](const PointType& a, const PointType& b, const PointType& c,
2106 const PointType& d) {
2107 return (a == c && b == d) || (a == d && b == c);
2108 };
2109 if (sameSet(o0, o1, m0, m1)) {
2110 return std::nullopt; // re-adding the removed edge is not a flip
2111 }
2112
2113 const std::vector<PointType> v = vertices();
2114 for (std::size_t i = 0; i + 1 < n; ++i) {
2115 if (!sameSet(v[i], v[i + 1], o0, o1)) {
2116 continue; // oldEdge does not match this edge
2117 }
2118 // A = v[0 .. i] (holds the first vertex), B = v[i+1 .. n-1] (the last).
2119 std::vector<PointType> out;
2120 out.reserve(n);
2121 if (sameSet(m0, m1, v[i], v[n - 1])) { // add (p_i, p_{n-1}): reverse B
2122 for (std::size_t k = 0; k <= i; ++k) {
2123 out.push_back(v[k]);
2124 }
2125 for (std::size_t k = n; k-- > i + 1;) {
2126 out.push_back(v[k]);
2127 }
2128 return out;
2129 }
2130 if (sameSet(m0, m1, v[0], v[i + 1])) { // add (p_0, p_{i+1}): reverse A
2131 for (std::size_t k = i + 1; k-- > 0;) {
2132 out.push_back(v[k]);
2133 }
2134 for (std::size_t k = i + 1; k < n; ++k) {
2135 out.push_back(v[k]);
2136 }
2137 return out;
2138 }
2139 if (sameSet(m0, m1, v[0], v[n - 1])) { // add (p_0, p_{n-1}): reverse both
2140 for (std::size_t k = i + 1; k-- > 0;) {
2141 out.push_back(v[k]);
2142 }
2143 for (std::size_t k = n; k-- > i + 1;) {
2144 out.push_back(v[k]);
2145 }
2146 return out;
2147 }
2148 // This edge matches oldEdge but newEdge is not a valid reconnection for
2149 // it; a later duplicate of oldEdge might still admit newEdge.
2150 }
2151 return std::nullopt;
2152}
2153
2154template <class PointType, class LabelType>
2155template <SegmentConcept OldSegment, SegmentConcept NewSegment>
2156constexpr bool Polyline<PointType, LabelType>::flippable(const OldSegment& oldEdge,
2157 const NewSegment& newEdge) const {
2158 return flipVertices(oldEdge, newEdge).has_value();
2159}
2160
2161template <class PointType, class LabelType>
2162template <SegmentConcept OldSegment, SegmentConcept NewSegment>
2163constexpr Polyline<PointType, LabelType>
2164Polyline<PointType, LabelType>::flipped(const OldSegment& oldEdge, const NewSegment& newEdge) const {
2165 auto vertices = flipVertices(oldEdge, newEdge);
2166 assert(vertices.has_value());
2167 return Polyline<PointType, LabelType>(std::move(*vertices));
2168}
2169
2170template <class PointType, class LabelType>
2171template <SegmentConcept OldSegment, SegmentConcept NewSegment>
2172constexpr void Polyline<PointType, LabelType>::flip(const OldSegment& oldEdge,
2173 const NewSegment& newEdge) {
2174 auto saved = label_;
2175 *this = flipped(oldEdge, newEdge);
2176 label_ = std::move(saved);
2177}
2178
2179// ---------------------------------------------------------------------------
2180// Disk
2181
2182template <class PointType, class LabelType>
2183constexpr Disk<PointType, LabelType> Disk<PointType, LabelType>::rotated90(int k) const {
2184 return Disk(a().rotated90(k), b().rotated90(k), c().rotated90(k));
2185}
2186
2187template <class PointType, class LabelType>
2188constexpr void Disk<PointType, LabelType>::rotate90(int k) {
2189 for (auto& point : points_) {
2190 point.rotate90(k);
2191 }
2192 points_ = canonicalizePoints(points_[0], points_[1], points_[2]);
2193}
2194
2195// ---------------------------------------------------------------------------
2196// Transformation
2197
2198template <class Number, class ShapeT>
2199 requires (detail::shapeRank<ShapeT> >= 0 && !RectangleConcept<ShapeT> && !DiskConcept<ShapeT>)
2200constexpr auto operator*(const Transformation<Number>& transformation, const ShapeT& shape) {
2201 // Applies the transformation to a single point, promoting the coordinate
2202 // type the same way every other operator in this file does.
2203 const auto point = [&transformation](const auto& p) {
2204 using PLabel = typename std::decay_t<decltype(p)>::LabelType;
2205 using PNumber = typename std::decay_t<decltype(p)>::NumberType;
2206 using ResultNumber = std::common_type_t<Number, PNumber>;
2207 return Point<ResultNumber, PLabel>(
2208 transformation.a() * p.x() + transformation.b() * p.y() + transformation.tx(),
2209 transformation.c() * p.x() + transformation.d() * p.y() + transformation.ty());
2210 };
2211
2212 if constexpr (detail::is_empty_shape_v<ShapeT>) {
2213 using ResultNumber = std::common_type_t<Number, typename ShapeT::NumberType>;
2214 return EmptyShape<Point<ResultNumber, typename ShapeT::LabelType>>{};
2215 } else if constexpr (PointConcept<ShapeT>) {
2216 return point(shape);
2217 } else if constexpr (SegmentConcept<ShapeT>) {
2218 const auto first = point(shape.min());
2219 const auto second = point(shape.max());
2220 return Segment<std::decay_t<decltype(first)>, typename ShapeT::LabelType>(first, second);
2221 } else if constexpr (OrientedSegmentConcept<ShapeT>) {
2222 const auto first = point(shape.source());
2223 const auto second = point(shape.target());
2224 return OrientedSegment<std::decay_t<decltype(first)>, typename ShapeT::LabelType>(first, second);
2225 } else if constexpr (LineConcept<ShapeT>) {
2226 const auto first = point(shape.min());
2227 const auto second = point(shape.max());
2228 return Line<std::decay_t<decltype(first)>, typename ShapeT::LabelType>(first, second);
2229 } else if constexpr (OrientedLineConcept<ShapeT>) {
2230 // Unlike Halfplane below, an OrientedLine has no "this is a fixed
2231 // region" contract to preserve: "left"/"right" are just whichever
2232 // side is currently left/right of source->target, so no swap is
2233 // needed even when the transformation reverses orientation.
2234 const auto first = point(shape.source());
2235 const auto second = point(shape.target());
2236 return OrientedLine<std::decay_t<decltype(first)>, typename ShapeT::LabelType>(first, second);
2237 } else if constexpr (RayConcept<ShapeT>) {
2238 const auto first = point(shape.source());
2239 const auto second = point(shape.target());
2240 return Ray<std::decay_t<decltype(first)>, typename ShapeT::LabelType>(first, second);
2241 } else if constexpr (HalfplaneConcept<ShapeT>) {
2242 const auto first = point(shape.source());
2243 const auto second = point(shape.target());
2244 using ResultPoint = std::decay_t<decltype(first)>;
2245 // A negative determinant reflects the plane, flipping the inside
2246 // side; swap source and target so the oriented boundary keeps the
2247 // correct side, mirroring the same fix in Halfplane::scaledUpX for a
2248 // negative scale factor.
2249 if (transformation.determinant() < decltype(transformation.determinant()){}) {
2250 return Halfplane<ResultPoint, typename ShapeT::LabelType>(second, first);
2251 }
2252 return Halfplane<ResultPoint, typename ShapeT::LabelType>(first, second);
2253 } else if constexpr (TriangleConcept<ShapeT>) {
2254 // Triangle's constructor normalizes (CCW, lex-min vertex first), so
2255 // an orientation-reversing transformation is fixed up automatically.
2256 const auto pa = point(shape.a());
2257 const auto pb = point(shape.b());
2258 const auto pc = point(shape.c());
2259 return Triangle<std::decay_t<decltype(pa)>, typename ShapeT::LabelType>(pa, pb, pc);
2260 } else if constexpr (ConvexConcept<ShapeT>) {
2261 // The non-trusted constructor reruns the Graham scan, which both
2262 // fixes up orientation and prunes any collinear points a degenerate
2263 // transformation may introduce -- the same reasoning already used by
2264 // Convex::rotated90.
2265 using ResultPoint = decltype(point(std::declval<typename ShapeT::PointType>()));
2266 std::vector<ResultPoint> pts;
2267 pts.reserve(shape.size());
2268 for (const auto& p : shape) {
2269 pts.push_back(point(p));
2270 }
2271 return Convex<ResultPoint, typename ShapeT::LabelType>(std::move(pts));
2272 } else if constexpr (PolygonConcept<ShapeT>) {
2273 // The non-trusted constructor renormalizes (CCW, lex-min vertex
2274 // first), the same reasoning already used by Polygon::rotated90.
2275 using ResultPoint = decltype(point(std::declval<typename ShapeT::PointType>()));
2276 std::vector<ResultPoint> pts;
2277 pts.reserve(shape.size());
2278 for (const auto& p : shape) {
2279 pts.push_back(point(p));
2280 }
2281 return Polygon<ResultPoint, typename ShapeT::LabelType>(std::move(pts));
2282 } else if constexpr (MonotoneChainConcept<ShapeT>) {
2283 // A general affine map does not preserve x-monotonicity, so the
2284 // non-trusted constructor re-sorts the transformed vertices into the
2285 // canonical chain on the mapped point set, the same reasoning already
2286 // used by MonotoneChain::rotated90.
2287 using ResultPoint = decltype(point(std::declval<typename ShapeT::PointType>()));
2288 std::vector<ResultPoint> pts;
2289 pts.reserve(shape.size());
2290 for (const auto& p : shape) {
2291 pts.push_back(point(p));
2292 }
2293 return MonotoneChain<ResultPoint, typename ShapeT::LabelType>(std::move(pts));
2294 } else if constexpr (PolylineConcept<ShapeT>) {
2295 // The vertices are mapped in traversal order; the non-trusted
2296 // constructor only fixes the direction canonicalization, which an
2297 // orientation-reversing transformation may flip.
2298 using ResultPoint = decltype(point(std::declval<typename ShapeT::PointType>()));
2299 std::vector<ResultPoint> pts;
2300 pts.reserve(shape.size());
2301 for (const auto& p : shape) {
2302 pts.push_back(point(p));
2303 }
2304 return Polyline<ResultPoint, typename ShapeT::LabelType>(std::move(pts));
2305 } else if constexpr (PolygonWithHolesConcept<ShapeT>) {
2306 // Every ring maps like the Polygon branch above, each through its own
2307 // non-trusted constructor; the region's normalization then re-sorts the
2308 // holes, whose relative order an orientation-reversing map can change,
2309 // the same reasoning already used by PolygonWithHoles::rotated90.
2310 using ResultPoint = decltype(point(std::declval<typename ShapeT::PointType>()));
2311 using ResultPolygon = Polygon<ResultPoint>;
2312 const auto ring = [&point](const auto& source) {
2313 std::vector<ResultPoint> pts;
2314 pts.reserve(source.size());
2315 for (const auto& p : source) {
2316 pts.push_back(point(p));
2317 }
2318 return ResultPolygon(std::move(pts));
2319 };
2320
2321 std::vector<ResultPolygon> holes;
2322 holes.reserve(shape.holeCount());
2323 for (const auto& hole : shape.holes()) {
2324 holes.push_back(ring(hole));
2325 }
2326 return PolygonWithHoles<ResultPoint, typename ShapeT::LabelType>(
2327 ring(shape.outer()), std::move(holes));
2328 } else if constexpr (PolygonSetConcept<ShapeT>) {
2329 // Every component maps like the region branch above, through its own
2330 // non-trusted constructor; the set's normalization then re-sorts the
2331 // components, whose relative order an orientation-reversing map can
2332 // change, and drops any that a degenerate map has collapsed.
2333 using ResultPoint = decltype(point(std::declval<typename ShapeT::PointType>()));
2334 using ResultRegion = PolygonWithHoles<ResultPoint>;
2335 const auto ring = [&point](const auto& source) {
2336 std::vector<ResultPoint> pts;
2337 pts.reserve(source.size());
2338 for (const auto& p : source) {
2339 pts.push_back(point(p));
2340 }
2341 return Polygon<ResultPoint>(std::move(pts));
2342 };
2343
2344 std::vector<ResultRegion> components;
2345 components.reserve(shape.componentCount());
2346 for (const auto& component : shape) {
2347 std::vector<Polygon<ResultPoint>> holes;
2348 holes.reserve(component.holeCount());
2349 for (const auto& hole : component.holes()) {
2350 holes.push_back(ring(hole));
2351 }
2352 components.emplace_back(ring(component.outer()), std::move(holes));
2353 }
2354 return PolygonSet<ResultPoint, typename ShapeT::LabelType>(std::move(components));
2355 } else if constexpr (HalfplaneIntersectionConcept<ShapeT>) {
2356 // Each stored half-plane maps like the Halfplane branch above,
2357 // swapping its defining points under a reflection; the non-trusted
2358 // range constructor restores the sorted invariant. The sticky empty
2359 // state is rebuilt from contradictory constraints, since the affine
2360 // image of the empty set is empty.
2361 using ResultPoint = decltype(point(std::declval<typename ShapeT::PointType>()));
2362 using ResultRegion = HalfplaneIntersection<ResultPoint, typename ShapeT::LabelType>;
2363 using ResultHalfplane = typename ResultRegion::HalfplaneType;
2364 if (shape.empty()) {
2365 ResultRegion result;
2366 result.insert(ResultHalfplane(ResultPoint(0, 0), ResultPoint(0, 1)));
2367 result.insert(ResultHalfplane(ResultPoint(1, 1), ResultPoint(1, 0)));
2368 return result;
2369 }
2370 const bool reflecting =
2371 transformation.determinant() < decltype(transformation.determinant()){};
2372 std::vector<ResultHalfplane> mapped;
2373 mapped.reserve(shape.size());
2374 for (const auto& halfplane : shape) {
2375 const auto first = point(halfplane.source());
2376 const auto second = point(halfplane.target());
2377 mapped.push_back(reflecting ? ResultHalfplane(second, first)
2378 : ResultHalfplane(first, second));
2379 }
2380 return ResultRegion(mapped);
2381 }
2382}
2383
2384template <class Number, ShapeConcept ShapeT>
2385constexpr auto operator*(const Transformation<Number>& transformation, const ShapeT& shape) {
2386 using PointType = typename ShapeT::PointType_;
2387 using ResultNumber = std::common_type_t<Number, typename PointType::NumberType>;
2388 using ResultShape = Shape<Point<ResultNumber, typename PointType::LabelType>>;
2389 return std::visit(
2390 [&transformation](const auto& value) -> ResultShape {
2391 if constexpr (requires { transformation * value; }) {
2392 return ResultShape(transformation * value);
2393 } else {
2394 throw std::logic_error(
2395 "Transformation::operator* is not defined for the Rectangle/Disk alternative");
2396 }
2397 },
2398 shape.variant());
2399}
2400
2401
2402// ---------------------------------------------------------------------------
2403// HalfplaneIntersection
2404//
2405// Translations and rotations preserve the sorted-by-direction invariant up to
2406// a cyclic rotation, and axis scalings up to a reversal; canonicalizeSorted()
2407// restores the canonical order in every mutating case. Feasibility and
2408// non-redundancy are preserved by any bijective affine map, so no rebuild is
2409// needed — but the truncating operations (integer division) are inexact and
2410// may leave a representation that no longer matches the exact image.
2411
2412template <class PointType, class LabelType>
2413template <PointConcept OtherPoint>
2414constexpr HalfplaneIntersection<PointType, LabelType>&
2415HalfplaneIntersection<PointType, LabelType>::operator+=(const OtherPoint& translation) {
2416 for (auto& halfplane : halfplanes_) {
2417 halfplane += translation;
2418 }
2419 resetCache();
2420 return *this;
2421}
2422
2423template <class PointType, class LabelType>
2424template <PointConcept OtherPoint>
2425constexpr HalfplaneIntersection<PointType, LabelType>&
2426HalfplaneIntersection<PointType, LabelType>::operator-=(const OtherPoint& translation) {
2427 for (auto& halfplane : halfplanes_) {
2428 halfplane -= translation;
2429 }
2430 resetCache();
2431 return *this;
2432}
2433
2434template <class PointType, class LabelType>
2435template <class Scalar>
2436 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
2437constexpr HalfplaneIntersection<PointType, LabelType>&
2438HalfplaneIntersection<PointType, LabelType>::operator*=(const Scalar& scalar) {
2439 for (auto& halfplane : halfplanes_) {
2440 halfplane *= scalar;
2441 }
2442 canonicalizeSorted();
2443 return *this;
2444}
2445
2446template <class PointType, class LabelType>
2447template <class Scalar>
2448 requires(!detail::is_point_v<Scalar> && !TransformationConcept<Scalar>)
2449constexpr HalfplaneIntersection<PointType, LabelType>&
2450HalfplaneIntersection<PointType, LabelType>::operator/=(const Scalar& scalar) {
2451 for (auto& halfplane : halfplanes_) {
2452 halfplane /= scalar;
2453 }
2454 canonicalizeSorted();
2455 return *this;
2456}
2457
2458template <class PointType, class LabelType>
2459constexpr HalfplaneIntersection<PointType, LabelType>
2460HalfplaneIntersection<PointType, LabelType>::rotated90(int k) const {
2461 HalfplaneIntersection result(*this);
2462 result.rotate90(k);
2463 return result;
2464}
2465
2466template <class PointType, class LabelType>
2467constexpr void HalfplaneIntersection<PointType, LabelType>::rotate90(int k) {
2468 for (auto& halfplane : halfplanes_) {
2469 halfplane.rotate90(k);
2470 }
2471 canonicalizeSorted();
2472}
2473
2474template <class PointType, class LabelType>
2475template <class OtherNumber>
2476constexpr HalfplaneIntersection<PointType, LabelType>
2477HalfplaneIntersection<PointType, LabelType>::scaledUpX(const OtherNumber scalar) const {
2478 HalfplaneIntersection result(*this);
2479 result.scaleUpX(scalar);
2480 return result;
2481}
2482
2483template <class PointType, class LabelType>
2484template <class OtherNumber>
2485constexpr void HalfplaneIntersection<PointType, LabelType>::scaleUpX(const OtherNumber scalar) {
2486 for (auto& halfplane : halfplanes_) {
2487 halfplane.scaleUpX(scalar);
2488 }
2489 canonicalizeSorted();
2490}
2491
2492template <class PointType, class LabelType>
2493template <class OtherNumber>
2494constexpr HalfplaneIntersection<PointType, LabelType>
2495HalfplaneIntersection<PointType, LabelType>::scaledUpY(const OtherNumber scalar) const {
2496 HalfplaneIntersection result(*this);
2497 result.scaleUpY(scalar);
2498 return result;
2499}
2500
2501template <class PointType, class LabelType>
2502template <class OtherNumber>
2503constexpr void HalfplaneIntersection<PointType, LabelType>::scaleUpY(const OtherNumber scalar) {
2504 for (auto& halfplane : halfplanes_) {
2505 halfplane.scaleUpY(scalar);
2506 }
2507 canonicalizeSorted();
2508}
2509
2510template <class PointType, class LabelType>
2511template <class OtherNumber>
2512constexpr HalfplaneIntersection<PointType, LabelType>
2513HalfplaneIntersection<PointType, LabelType>::scaledDownX(const OtherNumber scalar) const {
2514 HalfplaneIntersection result(*this);
2515 result.scaleDownX(scalar);
2516 return result;
2517}
2518
2519template <class PointType, class LabelType>
2520template <class OtherNumber>
2521constexpr void HalfplaneIntersection<PointType, LabelType>::scaleDownX(const OtherNumber scalar) {
2522 for (auto& halfplane : halfplanes_) {
2523 halfplane.scaleDownX(scalar);
2524 }
2525 canonicalizeSorted();
2526}
2527
2528template <class PointType, class LabelType>
2529template <class OtherNumber>
2530constexpr HalfplaneIntersection<PointType, LabelType>
2531HalfplaneIntersection<PointType, LabelType>::scaledDownY(const OtherNumber scalar) const {
2532 HalfplaneIntersection result(*this);
2533 result.scaleDownY(scalar);
2534 return result;
2535}
2536
2537template <class PointType, class LabelType>
2538template <class OtherNumber>
2539constexpr void HalfplaneIntersection<PointType, LabelType>::scaleDownY(const OtherNumber scalar) {
2540 for (auto& halfplane : halfplanes_) {
2541 halfplane.scaleDownY(scalar);
2542 }
2543 canonicalizeSorted();
2544}
2545
2546} // namespace pgl
pgl::ConvexConcept
Definition forward.hpp:315
pgl::DiskConcept
Definition forward.hpp:322
pgl::HalfplaneConcept
Definition forward.hpp:312
pgl::HalfplaneIntersectionConcept
Definition forward.hpp:319
pgl::LineConcept
Definition forward.hpp:309
pgl::MonotoneChainConcept
Definition forward.hpp:320
pgl::OrientedLineConcept
Definition forward.hpp:310
pgl::OrientedSegmentConcept
Definition forward.hpp:308
pgl::PointConcept
Definition forward.hpp:306
pgl::PolygonConcept
Definition forward.hpp:316
pgl::PolygonSetConcept
Definition forward.hpp:318
pgl::PolygonWithHolesConcept
Definition forward.hpp:317
pgl::PolylineConcept
Definition forward.hpp:321
pgl::RayConcept
Definition forward.hpp:311
pgl::RectangleConcept
Definition forward.hpp:313
pgl::SegmentConcept
Definition forward.hpp:307
pgl::TransformationConcept
Definition forward.hpp:324
pgl::TriangleConcept
Definition forward.hpp:314
io.hpp
Stream output helpers for Pangolin value types.
pgl
Definition arrangement.hpp:67
pgl::HalfplaneIntersection
HalfplaneIntersection() -> HalfplaneIntersection< Point<>, NoLabel >
Definition halfplaneintersection.hpp:2308
pgl::ProjectionAxis::y
@ y
Definition intervaltree.hpp:24
pgl::ProjectionAxis::x
@ x
Definition intervaltree.hpp:24
pgl::abs
BigInt abs(const BigInt &v)
Free-function absolute value, matching the integer helpers.
Definition bigint.hpp:948
pgl::Rectangle
Rectangle() -> Rectangle< Point<>, NoLabel >
Definition rectangle.hpp:2384
pgl::is_Rational_v
constexpr bool is_Rational_v
Definition rational.hpp:37
pgl::GridAdjacency::edge
@ edge
Definition bitmatrix.hpp:37
pgl::GridAdjacency::vertex
@ vertex
Definition bitmatrix.hpp:37
pgl::Line
Line() -> Line< Point<>, NoLabel >
pgl::Point
Point() -> Point< int >
pgl::operator-
constexpr auto operator-(const Point< LeftNumber, LeftLabel > &left, const Point< RightNumber, RightLabel > &right)
Translates a point by the opposite of another point.
Definition transformations.hpp:130
pgl::PolygonSet
PolygonSet() -> PolygonSet< Point<>, NoLabel >
Definition polygonset.hpp:1699
pgl::OrientedSegment
OrientedSegment() -> OrientedSegment< Point<>, NoLabel >
pgl::rational_int_t
typename rational_int< T >::type rational_int_t
Definition rational.hpp:61
pgl::MonotoneChain
MonotoneChain() -> MonotoneChain< Point<>, NoLabel >
Definition monotonechain.hpp:2439
pgl::PolygonWithHoles
PolygonWithHoles() -> PolygonWithHoles< Point<>, NoLabel >
Definition polygonwithholes.hpp:3093
pgl::Convex
Convex() -> Convex< Point<>, NoLabel >
Definition convex.hpp:3311
pgl::Segment
Segment() -> Segment< Point<>, NoLabel >
pgl::Halfplane
Halfplane() -> Halfplane< Point<>, NoLabel >
pgl::Polyline
Polyline() -> Polyline< Point<>, NoLabel >
Definition polyline.hpp:2369
pgl::Ray
Ray() -> Ray< Point<>, NoLabel >
pgl::Polygon
Polygon() -> Polygon< Point<>, NoLabel >
Definition polygon.hpp:3200
pgl::Disk
Disk() -> Disk< Point<>, NoLabel >
Deduces a default disk with Point<> boundary points and no label.
Definition disk.hpp:1691
pgl::OrientedLine
OrientedLine() -> OrientedLine< Point<>, NoLabel >
pgl::operator*
constexpr auto operator*(const Transformation< Number > &transformation, const ShapeT &shape)
Applies a transformation to any supported shape.
Definition transformations.hpp:2200
pgl::Triangle
Triangle() -> Triangle< Point<>, NoLabel >
Definition triangle.hpp:2029
pgl::Convex::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the convex polygon's y-coordinates by a factor in place.
Definition transformations.hpp:1666
pgl::Convex::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the convex polygon's x-coordinates by a divisor in place.
Definition transformations.hpp:1685
pgl::Convex::scaledDownX
constexpr Convex scaledDownX(const OtherNumber scalar) const
Returns the convex polygon with its x-coordinates divided by a divisor.
pgl::Convex::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the convex polygon's y-coordinates by a divisor in place.
Definition transformations.hpp:1704
pgl::Convex::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the convex polygon's x-coordinates by a factor in place.
Definition transformations.hpp:1647
pgl::Convex::operator+=
constexpr Convex & operator+=(const OtherPoint &translation)
Translates the convex polygon by the given point in place.
pgl::Convex::operator-=
constexpr Convex & operator-=(const OtherPoint &translation)
Translates the convex polygon by the negation of the given point.
pgl::Convex::rotated90
constexpr Convex rotated90(int k=1) const
Returns the convex polygon rotated by 90k degrees around the origin.
Definition transformations.hpp:1618
pgl::Convex::scaledUpX
constexpr Convex scaledUpX(const OtherNumber scalar) const
Returns the convex polygon with its x-coordinates multiplied by a factor.
pgl::Convex::scaledUpY
constexpr Convex scaledUpY(const OtherNumber scalar) const
Returns the convex polygon with its y-coordinates multiplied by a factor.
pgl::Convex< PointType >::Convex
constexpr Convex()=default
pgl::Convex::rotate90
constexpr void rotate90(int k=1)
Rotates the convex polygon by 90k degrees around the origin in place.
Definition transformations.hpp:1628
pgl::Convex< PointType >::size
size_t size() const
Definition convex.hpp:840
pgl::Convex< PointType >::PointType
PointType PointType
Definition convex.hpp:171
pgl::Convex::scaledDownY
constexpr Convex scaledDownY(const OtherNumber scalar) const
Returns the convex polygon with its y-coordinates divided by a divisor.
pgl::Disk::rotated90
constexpr Disk rotated90(int k=1) const
Returns the disk rotated by 90k degrees around the origin.
Definition transformations.hpp:2183
pgl::Disk::c
constexpr const PointType & c() const
Returns the third boundary point in canonical order.
Definition disk.hpp:244
pgl::Disk::Disk
constexpr Disk()=default
Creates a disk with all three boundary points at the origin.
pgl::Disk::rotate90
constexpr void rotate90(int k=1)
Rotates the disk by 90k degrees around the origin in place.
Definition transformations.hpp:2188
pgl::Disk::a
constexpr const PointType & a() const
Returns the first boundary point (lexicographically smallest).
Definition disk.hpp:228
pgl::Disk::b
constexpr const PointType & b() const
Returns the second boundary point in canonical order.
Definition disk.hpp:235
pgl::EmptyShape
The empty set of points in the plane.
Definition emptyshape.hpp:33
pgl::HalfplaneIntersection
Intersection of closed half-planes; convex but possibly unbounded or empty.
Definition halfplaneintersection.hpp:244
pgl::HalfplaneIntersection::rotated90
constexpr HalfplaneIntersection rotated90(int k=1) const
Returns the region rotated by 90k degrees around the origin.
Definition transformations.hpp:2460
pgl::HalfplaneIntersection::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the region's x-coordinates by a divisor in place.
Definition transformations.hpp:2521
pgl::HalfplaneIntersection::operator-=
constexpr HalfplaneIntersection & operator-=(const OtherPoint &translation)
Translates the region by the negation of the given point in place.
pgl::HalfplaneIntersection::scaledDownX
constexpr HalfplaneIntersection scaledDownX(const OtherNumber scalar) const
Returns the region with its x-coordinates divided by a divisor.
pgl::HalfplaneIntersection::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the region's y-coordinates by a divisor in place.
Definition transformations.hpp:2539
pgl::HalfplaneIntersection::scaledDownY
constexpr HalfplaneIntersection scaledDownY(const OtherNumber scalar) const
Returns the region with its y-coordinates divided by a divisor.
pgl::HalfplaneIntersection::scaledUpX
constexpr HalfplaneIntersection scaledUpX(const OtherNumber scalar) const
Returns the region with its x-coordinates multiplied by a factor.
pgl::HalfplaneIntersection::rotate90
constexpr void rotate90(int k=1)
Rotates the region by 90k degrees around the origin in place.
Definition transformations.hpp:2467
pgl::HalfplaneIntersection::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the region's y-coordinates by a factor in place.
Definition transformations.hpp:2503
pgl::HalfplaneIntersection< minkowskiErosionPoint_t< A, B > >::HalfplaneIntersection
friend struct HalfplaneIntersection
Definition halfplaneintersection.hpp:2308
pgl::HalfplaneIntersection::scaledUpY
constexpr HalfplaneIntersection scaledUpY(const OtherNumber scalar) const
Returns the region with its y-coordinates multiplied by a factor.
pgl::HalfplaneIntersection::operator+=
constexpr HalfplaneIntersection & operator+=(const OtherPoint &translation)
Translates the region by the given point in place.
pgl::HalfplaneIntersection::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the region's x-coordinates by a factor in place.
Definition transformations.hpp:2485
pgl::Halfplane
Closed half-plane defined by an oriented boundary line.
Definition halfplane.hpp:51
pgl::Halfplane::rotated90
constexpr Halfplane rotated90(int k=1) const
Returns the half-plane rotated by 90k degrees around the origin.
Definition transformations.hpp:1457
pgl::Halfplane::scaledDownY
constexpr Halfplane scaledDownY(const OtherNumber scalar) const
Returns the half-plane with its y-coordinates divided by a divisor.
pgl::Halfplane::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the half-plane's x-coordinates by a divisor in place.
Definition transformations.hpp:1516
pgl::Halfplane::operator+=
constexpr Halfplane & operator+=(const OtherPoint &translation)
Translates the half-plane by the given point in place.
pgl::Halfplane::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the half-plane's y-coordinates by a divisor in place.
Definition transformations.hpp:1534
pgl::Halfplane::rotate90
constexpr void rotate90(int k=1)
Rotates the half-plane by 90k degrees around the origin in place.
Definition transformations.hpp:1462
pgl::Halfplane::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the half-plane's x-coordinates by a factor in place.
Definition transformations.hpp:1480
pgl::Halfplane::operator-=
constexpr Halfplane & operator-=(const OtherPoint &translation)
Translates the half-plane by the negation of the given point in place.
pgl::Halfplane::target
constexpr const PointType & target() const
Returns the target boundary point.
Definition halfplane.hpp:193
pgl::Halfplane::scaledDownX
constexpr Halfplane scaledDownX(const OtherNumber scalar) const
Returns the half-plane with its x-coordinates divided by a divisor.
pgl::Halfplane::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the half-plane's y-coordinates by a factor in place.
Definition transformations.hpp:1498
pgl::Halfplane::scaledUpX
constexpr Halfplane scaledUpX(const OtherNumber scalar) const
Returns the half-plane with its x-coordinates multiplied by a factor.
pgl::Halfplane::source
constexpr const PointType & source() const
Returns the source boundary point.
Definition halfplane.hpp:181
pgl::Halfplane::Halfplane
constexpr Halfplane()=default
Creates the degenerate half-plane (0,0)->(0,0).
pgl::Halfplane::scaledUpY
constexpr Halfplane scaledUpY(const OtherNumber scalar) const
Returns the half-plane with its y-coordinates multiplied by a factor.
pgl::Line
Unoriented infinite line.
Definition line.hpp:52
pgl::Line::rotate90
constexpr void rotate90(int k=1)
Rotates the line by 90k degrees around the origin in place.
Definition transformations.hpp:510
pgl::Line::max
constexpr const PointType & max() const
Returns the largest stored defining point.
Definition line.hpp:189
pgl::Line::scaledDownX
constexpr Line scaledDownX(const OtherNumber scalar) const
Returns the line with its x-coordinates divided by a divisor.
pgl::Line::min
constexpr const PointType & min() const
Returns the smallest stored defining point.
Definition line.hpp:180
pgl::Line::scaledUpY
constexpr Line scaledUpY(const OtherNumber scalar) const
Returns the line with its y-coordinates multiplied by a factor.
pgl::Line::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the line's x-coordinates by a factor in place.
Definition transformations.hpp:524
pgl::Line::rotated90
constexpr Line rotated90(int k=1) const
Returns the line rotated by 90k degrees around the origin.
Definition transformations.hpp:505
pgl::Line< PointType, TLabel >::Line
constexpr Line()=default
pgl::Line::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the line's y-coordinates by a divisor in place.
Definition transformations.hpp:566
pgl::Line::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the line's x-coordinates by a divisor in place.
Definition transformations.hpp:552
pgl::Line::operator+=
constexpr Line & operator+=(const OtherPoint &translation)
Translates both defining points in place.
pgl::Line::scaledUpX
constexpr Line scaledUpX(const OtherNumber scalar) const
Returns the line with its x-coordinates multiplied by a factor.
pgl::Line::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the line's y-coordinates by a factor in place.
Definition transformations.hpp:538
pgl::Line::scaledDownY
constexpr Line scaledDownY(const OtherNumber scalar) const
Returns the line with its y-coordinates divided by a divisor.
pgl::Line::operator-=
constexpr Line & operator-=(const OtherPoint &translation)
Translates both defining points by the opposite vector in place.
pgl::MonotoneChain::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the chain's x-coordinates by a factor in place.
Definition transformations.hpp:1918
pgl::MonotoneChain::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the chain's x-coordinates by a divisor in place.
Definition transformations.hpp:1958
pgl::MonotoneChain::size
constexpr std::size_t size() const
Returns the number of vertices in the chain.
Definition monotonechain.hpp:393
pgl::MonotoneChain::scaledUpY
constexpr OwningChain scaledUpY(const OtherNumber scalar) const
Returns the chain with its y-coordinates multiplied by a factor.
pgl::MonotoneChain::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the chain's y-coordinates by a divisor in place.
Definition transformations.hpp:1978
pgl::MonotoneChain::scaledDownX
constexpr OwningChain scaledDownX(const OtherNumber scalar) const
Returns the chain with its x-coordinates divided by a divisor.
pgl::MonotoneChain::scaledDownY
constexpr OwningChain scaledDownY(const OtherNumber scalar) const
Returns the chain with its y-coordinates divided by a divisor.
pgl::MonotoneChain::MonotoneChain
constexpr MonotoneChain()=default
Creates a chain with no vertex.
pgl::MonotoneChain::rotate90
constexpr void rotate90(int k=1)
Rotates the chain by 90k degrees around the origin in place.
Definition transformations.hpp:1898
pgl::MonotoneChain::rotated90
constexpr OwningChain rotated90(int k=1) const
Returns the chain rotated by 90k degrees around the origin.
Definition transformations.hpp:1888
pgl::MonotoneChain::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the chain's y-coordinates by a factor in place.
Definition transformations.hpp:1938
pgl::MonotoneChain::scaledUpX
constexpr OwningChain scaledUpX(const OtherNumber scalar) const
Returns the chain with its x-coordinates multiplied by a factor.
pgl::OrientedLine
Directed infinite line with left/right side semantics plus optional line label.
Definition orientedline.hpp:53
pgl::OrientedLine::scaledUpY
constexpr OrientedLine scaledUpY(const OtherNumber scalar) const
Returns the line with its y-coordinates multiplied by a factor.
pgl::OrientedLine::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the line's y-coordinates by a factor in place.
Definition transformations.hpp:685
pgl::OrientedLine::operator-=
constexpr OrientedLine & operator-=(const OtherPoint &translation)
Translates the oriented line by the negation of the given point in place.
pgl::OrientedLine::target
constexpr const PointType & target() const
Returns the target defining point.
Definition orientedline.hpp:195
pgl::OrientedLine::scaledDownX
constexpr OrientedLine scaledDownX(const OtherNumber scalar) const
Returns the line with its x-coordinates divided by a divisor.
pgl::OrientedLine::rotate90
constexpr void rotate90(int k=1)
Rotates the oriented line by 90k degrees around the origin in place.
Definition transformations.hpp:659
pgl::OrientedLine::label
constexpr A & label() const
Returns the line label.
Definition orientedline.hpp:305
pgl::OrientedLine::integralLine
std::optional< OrientedLine< Point< ResultNumber, typename PointType_::LabelType >, TLabel > > integralLine() const
Returns an equal oriented line whose defining points have integer coordinates, when one exists.
Definition transformations.hpp:840
pgl::OrientedLine::scaledDownY
constexpr OrientedLine scaledDownY(const OtherNumber scalar) const
Returns the line with its y-coordinates divided by a divisor.
pgl::OrientedLine::operator+=
constexpr OrientedLine & operator+=(const OtherPoint &translation)
Translates the oriented line by the given point in place.
pgl::OrientedLine::scaledUpX
constexpr OrientedLine scaledUpX(const OtherNumber scalar) const
Returns the line with its x-coordinates multiplied by a factor.
pgl::OrientedLine::OrientedLine
constexpr OrientedLine()=default
Creates the degenerate oriented line (0,0)--(0,0).
pgl::OrientedLine::rotated90
constexpr OrientedLine rotated90(int k=1) const
Returns the oriented line rotated by 90k degrees around the origin.
Definition transformations.hpp:654
pgl::OrientedLine::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the line's x-coordinates by a divisor in place.
Definition transformations.hpp:698
pgl::OrientedLine::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the line's y-coordinates by a divisor in place.
Definition transformations.hpp:711
pgl::OrientedLine::NumberType
PointType::NumberType NumberType
Definition orientedline.hpp:55
pgl::OrientedLine::source
constexpr const PointType & source() const
Returns the source defining point.
Definition orientedline.hpp:183
pgl::OrientedLine::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the line's x-coordinates by a factor in place.
Definition transformations.hpp:672
pgl::OrientedSegment
Directed segment preserving source-to-target order plus optional segment label.
Definition orientedsegment.hpp:44
pgl::OrientedSegment::rotate90
constexpr void rotate90(int k=1)
Rotates the segment by 90k degrees around the origin in place.
Definition transformations.hpp:369
pgl::OrientedSegment< PointType, TLabel >::points_
std::array< PointType, 2 > points_
Definition orientedsegment.hpp:1842
pgl::OrientedSegment::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the segment's x-coordinates by a factor in place.
Definition transformations.hpp:382
pgl::OrientedSegment::source
constexpr const PointType & source() const
Returns the source endpoint.
Definition orientedsegment.hpp:178
pgl::OrientedSegment::rotated90
constexpr OrientedSegment rotated90(int k=1) const
Returns the segment rotated by 90k degrees around the origin.
Definition transformations.hpp:364
pgl::OrientedSegment::scaledDownY
constexpr OrientedSegment scaledDownY(const OtherNumber scalar) const
Returns the segment with its y-coordinates divided by a divisor.
pgl::OrientedSegment::operator+=
constexpr OrientedSegment & operator+=(const OtherPoint &translation)
Translates the oriented segment by the given point in place.
pgl::OrientedSegment::target
constexpr const PointType & target() const
Returns the target endpoint.
Definition orientedsegment.hpp:190
pgl::OrientedSegment::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the segment's x-coordinates by a divisor in place.
Definition transformations.hpp:408
pgl::OrientedSegment::operator-=
constexpr OrientedSegment & operator-=(const OtherPoint &translation)
Translates the oriented segment by the negation of the given point in place.
pgl::OrientedSegment::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the segment's y-coordinates by a factor in place.
Definition transformations.hpp:395
pgl::OrientedSegment::scaledUpX
constexpr OrientedSegment scaledUpX(const OtherNumber scalar) const
Returns the segment with its x-coordinates multiplied by a factor.
pgl::OrientedSegment::scaledDownX
constexpr OrientedSegment scaledDownX(const OtherNumber scalar) const
Returns the segment with its x-coordinates divided by a divisor.
pgl::OrientedSegment::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the segment's y-coordinates by a divisor in place.
Definition transformations.hpp:421
pgl::OrientedSegment::scaledUpY
constexpr OrientedSegment scaledUpY(const OtherNumber scalar) const
Returns the segment with its y-coordinates multiplied by a factor.
pgl::Point
Two-dimensional point with optional label payload.
Definition point.hpp:129
pgl::Point::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the point's x-coordinate by a scalar in place.
Definition transformations.hpp:87
pgl::Point::rotated90
constexpr Point rotated90(int k=1) const
Returns the point rotated by 90k degrees around the origin.
Definition transformations.hpp:61
pgl::Point::Point
constexpr Point()=default
Creates the origin point (0, 0).
pgl::Point::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the point's x-coordinate by a scalar in place.
Definition transformations.hpp:111
pgl::Point< int >::scaledUpY
constexpr Point< Number, Label > scaledUpY(const OtherNumber scalar) const
Definition transformations.hpp:93
pgl::Point::swapped
constexpr Point swapped() const
Returns the point with x and y swapped.
Definition transformations.hpp:56
pgl::Point::operator-
constexpr Point operator-() const
Returns the point mirrored through the origin.
Definition transformations.hpp:19
pgl::Point::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the point's y-coordinate by a scalar in place.
Definition transformations.hpp:123
pgl::Point::scaledUpX
constexpr Point scaledUpX(const OtherNumber scalar) const
Returns the point with its x-coordinate multiplied by a scalar.
pgl::Point::scaledDownX
constexpr Point scaledDownX(const OtherNumber scalar) const
Returns the point with its x-coordinate divided by a scalar.
pgl::Point::operator/=
constexpr Point & operator/=(const OtherNumber scalar)
Scales a point by a scalar division in place.
pgl::Point::operator-=
constexpr Point & operator-=(const OtherPoint &other)
Translates a point by the opposite of another point in place.
pgl::Point< int >::scaledUpX
constexpr Point< Number, Label > scaledUpX(const OtherNumber scalar) const
Definition transformations.hpp:81
pgl::Point::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the point's y-coordinate by a scalar in place.
Definition transformations.hpp:99
pgl::Point::operator*=
constexpr Point & operator*=(const OtherNumber scalar)
Scales a point by a scalar in place.
pgl::Point::operator+=
constexpr Point & operator+=(const OtherPoint &other)
Translates a point by another point in place.
pgl::Point::rotate90
constexpr void rotate90(int k=1)
Rotates the point by 90k degrees around the origin in place.
Definition transformations.hpp:71
pgl::Point< int >::LabelType
TLabel LabelType
Definition point.hpp:133
pgl::Point::x
constexpr const NumberType & x() const
Returns the x coordinate.
Definition point.hpp:193
pgl::Point::y
constexpr const NumberType & y() const
Returns the y coordinate.
Definition point.hpp:205
pgl::Point::scaledDownY
constexpr Point scaledDownY(const OtherNumber scalar) const
Returns the point with its y-coordinate divided by a scalar.
pgl::Point::scaledUpY
constexpr Point scaledUpY(const OtherNumber scalar) const
Returns the point with its y-coordinate multiplied by a scalar.
pgl::PolygonWithHoles
Closed region bounded by one outer simple polygon minus disjoint polygonal holes.
Definition polygonwithholes.hpp:89
pgl::Polygon
Closed simple polygon stored by its vertices.
Definition polygon.hpp:59
pgl::Polygon::crosses
constexpr bool crosses(const OtherChain &other) const
Tests whether the two shapes mutually separate each other (each disconnects the other).
Definition crosses.hpp:940
pgl::Polygon::scaledUpY
constexpr Polygon scaledUpY(const OtherNumber scalar) const
Returns the polygon with its y-coordinates multiplied by a factor.
pgl::Polygon::contains
constexpr bool contains(const OtherPoint &point) const
Tests whether this shape contains the other shape (A ⊇ B).
Definition contains.hpp:1296
pgl::Polygon::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the polygon's x-coordinates by a factor in place.
Definition transformations.hpp:1816
pgl::Polygon::scaledDownY
constexpr Polygon scaledDownY(const OtherNumber scalar) const
Returns the polygon with its y-coordinates divided by a divisor.
pgl::Polygon::Polygon
constexpr Polygon()=default
Creates a polygon with no vertex.
pgl::Polygon::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the polygon's y-coordinates by a divisor in place.
Definition transformations.hpp:1873
pgl::Polygon::size
constexpr std::size_t size() const
Returns the number of vertices in the polygon.
Definition polygon.hpp:259
pgl::Polygon::untangle
constexpr void untangle()
Makes the polygon simple in place by uncrossing its boundary.
Definition transformations.hpp:1731
pgl::Polygon::rotate90
constexpr void rotate90(int k=1)
Rotates the polygon by 90k degrees around the origin in place.
Definition transformations.hpp:1724
pgl::Polygon::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the polygon's y-coordinates by a factor in place.
Definition transformations.hpp:1835
pgl::Polygon::scaledUpX
constexpr Polygon scaledUpX(const OtherNumber scalar) const
Returns the polygon with its x-coordinates multiplied by a factor.
pgl::Polygon::rotated90
constexpr Polygon rotated90(int k=1) const
Returns the polygon rotated by 90k degrees around the origin.
Definition transformations.hpp:1714
pgl::Polygon::scaledDownX
constexpr Polygon scaledDownX(const OtherNumber scalar) const
Returns the polygon with its x-coordinates divided by a divisor.
pgl::Polygon::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the polygon's x-coordinates by a divisor in place.
Definition transformations.hpp:1854
pgl::Polyline
Open polygonal chain stored in traversal order; may self-intersect.
Definition polyline.hpp:69
pgl::Polyline::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the polyline's y-coordinates by a factor in place.
Definition transformations.hpp:2042
pgl::Polyline::rotate90
constexpr void rotate90(int k=1)
Rotates the polyline by 90k degrees around the origin in place.
Definition transformations.hpp:2004
pgl::Polyline::Polyline
constexpr Polyline()=default
Creates a polyline with no vertex.
pgl::Polyline::flipped
constexpr Polyline flipped(const OldSegment &oldEdge, const NewSegment &newEdge) const
Returns the polyline with oldEdge flipped to newEdge.
pgl::Polyline::flippable
constexpr bool flippable(const OldSegment &oldEdge, const NewSegment &newEdge) const
Tests whether oldEdge can be flipped to newEdge.
Definition transformations.hpp:2156
pgl::Polyline< EPoint >::vertices
constexpr std::vector< PointType > vertices() const
Definition polyline.hpp:570
pgl::Polyline::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the polyline's x-coordinates by a factor in place.
Definition transformations.hpp:2023
pgl::Polyline::flip
constexpr void flip(const OldSegment &oldEdge, const NewSegment &newEdge)
Flips oldEdge to newEdge in place.
Definition transformations.hpp:2172
pgl::Polyline::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the polyline's x-coordinates by a divisor in place.
Definition transformations.hpp:2061
pgl::Polyline::rotated90
constexpr Polyline rotated90(int k=1) const
Returns the polyline rotated by 90k degrees around the origin.
Definition transformations.hpp:1994
pgl::Polyline::scaledUpX
constexpr Polyline scaledUpX(const OtherNumber scalar) const
Returns the polyline with its x-coordinates multiplied by a factor.
pgl::Polyline::scaledDownX
constexpr Polyline scaledDownX(const OtherNumber scalar) const
Returns the polyline with its x-coordinates divided by a divisor.
pgl::Polyline::size
constexpr std::size_t size() const
Returns the number of vertices in the polyline.
Definition polyline.hpp:388
pgl::Polyline::scaledUpY
constexpr Polyline scaledUpY(const OtherNumber scalar) const
Returns the polyline with its y-coordinates multiplied by a factor.
pgl::Polyline::scaledDownY
constexpr Polyline scaledDownY(const OtherNumber scalar) const
Returns the polyline with its y-coordinates divided by a divisor.
pgl::Polyline::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the polyline's y-coordinates by a divisor in place.
Definition transformations.hpp:2080
pgl::Ray
Half-infinite line starting from one source point plus optional ray label.
Definition ray.hpp:51
pgl::Ray::scaledDownY
constexpr Ray scaledDownY(const OtherNumber scalar) const
Returns the ray with its y-coordinates divided by a divisor.
pgl::Ray::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the ray's x-coordinates by a divisor in place.
Definition transformations.hpp:1047
pgl::Ray::operator-=
constexpr Ray & operator-=(const OtherPoint &translation)
Translates the ray by the negation of the given point in place.
pgl::Ray::Ray
constexpr Ray()=default
Creates the degenerate ray (0,0)--(0,0)->.
pgl::Ray::scaledUpY
constexpr Ray scaledUpY(const OtherNumber scalar) const
Returns the ray with its y-coordinates multiplied by a factor.
pgl::Ray::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the ray's y-coordinates by a divisor in place.
Definition transformations.hpp:1060
pgl::Ray::operator+=
constexpr Ray & operator+=(const OtherPoint &translation)
Translates the ray by the given point in place.
pgl::Ray::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the ray's y-coordinates by a factor in place.
Definition transformations.hpp:1034
pgl::Ray::target
constexpr const PointType & target() const
Returns the second stored point defining the direction.
Definition ray.hpp:193
pgl::Ray::rotate90
constexpr void rotate90(int k=1)
Rotates the ray by 90k degrees around the origin in place.
Definition transformations.hpp:1008
pgl::Ray::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the ray's x-coordinates by a factor in place.
Definition transformations.hpp:1021
pgl::Ray::scaledUpX
constexpr Ray scaledUpX(const OtherNumber scalar) const
Returns the ray with its x-coordinates multiplied by a factor.
pgl::Ray::scaledDownX
constexpr Ray scaledDownX(const OtherNumber scalar) const
Returns the ray with its x-coordinates divided by a divisor.
pgl::Ray::source
constexpr const PointType & source() const
Returns the source point of the ray.
Definition ray.hpp:181
pgl::Ray::rotated90
constexpr Ray rotated90(int k=1) const
Returns the ray rotated by 90k degrees around the origin.
Definition transformations.hpp:1003
pgl::Rectangle
Axis-aligned rectangle stored by minimum and maximum corners.
Definition rectangle.hpp:75
pgl::Rectangle::rotated90
constexpr Rectangle rotated90(int k=1) const
Returns the rectangle rotated by 90k degrees around the origin.
Definition transformations.hpp:1157
pgl::Rectangle::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the rectangle's y-coordinates by a factor in place.
Definition transformations.hpp:1202
pgl::Rectangle::operator+=
constexpr Rectangle & operator+=(const OtherPoint &translation)
Translates both stored corners in place.
pgl::Rectangle::operator-=
constexpr Rectangle & operator-=(const OtherPoint &translation)
Translates both stored corners by the opposite vector in place.
pgl::Rectangle::scaledDownX
constexpr Rectangle scaledDownX(const OtherNumber scalar) const
Returns the rectangle with its x-coordinates divided by a divisor.
pgl::Rectangle::min
constexpr const PointType & min() const
Returns the minimum corner (min x, min y).
Definition rectangle.hpp:347
pgl::Rectangle< PointType >::empty
constexpr bool empty() const
Definition rectangle.hpp:290
pgl::Rectangle::rotate90
constexpr void rotate90(int k=1)
Rotates the rectangle by 90k degrees around the origin in place.
Definition transformations.hpp:1166
pgl::Rectangle::scaledDownY
constexpr Rectangle scaledDownY(const OtherNumber scalar) const
Returns the rectangle with its y-coordinates divided by a divisor.
pgl::Rectangle::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the rectangle's y-coordinates by a divisor in place.
Definition transformations.hpp:1238
pgl::Rectangle::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the rectangle's x-coordinates by a divisor in place.
Definition transformations.hpp:1220
pgl::Rectangle::scaledUpX
constexpr Rectangle scaledUpX(const OtherNumber scalar) const
Returns the rectangle with its x-coordinates multiplied by a factor.
pgl::Rectangle::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the rectangle's x-coordinates by a factor in place.
Definition transformations.hpp:1184
pgl::Rectangle::max
constexpr const PointType & max() const
Returns the maximum corner (max x, max y).
Definition rectangle.hpp:359
pgl::Rectangle< PointType >::Rectangle
constexpr Rectangle()
Definition rectangle.hpp:120
pgl::Rectangle::scaledUpY
constexpr Rectangle scaledUpY(const OtherNumber scalar) const
Returns the rectangle with its y-coordinates multiplied by a factor.
pgl::Segment
Unoriented closed segment between two endpoints plus optional segment label.
Definition segment.hpp:58
pgl::Segment::scaledUpX
constexpr Segment scaledUpX(const OtherNumber scalar) const
Returns the segment with its x-coordinates multiplied by a factor.
pgl::Segment::rotate90
constexpr void rotate90(int k=1)
Rotates the segment by 90k degrees around the origin in place.
Definition transformations.hpp:235
pgl::Segment::operator-=
constexpr Segment & operator-=(const OtherPoint &translation)
Translates the segment by the negation of the given point in place.
pgl::Segment::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the segment's y-coordinates by a divisor in place.
Definition transformations.hpp:291
pgl::Segment::scaledDownY
constexpr Segment scaledDownY(const OtherNumber scalar) const
Returns the segment with its y-coordinates divided by a divisor.
pgl::Segment::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the segment's y-coordinates by a factor in place.
Definition transformations.hpp:263
pgl::Segment::scaledUpY
constexpr Segment scaledUpY(const OtherNumber scalar) const
Returns the segment with its y-coordinates multiplied by a factor.
pgl::Segment::max
constexpr const PointType & max() const
Returns the largest stored endpoint.
Definition segment.hpp:199
pgl::Segment::min
constexpr const PointType & min() const
Returns the smallest stored endpoint.
Definition segment.hpp:190
pgl::Segment::rotated90
constexpr Segment rotated90(int k=1) const
Returns the segment rotated by 90k degrees around the origin.
Definition transformations.hpp:230
pgl::Segment::operator+=
constexpr Segment & operator+=(const OtherPoint &translation)
Translates the segment by the given point in place.
pgl::Segment::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the segment's x-coordinates by a factor in place.
Definition transformations.hpp:249
pgl::Segment::scaledDownX
constexpr Segment scaledDownX(const OtherNumber scalar) const
Returns the segment with its x-coordinates divided by a divisor.
pgl::Segment::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the segment's x-coordinates by a divisor in place.
Definition transformations.hpp:277
pgl::Shape
Runtime variant wrapper over the supported primitive shapes.
Definition shape.hpp:160
pgl::Transformation
Affine transformation stored as a 2x3 matrix.
Definition transformation.hpp:32
pgl::Transformation::ty
constexpr Number ty() const
Returns the translation added to the second coordinate.
Definition transformation.hpp:173
pgl::Transformation::a
constexpr Number a() const
Returns the row-0, column-0 matrix entry.
Definition transformation.hpp:163
pgl::Transformation::d
constexpr Number d() const
Returns the row-1, column-1 matrix entry.
Definition transformation.hpp:169
pgl::Transformation::determinant
constexpr auto determinant() const
Returns the determinant of the linear (non-translation) part.
Definition transformation.hpp:182
pgl::Transformation::tx
constexpr Number tx() const
Returns the translation added to the first coordinate.
Definition transformation.hpp:171
pgl::Transformation::c
constexpr Number c() const
Returns the row-1, column-0 matrix entry.
Definition transformation.hpp:167
pgl::Transformation::b
constexpr Number b() const
Returns the row-0, column-1 matrix entry.
Definition transformation.hpp:165
pgl::Triangle
Closed triangle stored by three vertices.
Definition triangle.hpp:53
pgl::Triangle::operator-=
constexpr Triangle & operator-=(const OtherPoint &translation)
Translates all vertices by the opposite of a point in place.
pgl::Triangle::b
constexpr const PointType & b() const
Returns the second vertex.
Definition triangle.hpp:217
pgl::Triangle< EPoint >::Triangle
constexpr Triangle()=default
pgl::Triangle::a
constexpr const PointType & a() const
Returns the first vertex.
Definition triangle.hpp:208
pgl::Triangle::operator+=
constexpr Triangle & operator+=(const OtherPoint &translation)
Translates all vertices by a point in place.
pgl::Triangle::scaledDownX
constexpr Triangle scaledDownX(const OtherNumber scalar) const
Returns the triangle with its x-coordinates divided by a divisor.
pgl::Triangle::scaleUpX
constexpr void scaleUpX(const OtherNumber scalar)
Multiplies the triangle's x-coordinates by a factor in place.
Definition transformations.hpp:1341
pgl::Triangle::scaledUpX
constexpr Triangle scaledUpX(const OtherNumber scalar) const
Returns the triangle with its x-coordinates multiplied by a factor.
pgl::Triangle::scaleUpY
constexpr void scaleUpY(const OtherNumber scalar)
Multiplies the triangle's y-coordinates by a factor in place.
Definition transformations.hpp:1355
pgl::Triangle::scaledDownY
constexpr Triangle scaledDownY(const OtherNumber scalar) const
Returns the triangle with its y-coordinates divided by a divisor.
pgl::Triangle::rotate90
constexpr void rotate90(int k=1)
Rotates the triangle by 90k degrees around the origin in place.
Definition transformations.hpp:1327
pgl::Triangle::scaledUpY
constexpr Triangle scaledUpY(const OtherNumber scalar) const
Returns the triangle with its y-coordinates multiplied by a factor.
pgl::Triangle::scaleDownY
constexpr void scaleDownY(const OtherNumber scalar)
Divides the triangle's y-coordinates by a divisor in place.
Definition transformations.hpp:1383
pgl::Triangle::scaleDownX
constexpr void scaleDownX(const OtherNumber scalar)
Divides the triangle's x-coordinates by a divisor in place.
Definition transformations.hpp:1369
pgl::Triangle::rotated90
constexpr Triangle rotated90(int k=1) const
Returns the triangle rotated by 90k degrees around the origin.
Definition transformations.hpp:1322
pgl::Triangle::c
constexpr const PointType & c() const
Returns the third vertex.
Definition triangle.hpp:226