geometry - resueltos - perimetro de un circulo

Encontrar puntos de manera eficiente dentro de un sector de círculo.

Question

Tengo un conjunto de 2d puntos distribuidos al azar. Necesito realizar una operación que requiera mucho tiempo en un pequeño subconjunto de estos puntos, pero primero tengo que averiguar en qué puntos necesito realizar esta operación que requiere mucho tiempo. Para determinar qué puntos necesito deben pasar una serie de criterios geométricos.

El criterio más básico es si están a cierta distancia de un punto específico. El segundo criterio más básico es si están contenidos dentro de un sector circular (un cono 2-D) que se extiende desde ese punto específico. (Editar: esta operación se llama regularmente con un punto específico diferente cada vez pero con el mismo conjunto de puntos 2d).

Mi idea inicial fue crear una cuadrícula que contenga los puntos 2d, luego iterar a lo largo de la cuadrícula de agarre de cono que se interseca. Dependiendo del tamaño de la cuadrícula, filtraría la gran mayoría de los 2d puntos innecesarios. Desafortunadamente, el sistema integrado en el que estoy ejecutando está severamente limitado por la memoria, por lo que una matriz 2D grande (según nuestros estándares no es la de nadie) requeriría demasiada memoria.

He estado tratando de investigar el uso de árboles KD para acelerar el cálculo, pero no he podido encontrar un algoritmo que relacione sectores circulares y árboles-kd.

¿Existe un algoritmo eficiente para encontrar qué puntos 2d se encuentran dentro de un sector de círculo?

Solo una nota de que nuestro sistema en particular es lento tanto en matemática de punto flotante como en trigonometría, por lo que una solución que implique menos de esos es superior y requiere mucho.

Answer 1

Es posible verificar si un punto está dentro de un sector con solo aritmética de enteros y las operaciones básicas de suma, resta y multiplicación.

Para que un punto esté dentro de un sector circular , tiene que cumplir las siguientes pruebas:

1. Debe colocarse en el sentido contrario a las agujas del reloj desde el "brazo" de inicio del sector.
2. Debe colocarse en el sentido de las agujas del reloj desde el extremo del sector.

3. Tiene que estar más cerca del centro del círculo que el radio del sector.

Pruebas en el sentido de las agujas del reloj

Para probar si un vector v2 está en el sentido de las agujas del reloj a otro vector v1, haga lo siguiente:

1. Encuentra el vector normal en sentido antihorario de v1. El vector normal está en un ángulo de 90 grados con respecto al vector original. Esto es sencillo de hacer : si v1=(x1,y1) , entonces la normal en sentido antihorario es n1=(-y1,x1) .

2. Encuentra el tamaño de la proyección de v2 en la normal. Esto se puede hacer calculando el producto punto de v2 y lo normal.

   projection = v2.x*n1.x + v2.y*n1.y

3. Si la proyección es un número positivo, entonces v2 se posiciona en sentido contrario a las agujas del reloj a v1. De lo contrario, v2 es en sentido horario a v1.

Aquí hay un ejemplo a la izquierda:

Y un ejemplo en el sentido de las agujas del reloj:

Los pasos se pueden combinar:

function areClockwise(v1, v2) {
return -v1.x*v2.y + v1.y*v2.x > 0;
}

Prueba de radio

La prueba de radio es sencilla. Solo verifique si la distancia del punto desde el centro del círculo es menor que el radio deseado. Para evitar calcular las raíces cuadradas, podemos comparar el cuadrado de la distancia con el cuadrado del radio.

function isWithinRadius(v, radiusSquared) {
return v.x*v.x + v.y*v.y <= radiusSquared;
}

Poniendo todo junto

La prueba completa del sector se ve algo así como:

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);
}

La siguiente página de muestra lo demuestra sobre varios miles de puntos. Puede experimentar con el código en: http://jsbin.com/oriyes/8/edit .

Código fuente de muestra

<!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("&#8226;")
.addClass(isInside ? "in" : "out")
.appendTo($canvas);
}
});
</script>
</head>
<body>
<div id="canvas" class="canvas"></div>
</body>
</html>

Notas, advertencias y limitaciones.

1. Tienes que especificar los límites del sector en términos de vectores. La captura de pantalla anterior, por ejemplo, muestra un sector que se extiende entre los vectores de (4,1) y (1,4).

2. Si su sector se especifica en otros términos, por ejemplo, ángulos, primero tendrá que convertirlo en vectores, por ejemplo, usando la función tan() . Afortunadamente, solo tienes que hacer esto una vez.

3. La lógica aquí funciona para sectores con un ángulo interno de menos de 180 grados. Si sus sectores pueden abarcar un ángulo mayor, tendrá que modificarlo.

4. Además, el código supone que usted sabe cuál de los vectores delimitadores del sector es el "inicio" y cuál es el "final". Si no lo hace, puede ejecutar areClockwise() en ellos para averiguarlo.

5. Tenga en cuenta que si bien todo esto se puede hacer con aritmética de enteros, tanto las pruebas de radio como las de las agujas del reloj utilizan un mayor rango de números, debido a la cuadratura de las x y las y multiplicándolas. Asegúrese de usar números enteros de bits suficientes para mantener los resultados.

Answer 2

Sé que no quieres trigonometría, pero podrías convertir cada punto (en tu subconjunto) a sus coordenadas polares (donde el origen es tu punto específico) y el umbral r,theta donde r < R y T1 < theta < T2 correspondiente a el sector. ¡Es ciertamente memoria eficiente!