Ответ 1
Можно проверить, находится ли точка внутри сектора с целочисленной арифметикой и основными операциями сложения, вычитания и умножения.
Чтобы точка находилась внутри кругового сектора она должна отвечать следующим тестам:
- Он должен располагаться против часовой стрелки от начала "руки" сектора.
- Он должен располагаться по часовой стрелке от конечного рычага сектора.
-
Он должен быть ближе к центру круга, чем радиус сектора.
![For a point to be inside a, it has to meet the following tests]()
![It has to be positioned counter-clockwise from the start "arm" of the sector]()
![It has to be positioned clockwise from the end arm of the sector]()
![It has to be closer to the center of the circle than the sector's radius]()
Проверки по часовой стрелке
Чтобы проверить, равен ли вектор v2 по часовой стрелке другому вектору v1, выполните следующие действия:
-
Найдите против часовой стрелки нормальный вектор v1. Нормальный вектор находится под углом 90 градусов к исходному вектору. Это прямое выполнение: если
v1=(x1,y1), то норма против часовой стрелкиn1=(-y1,x1). -
Найдите размер проекции v2 на нормальный. Это можно сделать, вычислив dot product 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()на них, чтобы узнать. -
Обратите внимание, что, хотя все это можно сделать с помощью целочисленной арифметики, как в радиусе, так и в тестах по часовой стрелке используется больший диапазон чисел из-за возведения в квадрат х и у и их умножения. Не забудьте использовать целые числа с достаточным количеством бит для хранения результатов.