blocks|key|10421|text|最常见的方法是将点放入K-D树或类似的树中：https://en.wikipedia.org/wiki/K-d_tree|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|10422|要查找圆内的点，请按距圆心的距离递增的顺序获得点的列表，并在距离超过圆半径时停止。|10423|要按距离递增的顺序获得点的列表，您可以使用优先级队列，该队列可以同时包含点和树的内部节点，这允许您按距离的顺序删除它们。|10424|对于点(叶子)，距离就是点到中心点的距离。对于内部节点，距离是从中心点到可能位于该节点中的任何点的最小距离。|10425|要进行搜索，只需将树的根放入优先级队列，然后重复：|10426|10427|删除优先级队列的头；|ordered-list-item|10428|如果队列头是一个点，则它是树中尚未返回的最近点。您知道这一点，因为如果任何内部节点可能有一个更近的点，那么它将首先从优先级队列返回；|10429|如果队列的头部是内部节点，则将其子节点放回到队列|10430|中|10431|这将按照与中心点的距离递增的顺序生成树中的所有点。|10432|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/K-d_tree^0|M|12|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|15|8|@]|9|@$A|16|B|17|1|18]]|C|$]]|$1|D|3|E|5|6|7|19|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|1A|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|1B|8|@]|9|@]|C|$]]|$1|J|3|K|5|6|7|1C|8|@]|9|@]|C|$]]|$1|L|3|-4|5|6|7|1D|8|@]|9|@]|C|$]]|$1|M|3|N|5|O|7|1E|8|@]|9|@]|C|$]]|$1|P|3|Q|5|O|7|1F|8|@]|9|@]|C|$]]|$1|R|3|S|5|O|7|1G|8|@]|9|@]|C|$]]|$1|T|3|U|5|6|7|1H|8|@]|9|@]|C|$]]|$1|V|3|W|5|6|7|1I|8|@]|9|@]|C|$]]|$1|X|3|-4|5|6|7|1J|8|@]|9|@]|C|$]]]|Y|$Z|$5|10|11|12|C|$13|14]]]]

The most common way is to put the points into a K-D tree or similar: <a href="https://en.wikipedia.org/wiki/K-d_tree" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/K-d_tree</a>

To find the points within a circle, you get the list of points in order of increasing distance from the center, and stop when the distance exceeds the circle radius.

To get list of points in order of increasing distance, you can use a priority queue that can hold both points and internal nodes of the tree, which lets you remove them in order of distance.

For points (leaves), the distance is just the distance of the point from the center point. For internal nodes, the distance is the smallest distance from the center point to any point that could possibly be in that node.

To search, you just put the root of the tree in the priority queue, and repeat:

<ol>
<li>Remove the head of the priority queue;</li>
<li>If the head of the queue was a point, then it is the closest point in the tree that you have not yet returned. You know this, because if any internal node could possibly have a closer point, then it would have been returned first from the priority queue;</li>
<li>If the head of the queue was an internal node, then put its children back into the queue</li>
</ol>

This will produce all the points in the tree in order of increasing distance from the center point.

Here is a picture to illustrate the problem:<img src="https://i.stack.imgur.com/OE0Gw.jpg" alt="picture and features">

In the picture there are some feature points shown as blue crosses. I know the coordinate <code>(x,y)</code> for all of the features. Now I want to query which features are inside the circle area (green circle). In practice, there are around 500 features and 300 queries (300 different circles, different centers and radius). I know the parameters (position, radius) of circles. Is there any good algorithm which can do this task? 

Current I have two ideas.

<ol>
<li>Most stupid one, just iterate through all of the features in each
query. This is slower.</li>
<li>A rough idea. Separate the whole picture to some sub-pictures. Put features into a tree structure according to sub-pictures, if features in the same sub-pictures, then put in the same leaf. In each query, find out which sub-picture are covered by the circle and check all of the feature in these sub-pictures.</li>
</ol>

Does anyone out there have any better ideas?

Query points in circle areas

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

这里有一张图片来说明这个问题：​在图片中，有一些特征点显示为蓝色十字。我知道所有功能的坐标(x,y)。现在我想查询哪些特征在圆区域内(绿色圆)。在实践中，大约有500个特征和300个查询(300个不同的圆，不同的中心和半径)。我知道圆的参数(位置、半径)。有没有好的算法可以完成这个任务？目前我有两个想法。最愚蠢的一个，...

查询圆区域中的点-腾讯云开发者社区-腾讯云

问查询圆区域中的点
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问查询圆区域中的点EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问查询圆区域中的点
EN