我有一组随机分布的二维点。我需要在这些点的一个小子集上执行耗时操作，但首先需要确定哪些点需要执行此操作。要确定我需要的点，它们必须通过一系列几何标准。
最基本的标准是它们是否与特定点距离在一定范围内。第二个最基本的标准是它们是否包含在从该特定点延伸出来的圆锥形区域（2-D锥）内。(编辑：每次使用不同的特定点但相同的2d点集调用此操作。)
我最初的想法是创建一个包含2d点的网格，然后沿着圆锥体迭代抓取它相交的网格方块。根据网格的大小，它会过滤掉大多数不需要的2d点。不幸的是，我运行的嵌入式系统严重受到内存限制，因此大型（按我们的标准而非其他人的标准）的2D数组将占用太多内存。
我一直在尝试研究使用KD树加速计算，但我没有找到一个涉及圆锥体和kd树的算法。
是否有一种有效的算法可以找到在圆锥体内的二维点？
请注意，我们特定的系统在浮点数和三角函数方面都很慢，因此需要较少使用这些内容的解决方案。
可以使用整数算术和基本的加、减、乘法运算来检查一个点是否在扇形内。
要使一个点位于圆形扇区内，它必须通过以下测试：
它必须比扇形的半径更靠近圆心。
要测试向量v2是否顺时针旋转到另一个向量v1，需执行以下步骤：
找到v1的逆时针法向量。法向量与原始向量成90度角，这可以通过简单的方法进行计算：如果v1=(x1,y1)，则逆时针法向量为n1=(-y1,x1)。
找到v2在法向量上的投影大小。这可以通过计算v2和法向量的点积来完成。
projection = v2.x*n1.x + v2.y*n1.y
如果投影是正数，则v2相对于v1逆时针定位。否则，v2顺时针定位于v1。
下面是一个逆时针旋转的例子：
这是一个顺时针旋转的例子：
这些步骤可以结合起来：
function areClockwise(v1, v2) {
return -v1.x*v2.y + v1.y*v2.x > 0;
}
半径测试很简单。只需检查点离圆心的距离是否小于所需半径即可。为了避免计算平方根，我们可以将距离的平方与半径的平方进行比较。
function isWithinRadius(v, radiusSquared) {
return v.x*v.x + v.y*v.y <= radiusSquared;
}
完整的部门测试大致如下：
function isInsideSector(point, center, sectorStart, sectorEnd, radiusSquared) {
var relPoint = {
x: point.x - center.x,
y: point.y - center.y
};
return !areClockwise(sectorStart, relPoint) &&
areClockwise(sectorEnd, relPoint) &&
isWithinRadius(relPoint, radiusSquared);
}
以下示例页面在数千个点上演示了这一点。您可以在以下网址自行尝试： http://jsbin.com/oriyes/8/edit.
<!DOCTYPE html>
<html>
<head>
<script src="http://code.jquery.com/jquery-1.8.2.min.js"></script>
<style>
.canvas {
position: absolute;
background: #f4f4f4;
border: 8px solid #f4f4f4;
width: 400px;
height: 400px;
}
.dot {
position: absolute;
font: 16px Arial;
}
.out { color: #ddd; }
.in { color: #00dd44; }
</style>
<script>
function isInsideSector(point, center, sectorStart, sectorEnd, radiusSquared) {
var relPoint = {
x: point.x - center.x,
y: point.y - center.y
};
return !areClockwise(sectorStart, relPoint) &&
areClockwise(sectorEnd, relPoint) &&
isWithinRadius(relPoint, radiusSquared);
}
function areClockwise(v1, v2) {
return -v1.x*v2.y + v1.y*v2.x > 0;
}
function isWithinRadius(v, radiusSquared) {
return v.x*v.x + v.y*v.y <= radiusSquared;
}
$(function() {
var $canvas = $("#canvas");
var canvasSize = 400;
var count = 4000;
// define the sector
var center = { x: canvasSize / 2, y: canvasSize / 2 };
var sectorStart = { x: 4, y: 1 };
var sectorEnd = { x: 1, y: 4 };
var radiusSquared = canvasSize * canvasSize / 4;
// create, draw and test a number of random points
for (var i = 0; i < count; ++i) {
// generate a random point
var point = {
x: Math.random() * canvasSize,
y: Math.random() * canvasSize
};
// test if the point is inside the sector
var isInside = isInsideSector(point, center, sectorStart, sectorEnd, radiusSquared);
// draw the point
var $point = $("<div class='dot'></div>")
.css({
left: point.x - 3,
top: canvasSize - point.y - 8 })
.html("•")
.addClass(isInside ? "in" : "out")
.appendTo($canvas);
}
});
</script>
</head>
<body>
<div id="canvas" class="canvas"></div>
</body>
</html>
你必须用向量的术语来指定扇区的边界。例如，上面的截图显示一个从向量（4,1）到（1,4）延伸的扇区。
如果你的扇区是用其他术语指定的，例如角度，那么你需要先将它转换为向量，例如使用tan()函数。幸运的是，你只需要这样做一次。
此处的逻辑适用于内角小于180度的扇区。如果你的扇区可以跨越更大的角度，则需要进行修改。
此外，该代码假定你知道扇区的边界向量中哪个是“起点”，哪个是“终点”。如果不知道，可以对它们运行areClockwise()来找出。
请注意，虽然所有这些都可以使用整数算术完成，但半径和顺时针测试都使用了较大范围的数字，因为要平方x和y，并将它们相乘。请确保使用具有足够位数以容纳结果的整数。
我知道你不想学三角函数，但你可以将你子集中的每个点转换为它们的极坐标（以你特定的点为原点），并对r,theta进行阈值处理，其中r < R，T1 < theta < T2与扇区对应。这绝对是一种内存高效的方法！
@Oren Trutner的回答非常好，所以我决定制作一个可视化示例，并进行一些改进，使其在所有角度上都能正常工作。
不多说了，看下面的示例吧。
$(document).on('keypress',function (e) {
if(e.which === 13)
{
$("#calc").click();
}
});
function areClockwise(v1, v2) {
return -v1.x*v2.y + v1.y*v2.x > 0;
}
function vector(x = 0, y = 0) {
return {x:x,y:y}
}
function degToRad(degree) {
return degree * Math.PI / 180;
}
function isIn()
{
let illustration = $("#illustration");
illustration.html("");
let r = 250;
let fieldOfViewAngle = 150;
let x = Number($("#x").val());
let y = Number($("#y").val());
let startAngle = Number($("#startAngle").val());
let startSectorAngle = degToRad(startAngle);
let endSectorAngle = degToRad(startAngle+fieldOfViewAngle);
$("#startLine").attr("x2",250 + r*Math.cos(-startSectorAngle)).attr("y2",250 + r*Math.sin(-startSectorAngle));
$("#endLine").attr("x2",250 + r*Math.cos(-endSectorAngle)).attr("y2",250 + r*Math.sin(-endSectorAngle));
$("#point").attr("cx",250 +x).attr("cy",250 -y);
let sectorStartVector = vector(r * Math.cos(startSectorAngle),r * Math.sin(startSectorAngle));
let sectorEndVector = vector(r * Math.cos(endSectorAngle),r * Math.sin(endSectorAngle));
let relPoint = vector(x,y);
if(!this.areClockwise(sectorStartVector, relPoint) &&
this.areClockwise(sectorEndVector, relPoint))
$("#result").html("Result: in");
else{
$("#result").html("Result: out")
}
}.flixy {
display: flex;
flex-direction: column;
}
.flixy > div {
margin-bottom: 20px;
width:300px
}
.flixy > div > input {
float: right;
}<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<div id="result"></div>
<div class="flixy">
<div class="input-group">
<label>X</label>
<input id="x">
</div>
<div class="input-group">
<label>Y</label>
<input id="y">
</div>
<div class="input-group">
<label>Start angle</label>
<input id="startAngle">
</div>
<div class="input-group">
<label>Radius</label>
<input value="250" disabled>
</div>
<div class="input-group">
<label>Theta</label>
<input value="150" disabled>
</div>
</div>
<button onclick="isIn()" id="calc">calc</button>
<div style="width: 500px;height: 500px; overflow: visible">
<svg width="500" height="500" style="overflow: visible">
<circle cx="250" cy="250" r="250" stroke="black" stroke-width="3" fill="yellow"></circle>
<line id="startLine" x1="250" y1="250" x2="500" y2="250" style="stroke:#2fa360;stroke-width:2" />
<line id="endLine" x1="250" y1="250" x2="500" y2="250" style="stroke:#1d68a7;stroke-width:2" />
<circle id="point" cx="250" cy="250" r="5" fill="red"></circle>
</svg>
</div>