1 /*
2     SPDX-FileCopyrightText: 2010 Johannes Loehnert <loehnert.kde@gmx.de>
3 
4     SPDX-License-Identifier: GPL-2.0-or-later
5 */
6 
7 #include "pointfinder.h"
8 
9 #include <QLineF>
10 
PointFinder(int width,int height,qreal radius)11 PointFinder::PointFinder(int width, int height, qreal radius) {
12     m_height = height;
13     m_width = width;
14     m_radius = radius;
15     m_xbins = int(m_width / m_radius) + 1;
16     m_ybins = int(m_height / m_radius) + 1;
17 
18     m_boxes = new QList<QPointF>* [m_xbins];
19     for (int nx=0; nx < m_xbins; nx++) m_boxes[nx] = new QList<QPointF> [m_ybins];
20 
21 
22 }
23 
~PointFinder()24 PointFinder::~PointFinder() {
25     for (int nx=0; nx < m_xbins; nx++) delete[] m_boxes[nx];
26     delete[] m_boxes;
27 }
28 
append(QPointF point)29 void PointFinder::append(QPointF point) {
30     int nx = point.x() / m_radius;
31     int ny = point.y() / m_radius;
32     m_points.append(point);
33     if (nx >= 0 && ny >= 0 && nx < m_xbins && ny < m_ybins) {
34         m_boxes[nx][ny].append(point);
35     }
36 }
37 
points()38 QList<QPointF> PointFinder::points() {
39     return m_points;
40 }
41 
find_neighbours(QPointF point)42 QList<QPointF> PointFinder::find_neighbours(QPointF point) {
43     QList<QPointF> result;
44     int nx = point.x() / m_radius;
45     int ny = point.y() / m_radius;
46     for (int nnx=nx-1; nnx <= nx+1; nnx++) {
47         if (nnx < 0 || nnx >= m_xbins) continue;
48         for (int nny = ny-1; nny <= ny+1; nny++) {
49             if (nny < 0 || nny >= m_ybins) continue;
50             for (int i=0; i<m_boxes[nnx][nny].size(); i++) {
51                 QPointF other = m_boxes[nnx][nny][i];
52                 if (QLineF(point, other).length() < m_radius &&
53                             point != other) {
54                     result.append(other);
55                 }
56             }
57         }
58     }
59     return result;
60 }
61