Определить, если квадратная ячейка находится внутри многоугольника

Question

Например, я хочу ячейки сетки (квадраты) внутри или частично внутри многоугольника # 14, чтобы быть связано с # 14. Есть ли алгоритм, который будет вычислять, если квадрат находится внутри полигона эффективно?

У меня есть координаты ребер, составляющих многоугольник.

Answer 1

Если я получить это право, это осуществление Fortune's algorithm в JavaScript, который принимает набор 2-й точек (называемых sites) и возвращает структуру, содержащую данные для Voronoi diagram, вычисленной для этого пункта. Он возвращает многоугольники в списке под названием cells. В качестве измерения используется Euclidean distance. Если это правда, мы знаем, что многоугольники всегда выпуклые (см. Формальное определение раздел в Voronoi wiki page).

Теперь, эти варианты решения этой проблемы (трудно просто):

1. Polygon Clipping:

1. форму многоугольника, для квадрата.
2. Find its intersection со всеми ячейками.
3. Calculate area этих перекрестков.
4. Найти наибольшее пересечение.

2- Точка в многоугольнике:

Вы также можете просто найти ячейку, центр квадрата лежит внутри него. Ray casting - это надежный алгоритм PIP. Хотя для выпуклых многоугольников существует более простой подход (см. Раздел «Выпуклые полигоны» here).

3. Расстояние между точками:

Я, если вы знаете, что site связано с каждым cell тогда вам просто нужно рассчитать расстояние между центром квадрата всем sites. Независимо от того, что distance measurement вы используете для вычисления Voronoi, центральная точка квадрата лежит внутри cell, что расстояние от его связанного site минимально, поскольку на самом деле это идея разбиения плоскости на диаграмме Вороного.

---

Исключения:

• Первый подход является вычислительно дорогой, но наиболее точным. Второй и третий варианты прекрасно работают в большинстве случаев, однако, есть исключения, что они не в состоянии правильно решить:

• Второй и третий довольно похожи друг на друга, но обратная сторона ПГИ случаи, когда точка лежит на краях многоугольника, которые стоили вам больше служебных данных для обнаружения.