Какой алгоритм я могу использовать для определения точек в полукруге? - PullRequest
Новая
       3

Какой алгоритм я могу использовать для определения точек в полукруге?

0 голосов
/ 09 июня 2010

Как я могу сделать это на сетке с несколькими "центрами", и, следовательно, имея совпадающие точки, которые я хочу считать только один раз?

Какой самый эффективный способ сделать это?

1 Ответ

4 голосов
/ 09 июня 2010

Чтобы выяснить, находится ли точка, P, внутри полукруга, я бы рассмотрел тест из двух частей:

  1. Находится ли P в радиусе R от центра C?
  2. Находится ли P в правильной (т.е. занятой) полуплоскости?

Часть (1) проста: сравните (P_x-C_x)^2 + (P_y-C_y)^2 (в 2d, конечно, добавьте направление Z в 3d) с R^2 (не беспокойтесь о квадратных корнях, они требуют времени и добавить что-нибудь).

Часть (2) почти такая же простая: определите вектор b = B - C, который делит пополам полукруг, указывающий на занятую полуплоскость. Затем вычислите вектор v = P - C и возьмите скалярное произведение с b. Если результат положительный, точка находится на занятой полуплоскости, если отрицательная, точка находится на незанятой половине места, а если 0, точка попадает на разделительную линию. Точечный продукт в 2d, как обычно, v*b = v_x*b_x + v_y*b_y.

...