From e3fbcc9f29a1b1c83b23a4cef3819631fd3117d0 Mon Sep 17 00:00:00 2001 From: Star Rauchenberger Date: Sun, 12 May 2024 18:45:21 -0400 Subject: Subway map hover detection with a quadtree --- CMakeLists.txt | 1 + src/subway_map.cpp | 37 ++++++ src/subway_map.h | 10 ++ vendor/quadtree/Box.h | 67 ++++++++++ vendor/quadtree/LICENSE | 21 +++ vendor/quadtree/Quadtree.h | 315 +++++++++++++++++++++++++++++++++++++++++++++ vendor/quadtree/Vector2.h | 47 +++++++ 7 files changed, 498 insertions(+) create mode 100644 vendor/quadtree/Box.h create mode 100644 vendor/quadtree/LICENSE create mode 100644 vendor/quadtree/Quadtree.h create mode 100644 vendor/quadtree/Vector2.h diff --git a/CMakeLists.txt b/CMakeLists.txt index 99b15f8..d6170a1 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -22,6 +22,7 @@ include_directories( ${yaml-cpp_INCLUDE_DIRS} ${OpenSSL_INCLUDE_DIRS} vendor/whereami + vendor ) find_path(SYSTEM_INCLUDE_DIR zlib.h) diff --git a/src/subway_map.cpp b/src/subway_map.cpp index 0aa7df3..230a256 100644 --- a/src/subway_map.cpp +++ b/src/subway_map.cpp @@ -25,6 +25,13 @@ SubwayMap::SubwayMap(wxWindow *parent) : wxPanel(parent, wxID_ANY) { return; } + tree_ = std::make_unique>( + quadtree::Box{0, 0, static_cast(map_image_.GetWidth()), + static_cast(map_image_.GetHeight())}); + for (const SubwayItem &subway_item : GD_GetSubwayItems()) { + tree_->add(subway_item.id); + } + Redraw(); Bind(wxEVT_PAINT, &SubwayMap::OnPaint, this); @@ -47,6 +54,30 @@ void SubwayMap::OnPaint(wxPaintEvent &event) { } void SubwayMap::OnMouseMove(wxMouseEvent &event) { + int mouse_x = std::clamp( + (event.GetX() - render_x_) * map_image_.GetWidth() / render_width_, + 0, map_image_.GetWidth() - 1); + int mouse_y = std::clamp( + (event.GetY() - render_y_) * map_image_.GetWidth() / render_width_, + 0, map_image_.GetHeight() - 1); + + std::vector hovered = tree_->query( + {static_cast(mouse_x), static_cast(mouse_y), 2, 2}); + std::optional new_hovered_item; + if (!hovered.empty()) { + new_hovered_item = hovered[0]; + } + + if (new_hovered_item != hovered_item_) { + if (new_hovered_item) { + wxLogVerbose("Hovered: %d", *new_hovered_item); + } else { + wxLogVerbose("Un-hovered: %d", *hovered_item_); + } + + hovered_item_ = new_hovered_item; + } + event.Skip(); } @@ -121,3 +152,9 @@ void SubwayMap::Redraw() { } } } + +quadtree::Box SubwayMap::GetItemBox::operator()(const int& id) const { + const SubwayItem &subway_item = GD_GetSubwayItem(id); + return {static_cast(subway_item.x), static_cast(subway_item.y), + AREA_ACTUAL_SIZE, AREA_ACTUAL_SIZE}; +} diff --git a/src/subway_map.h b/src/subway_map.h index e375750..6cb5c63 100644 --- a/src/subway_map.h +++ b/src/subway_map.h @@ -7,8 +7,12 @@ #include #endif +#include +#include #include +#include + class SubwayMap : public wxPanel { public: SubwayMap(wxWindow *parent); @@ -29,7 +33,13 @@ class SubwayMap : public wxPanel { int render_y_ = 0; int render_width_ = 0; int render_height_ = 0; + + struct GetItemBox { + quadtree::Box operator()(const int &id) const; + }; + std::unique_ptr> tree_; + std::optional hovered_item_; }; #endif /* end of include guard: SUBWAY_MAP_H_BD2D843E */ diff --git a/vendor/quadtree/Box.h b/vendor/quadtree/Box.h new file mode 100644 index 0000000..65182bf --- /dev/null +++ b/vendor/quadtree/Box.h @@ -0,0 +1,67 @@ +#pragma once + +#include "Vector2.h" + +namespace quadtree +{ + +template +class Box +{ +public: + T left; + T top; + T width; // Must be positive + T height; // Must be positive + + constexpr Box(T Left = 0, T Top = 0, T Width = 0, T Height = 0) noexcept : + left(Left), top(Top), width(Width), height(Height) + { + + } + + constexpr Box(const Vector2& position, const Vector2& size) noexcept : + left(position.x), top(position.y), width(size.x), height(size.y) + { + + } + + constexpr T getRight() const noexcept + { + return left + width; + } + + constexpr T getBottom() const noexcept + { + return top + height; + } + + constexpr Vector2 getTopLeft() const noexcept + { + return Vector2(left, top); + } + + constexpr Vector2 getCenter() const noexcept + { + return Vector2(left + width / 2, top + height / 2); + } + + constexpr Vector2 getSize() const noexcept + { + return Vector2(width, height); + } + + constexpr bool contains(const Box& box) const noexcept + { + return left <= box.left && box.getRight() <= getRight() && + top <= box.top && box.getBottom() <= getBottom(); + } + + constexpr bool intersects(const Box& box) const noexcept + { + return !(left >= box.getRight() || getRight() <= box.left || + top >= box.getBottom() || getBottom() <= box.top); + } +}; + +} \ No newline at end of file diff --git a/vendor/quadtree/LICENSE b/vendor/quadtree/LICENSE new file mode 100644 index 0000000..1b226d3 --- /dev/null +++ b/vendor/quadtree/LICENSE @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2019 Pierre Vigier + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/vendor/quadtree/Quadtree.h b/vendor/quadtree/Quadtree.h new file mode 100644 index 0000000..06097c5 --- /dev/null +++ b/vendor/quadtree/Quadtree.h @@ -0,0 +1,315 @@ +#pragma once + +#include +#include +#include +#include +#include +#include +#include "Box.h" + +namespace quadtree +{ + +template, typename Float = float> +class Quadtree +{ + static_assert(std::is_convertible_v, Box>, + "GetBox must be a callable of signature Box(const T&)"); + static_assert(std::is_convertible_v, bool>, + "Equal must be a callable of signature bool(const T&, const T&)"); + static_assert(std::is_arithmetic_v); + +public: + Quadtree(const Box& box, const GetBox& getBox = GetBox(), + const Equal& equal = Equal()) : + mBox(box), mRoot(std::make_unique()), mGetBox(getBox), mEqual(equal) + { + + } + + void add(const T& value) + { + add(mRoot.get(), 0, mBox, value); + } + + void remove(const T& value) + { + remove(mRoot.get(), mBox, value); + } + + std::vector query(const Box& box) const + { + auto values = std::vector(); + query(mRoot.get(), mBox, box, values); + return values; + } + + std::vector> findAllIntersections() const + { + auto intersections = std::vector>(); + findAllIntersections(mRoot.get(), intersections); + return intersections; + } + + Box getBox() const + { + return mBox; + } + +private: + static constexpr auto Threshold = std::size_t(16); + static constexpr auto MaxDepth = std::size_t(8); + + struct Node + { + std::array, 4> children; + std::vector values; + }; + + Box mBox; + std::unique_ptr mRoot; + GetBox mGetBox; + Equal mEqual; + + bool isLeaf(const Node* node) const + { + return !static_cast(node->children[0]); + } + + Box computeBox(const Box& box, int i) const + { + auto origin = box.getTopLeft(); + auto childSize = box.getSize() / static_cast(2); + switch (i) + { + // North West + case 0: + return Box(origin, childSize); + // Norst East + case 1: + return Box(Vector2(origin.x + childSize.x, origin.y), childSize); + // South West + case 2: + return Box(Vector2(origin.x, origin.y + childSize.y), childSize); + // South East + case 3: + return Box(origin + childSize, childSize); + default: + assert(false && "Invalid child index"); + return Box(); + } + } + + int getQuadrant(const Box& nodeBox, const Box& valueBox) const + { + auto center = nodeBox.getCenter(); + // West + if (valueBox.getRight() < center.x) + { + // North West + if (valueBox.getBottom() < center.y) + return 0; + // South West + else if (valueBox.top >= center.y) + return 2; + // Not contained in any quadrant + else + return -1; + } + // East + else if (valueBox.left >= center.x) + { + // North East + if (valueBox.getBottom() < center.y) + return 1; + // South East + else if (valueBox.top >= center.y) + return 3; + // Not contained in any quadrant + else + return -1; + } + // Not contained in any quadrant + else + return -1; + } + + void add(Node* node, std::size_t depth, const Box& box, const T& value) + { + assert(node != nullptr); + assert(box.contains(mGetBox(value))); + if (isLeaf(node)) + { + // Insert the value in this node if possible + if (depth >= MaxDepth || node->values.size() < Threshold) + node->values.push_back(value); + // Otherwise, we split and we try again + else + { + split(node, box); + add(node, depth, box, value); + } + } + else + { + auto i = getQuadrant(box, mGetBox(value)); + // Add the value in a child if the value is entirely contained in it + if (i != -1) + add(node->children[static_cast(i)].get(), depth + 1, computeBox(box, i), value); + // Otherwise, we add the value in the current node + else + node->values.push_back(value); + } + } + + void split(Node* node, const Box& box) + { + assert(node != nullptr); + assert(isLeaf(node) && "Only leaves can be split"); + // Create children + for (auto& child : node->children) + child = std::make_unique(); + // Assign values to children + auto newValues = std::vector(); // New values for this node + for (const auto& value : node->values) + { + auto i = getQuadrant(box, mGetBox(value)); + if (i != -1) + node->children[static_cast(i)]->values.push_back(value); + else + newValues.push_back(value); + } + node->values = std::move(newValues); + } + + bool remove(Node* node, const Box& box, const T& value) + { + assert(node != nullptr); + assert(box.contains(mGetBox(value))); + if (isLeaf(node)) + { + // Remove the value from node + removeValue(node, value); + return true; + } + else + { + // Remove the value in a child if the value is entirely contained in it + auto i = getQuadrant(box, mGetBox(value)); + if (i != -1) + { + if (remove(node->children[static_cast(i)].get(), computeBox(box, i), value)) + return tryMerge(node); + } + // Otherwise, we remove the value from the current node + else + removeValue(node, value); + return false; + } + } + + void removeValue(Node* node, const T& value) + { + // Find the value in node->values + auto it = std::find_if(std::begin(node->values), std::end(node->values), + [this, &value](const auto& rhs){ return mEqual(value, rhs); }); + assert(it != std::end(node->values) && "Trying to remove a value that is not present in the node"); + // Swap with the last element and pop back + *it = std::move(node->values.back()); + node->values.pop_back(); + } + + bool tryMerge(Node* node) + { + assert(node != nullptr); + assert(!isLeaf(node) && "Only interior nodes can be merged"); + auto nbValues = node->values.size(); + for (const auto& child : node->children) + { + if (!isLeaf(child.get())) + return false; + nbValues += child->values.size(); + } + if (nbValues <= Threshold) + { + node->values.reserve(nbValues); + // Merge the values of all the children + for (const auto& child : node->children) + { + for (const auto& value : child->values) + node->values.push_back(value); + } + // Remove the children + for (auto& child : node->children) + child.reset(); + return true; + } + else + return false; + } + + void query(Node* node, const Box& box, const Box& queryBox, std::vector& values) const + { + assert(node != nullptr); + assert(queryBox.intersects(box)); + for (const auto& value : node->values) + { + if (queryBox.intersects(mGetBox(value))) + values.push_back(value); + } + if (!isLeaf(node)) + { + for (auto i = std::size_t(0); i < node->children.size(); ++i) + { + auto childBox = computeBox(box, static_cast(i)); + if (queryBox.intersects(childBox)) + query(node->children[i].get(), childBox, queryBox, values); + } + } + } + + void findAllIntersections(Node* node, std::vector>& intersections) const + { + // Find intersections between values stored in this node + // Make sure to not report the same intersection twice + for (auto i = std::size_t(0); i < node->values.size(); ++i) + { + for (auto j = std::size_t(0); j < i; ++j) + { + if (mGetBox(node->values[i]).intersects(mGetBox(node->values[j]))) + intersections.emplace_back(node->values[i], node->values[j]); + } + } + if (!isLeaf(node)) + { + // Values in this node can intersect values in descendants + for (const auto& child : node->children) + { + for (const auto& value : node->values) + findIntersectionsInDescendants(child.get(), value, intersections); + } + // Find intersections in children + for (const auto& child : node->children) + findAllIntersections(child.get(), intersections); + } + } + + void findIntersectionsInDescendants(Node* node, const T& value, std::vector>& intersections) const + { + // Test against the values stored in this node + for (const auto& other : node->values) + { + if (mGetBox(value).intersects(mGetBox(other))) + intersections.emplace_back(value, other); + } + // Test against values stored into descendants of this node + if (!isLeaf(node)) + { + for (const auto& child : node->children) + findIntersectionsInDescendants(child.get(), value, intersections); + } + } +}; + +} diff --git a/vendor/quadtree/Vector2.h b/vendor/quadtree/Vector2.h new file mode 100644 index 0000000..302d73e --- /dev/null +++ b/vendor/quadtree/Vector2.h @@ -0,0 +1,47 @@ +#pragma once + +namespace quadtree +{ + +template +class Vector2 +{ +public: + T x; + T y; + + constexpr Vector2(T X = 0, T Y = 0) noexcept : x(X), y(Y) + { + + } + + constexpr Vector2& operator+=(const Vector2& other) noexcept + { + x += other.x; + y += other.y; + return *this; + } + + constexpr Vector2& operator/=(T t) noexcept + { + x /= t; + y /= t; + return *this; + } +}; + +template +constexpr Vector2 operator+(Vector2 lhs, const Vector2& rhs) noexcept +{ + lhs += rhs; + return lhs; +} + +template +constexpr Vector2 operator/(Vector2 vec, T t) noexcept +{ + vec /= t; + return vec; +} + +} -- cgit 1.4.1