Kstars

rectangleoverlap.cpp
1/*
2 SPDX-FileCopyrightText: 2023 Hy Murveit <hy@murveit.com>
3
4 SPDX-License-Identifier: GPL-2.0-or-later
5
6 Based on https://github.com/lennig/rectangleOverlap
7 with permission from Matt Lennig
8*/
9
10#include "rectangleoverlap.h"
11#include "math.h"
12
13namespace
14{
15
16// Rotates in place the points in vertices by rotationDegrees around the center point.
17void rotate(QVector<QPointF> &vertices, const QPointF &center, double rotationDegrees)
18{
19 constexpr double convertDegreesToRadians = M_PI / 180.0;
20 const double cosAngle = cos(rotationDegrees * convertDegreesToRadians);
21 const double sinAngle = sin(rotationDegrees * convertDegreesToRadians);
22
23 for (int i = 0; i < vertices.size(); i++)
24 {
25 // Translate the vertices so that center is at 0,0.
26 const double x = vertices[i].x() - center.x();
27 const double y = vertices[i].y() - center.y();
28 // Rotate the points around the origin, then translate them back.
29 vertices[i] = QPointF(center.x() + x * cosAngle - y * sinAngle,
30 center.y() + x * sinAngle + y * cosAngle);
31 }
32}
33
34// Compute the vertices (corner points) of a possibly rotated rectangle
35// with the given center point, width and height.
36// Points are returned in the input QVector in counter-clockwise order.
37void computeVertices(
38 QVector<QPointF> &vertices, const QPointF &center, int width,
39 int height, double rotationDegrees)
40{
41 // Initialize the rectangle unrotated, then rotate if necessary.
42 const double dw = width / 2.0;
43 const double dh = height / 2.0;
44 vertices.push_back(QPoint(center.x() - dw, center.y() - dh));
45 vertices.push_back(QPoint(center.x() + dw, center.y() - dh));
46 vertices.push_back(QPoint(center.x() + dw, center.y() + dh));
47 vertices.push_back(QPoint(center.x() - dw, center.y() + dh));
48 if (rotationDegrees != 0.0)
49 rotate(vertices, center, rotationDegrees);
50}
51
52// Returns the slope of the line between the two points
53// Slope returned is guaranteed to be finite--it is 0 for horizontal
54// or vertical lines, which works for this code.
55double finiteSlope(const QPointF &p1, const QPointF &p2)
56{
57 const double dx = p2.x() - p1.x();
58 if (dx == 0) return 0.0;
59 return (p2.y() - p1.y()) / dx;
60}
61
62// Returns the axes of the rectangle.
63// Axes are lines coming from the origin that are parallel to the sides of the rectangle.
64// As this is a rectangle, getting the slope between its first two points
65// assuming they are given clockwise or counter-clockwise, will tell us
66// all we need to know about the axes. That is, the rest of the axes are either
67// parallel or perpendicular. Similarly, as finiteSlope() returns 0 for horizontal
68// or vertical lines, in either case it will give us the axes of the rectangle.
69void addAxes(QVector<QPointF> &axes, const QVector<QPointF> &vertices)
70{
71 const double s = finiteSlope(vertices[0], vertices[1]);
72 if (s != 0)
73 {
74 // Projection axes are not parallel to main axes
75 axes.push_back(QPointF(1, s));
76 axes.push_back(QPointF(1, -1 / s));
77 }
78 else
79 {
80 // Projection axes are parallel to main axes
81 axes.push_back(QPointF(1, 0));
82 axes.push_back(QPointF(0, 1));
83 }
84}
85} // namespace
86
87RectangleOverlap::RectangleOverlap(const QPointF &center, int width, int height, double rotationDegrees)
88{
89 computeVertices(m_Vertices, center, width, height, rotationDegrees);
90}
91
92bool RectangleOverlap::intersects(const QPointF &center, int width, int height, double rotationDegrees) const
93{
94 // Compute the vertices of the test rectangle
95 QVector<QPointF> testVertices;
96 computeVertices(testVertices, center, width, height, rotationDegrees);
97
99 addAxes(axes, m_Vertices);
100 addAxes(axes, testVertices);
101
102 // According to the Separating Axis Theorum, two rectangles do not overlap if none of their axes
103 // separates the projections of the points from the two rectangles. To phrase that differently,
104 // if the projections of one rectangle's vertices onto an axis overlaps with the projections
105 // of the other rectangle's vertices onto that axis, then that axis does not rule out an overlap.
106 // If none of the axes rule out an overlap, then the rectangles overlap.
107
108 for (const auto &axis : axes)
109 {
110 // Compute min and max projections of the reference rectangle's vertices of onto an axis.
111 double minRefProjection = std::numeric_limits<double>::max();
112 double maxRefProjection = std::numeric_limits<double>::lowest();
113 for (const auto &vertex : m_Vertices)
114 {
115 // Compute the dot-product projection.
116 const double projection = vertex.x() * axis.x() + vertex.y() * axis.y();
117 if (projection > maxRefProjection) maxRefProjection = projection;
118 if (projection < minRefProjection) minRefProjection = projection;
119 };
120
121 // Compute min and max projections of the test rectangle's vertices of onto an axis.
122 double minTestProjection = std::numeric_limits<double>::max();
123 double maxTextProjection = std::numeric_limits<double>::lowest();
124 for (const auto &vertex : testVertices)
125 {
126 const double projection = vertex.x() * axis.x() + vertex.y() * axis.y();
127 if (projection > maxTextProjection) maxTextProjection = projection;
128 if (projection < minTestProjection) minTestProjection = projection;
129 }
130
131 bool separated = minRefProjection > maxTextProjection || minTestProjection > maxRefProjection;
132 if (separated)
133 return false;
134 }
135 // None of the axes separate the rectangles' vertices, so they are overlapped.
136 return true;
137}
bool intersects(const QPointF &center, int width, int height, double rotationDegrees=0.0) const
Check if the input rectangle overlaps the reference rectangle.
RectangleOverlap(const QPointF &center, int width, int height, double rotationDegrees=0.0)
Constructor specifying reference rectangle.
void push_back(parameter_type value)
qsizetype size() const const
qreal x() const const
qreal y() const const
QTextStream & center(QTextStream &stream)
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Sat Dec 21 2024 17:04:45 by doxygen 1.12.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.