Как протестировать, если точка в выпуклом полигоне в 2D целочисленных координатах?
Одним путем я обычно использую в своих интересах языки динамического программирования, находится в упрощении и разъяснении синтаксиса. Если я представляю базу данных, например, синтаксис, который я использую для взаимодействия с нею, может быть намного более чистым, если я могу динамично загрузить свойства и методы на объекте базы данных для его таблиц, таблиц и строк для их столбцов, и так далее. Различие могло бы быть между:
$row = $db->getTable('user')->getRow(27);
$row->setValue('name', 'Bob');
и
$row = $db->user->getRow(27);
$row->name = 'Bob';
'сбережения визуального шума' второй формы действительно начинают складывать при выполнении сложных вещей.
4 ответа
Если он выпуклый, тривиальный способ проверить это состоит в том, что точка лежит на одной стороне со всеми сегментами (при обходе в том же порядке).
Вы можете проверить это легко сделать с помощью перекрестного произведения (поскольку оно пропорционально косинусу угла, образованного между сегментом и точкой, те, у кого знак положительный, будут лежать справа, а те, у кого знак отрицательный - слева).
Здесь это код в Python:
RIGHT = "RIGHT"
LEFT = "LEFT"
def inside_convex_polygon(point, vertices):
previous_side = None
n_vertices = len(vertices)
for n in xrange(n_vertices):
a, b = vertices[n], vertices[(n+1)%n_vertices]
affine_segment = v_sub(b, a)
affine_point = v_sub(point, a)
current_side = get_side(affine_segment, affine_point)
if current_side is None:
return False #outside or over an edge
elif previous_side is None: #first segment
previous_side = current_side
elif previous_side != current_side:
return False
return True
def get_side(a, b):
x = x_product(a, b)
if x < 0:
return LEFT
elif x > 0:
return RIGHT
else:
return None
def v_sub(a, b):
return (a[0]-b[0], a[1]-b[1])
def x_product(a, b):
return a[0]*b[1]-a[1]*b[0]
Методы Ray Casting или Winding являются наиболее распространенными для этой проблемы. Подробности см. В статье Википедии .
Кроме того, посетите эту страницу , чтобы найти хорошо документированное решение на C.
Или от человека, написавшего книгу, см. - страница геометрии
В частности эта страница , он обсуждает, почему правило обмотки обычно лучше, чем пересечение лучей.
править - Извините, это не Джоспех О'Рурк , написавший отличную книгу Вычислительная геометрия в C , это Пол Бурк, но все же очень хороший источник геометрических алгоритмов.
the way i know is something like that.
you pick a point somewhere outside the polygon it may be far away from the geometry. then you draw a line from this point. i mean you create a line equation with these two points.
then for every line in this polygon, you check if they intersect.
them sum of number of intersected lines give you it is inside or not.
if it is odd : inside
if it is even : outside