извлечь координаты сетки многоугольника

Question

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

% construct grid 
MAX_X=10; 
MAX_Y=10; 
MAX_VAL=10; 
MAP=2*(ones(MAX_X,MAX_Y)); 
axis([1 MAX_X+1 1 MAX_Y+1]) 
grid on; 
hold on; 
%obst 1 
x = [1 1 4 4]; 
y = [1 11 11 1]; 
plot([x x(1)],[y y(1)],'r-'); 

% obst 2 
x = [7 7 11 11]; 
y = [11 1 1 11]; 
plot([x x(1)],[y y(1)],'r-'); 

Answer 1

Связанный пост здесь: What is an simple way to compute the overlap between an image and a polygon?

inpolygon может работать для вашего приложения, но только возвращает истину, если центральная точка конкретной коробки сетки находится внутри многоугольника. Это не сработает, если вы хотите узнать, находится ли какая-либо часть сетки в полигоне. Пример использования inpolygon показан указанным выше пользователем.

Answer 2

сначала сделать замкнутую линию:

x = [x x(1)] 
y = [y y(1)] 

и матрицу значений X и Y в различных точках:

Y = repmat((1:MAX_Y)',[1,MAX_X]) 
X = repmat(1:MAX_X,[MAX_Y,1]) 

Затем вы можете использовать inpolygon:

MAP = inpolygon(X,Y,x,y) 

Это также должно работать на невыпуклых многоугольниках.

Answer 3

Работа с невыпуклыми многоугольниками будет сложной задачей, поэтому, возможно, вам следует начать, разделив ваш многоугольник на несколько выпуклых многоугольников. Вы можете использовать внутренний угол, чтобы решить, где угол не выпуклый, и применять разрезы, которые связаны с этими углами, как минимум. Но, возможно, Matlab поддерживает некоторый алгоритм triangulation, который вы можете использовать.

Как только у вас есть выпуклые многоугольники, вы можете думать о них как о пересечениях полупространств. Если и B являются два угла, которые пронизывают линию, и P является точка сетки, вы можете использовать знак определителя

| Ax Bx Px | 
| Ay By Py | 
| 1 1 1 | 

решить, с какой стороны от линии точки вранье. Какой знак зависит от порядка, в котором вы обходите свой полигон, но если вы обрабатываете углы по порядку, то точка P лежит внутри выпуклого многоугольника, если знак никогда не изменяется. Горизонтальные или вертикальные линии не будут особыми случаями в этой формулировке, и у вас не будет подразделений, которые хороши для производительности и могут также помочь с точностью.

Если вы не хотите перебирать все точки сетки с помощью этого метода, вы можете придумать различные оптимизации. Можно было бы прекомпретировать перекрестный продукт A × B из двух углов, охватывающих каждую строку. Точечный продукт между этим кросс-продуктом и точкой P равен указанному выше определителю (т. Е. Det (A, B, P) = (A × B) · P), поэтому вместо полного детерминанта вам остается только вычислить три продукта и две суммы для каждой комбинации точечных линий.

Если вы хотите оптимизировать это еще больше, вы, вероятно, лучше всего посмотрите на что-то вроде Bresenham's line algorithm, чтобы вычислить точки на границе многоугольника, а затем просто перечислить все точки горизонтальной (или вертикальной) линии между соответствующие граничные точки.

Если вы не выполняете все ваши вычисления с целыми числами или другими точными числами, вопросы округления могут быть серьезной проблемой во всем этом. Вы должны решить, следует ли подсчитывать граничные точки, а также точно рассчитывать точки внутри исходного многоугольника, но на границе его выпуклых участков ровно один раз. Сколько усилий это требует, в значительной степени зависит от того, как выглядит ваш ввод.