Jaki jest prosty sposób obliczenia nakładania się obrazu i wielokąta?

Question

Mam zamknięty nie przecinający się wielokąt. Jego wierzchołki są zapisywane w dwóch wektorach X i Y. Ostatecznie wartości X i Y są powiązane między 0 a 22.

Chciałbym zbudować macierz o rozmiarze 22x22 i ustawić wartość każdego pojemnika równą true, jeśli część wielokąta pokrywa się z tym binem, w przeciwnym razie false.

Moją pierwszą myślą było wygenerowanie siatki punktów zdefiniowanych za pomocą [a, b] = meshgrid(1:22), a następnie użycie inpolygon do określenia, które punkty siatki znajdowały się w wielokącie.

[a b] = meshgrid(1:22); 
inPoly1 = inpolygon(a,b,X,Y); 

Jednak to tylko zwraca true jeśli jeśli środek pojemnika zawarta jest w wieloboku, czyli zwraca czerwony kształt na obrazku poniżej. Jednak to, co jest potrzebne, jest bardziej zbliżone do zielonego kształtu (choć nadal jest to rozwiązanie niepełne).

Aby uzyskać zieloną plamę, wykonałem cztery połączenia z numerem inpolygon. Dla każdego porównania przesunąłem siatkę punktów NE, NW, SE lub SW o 1/2. Jest to równoważne sprawdzeniu, czy rogi kosza znajdują się w wielokącie.

inPoly2 = inpolygon(a-.5,b-.5,X,Y) | inpolygon(a+.5,b-.5,X,Y) | inpolygon(a-.5,b+5,X,Y) | inpolygon(a+.5,b+.5,X,Y); 

Mimo to daje mi częściowe rozwiązanie to nie działa w przypadku, gdy wierzchołek znajduje się zawierać w kosza, ale żaden z kosza rogach są.

Czy istnieje bardziej bezpośredni sposób na zaatakowanie tego problemu, najlepiej za pomocą rozwiązania, które zapewnia bardziej czytelny kod?

Wykres ten został sporządzony z:

imagesc(inPoly1 + inPoly2); hold on; 
line(a, b, 'w.'); 
line(X, Y, 'y); 

Answer 1

Jedną z sugestii jest użycie funkcji polbool (niedostępne w wersji 2008b lub wcześniejszej). Znajduje przecięcie dwóch wielokątów i zwraca otrzymane wierzchołki (lub pusty wektor, jeśli nie istnieją żadne wierzchołki). Aby użyć go tutaj, wykonujemy iterację (przy użyciu arrayfun) na wszystkich polach w sprawdzaniu siatki, aby sprawdzić, czy argument wyjściowy dla polybool jest pusty (np. Nie zachodzi na siebie).

N=22; 
sqX = repmat([1:N]',1,N); 
sqX = sqX(:); 
sqY = repmat(1:N,N,1); 
sqY = sqY(:); 

intersects = arrayfun((@(xs,ys) ... 
     (~isempty(polybool('intersection',X,Y,[xs-1 xs-1 xs xs],[ys-1 ys ys ys-1])))),... 
     sqX,sqY); 

intersects = reshape(intersects,22,22); 

Oto obraz wynikowy:

Kod do kreślenia:

imagesc(.5:1:N-.5,.5:1:N-.5,intersects'); 
hold on; 
plot(X,Y,'w'); 
for x = 1:N 
    plot([0 N],[x x],'-k'); 
    plot([x x],[0 N],'-k'); 
end 
hold off; 

Answer 2

Jak o tym algorytmie pseudokod:

For each pair of points p1=p(i), p2=p(i+1), i = 1..n-1 
    Find the line passing through p1 and p2 
    Find every tile this line intersects // See note 
    Add intersecting tiles to the list of contained tiles 

Find the red area using the centers of each tile, and add these to the list of contained tiles 

Uwaga: Ta linia będzie miała odrobinę wysiłku, aby wdrożyć, ale Myślę, że istnieje dość prosty, dobrze znany algorytm.

Ponadto, jeśli korzystałem z .NET, po prostu zdefiniowałbym prostokąt odpowiadający każdej płytce siatki, a następnie zobacz, które z nich przecinają się z wielokątem. Nie wiem jednak, czy sprawdzenie skrzyżowania jest łatwe w Matlabie.

Answer 3

Najpierw zdefiniować niskiej rozdzielczości okrąg dla tego przykładu

X=11+cos(linspace(0,2*pi,10))*5; 
Y=11+sin(linspace(0,2.01*pi,10))*5; 

jak Twój przykład to wpisuje się w siatce ~ 22 jednostek. Następnie, podążając za twoim tropem, deklarujemy meshgrid i sprawdzamy, czy punkty znajdują się w wielokącie.

stepSize=0.1; 
[a b] = meshgrid(1:stepSize:22); 
inPoly1 = inpolygon(a,b,X,Y); 

Jedyną różnicą jest to, że gdzie oryginalny rozwiązanie podjęła kroki w jednej, to siatka może mieć mniejsze etapy. I wreszcie, aby to wszystko w ramach „krawędzi” kwadratów

inPolyFull=unique(round([a(inPoly1) b(inPoly1)]) ,'rows'); 

round prostu bierze naszą wysokiej rozdzielczości siatki i zaokrągla punkty odpowiednio do ich najbliższej ekwiwalentów niskiej rozdzielczości. Następnie usuwamy wszystkie duplikaty w stylu wektorowym lub w parze, dzwoniąc pod numer unique z kwalifikatorem .I to

Aby wyświetlić wynik,

[aOrig bOrig] = meshgrid(1:22); 
imagesc(1:stepSize:22,1:stepSize:22,inPoly1); hold on; 
plot(X,Y,'y'); 
plot(aOrig,bOrig,'k.'); 
plot(inPolyFull(:,1),inPolyFull(:,2),'w.'); hold off; 

Zmiana stepSize ma oczekiwany efekt poprawy wyniku kosztem szybkości i pamięci.

Jeśli potrzebujesz wynik będzie w tym samym formacie jak inPoly2 w swoim przykładzie, można użyć

inPoly2=zeros(22); 
inPoly2(inPolyFull(:,1),inPolyFull(:,2))=1 

nadzieję, że pomoże. Mogę wymyślić inne sposoby, aby to osiągnąć, ale wydaje mi się to najprostsze.

Answer 4

Sugerowałbym użyciu poly2mask w Image Processing Toolbox, robi mniej więcej to, co chcesz, jak sądzę, a także mniej więcej to, co Ty i Salain zasugerowałeś.

Answer 5

Lekka poprawa

Po pierwsze, aby uprościć „częściowe rozwiązanie” - to, co robisz jest po prostu patrząc na rogach. Jeśli zamiast rozpatrywania siatki punktów 22x22, możesz wziąć pod uwagę siatkę zakrętów o wymiarach 23x23 (która zostanie przesunięta z mniejszej siatki o (-0,5, -0,5). Gdy już to zrobisz, możesz zaznaczyć punkty na siatce 22x22 które mają co najmniej jeden róg w wieloboku

Pełne rozwiązanie..

jednak to, co tak naprawdę szukasz, czy wielobok przecina polu 1x1 otaczającej każdy piksel to nie koniecznie zawierać dowolny z rogów, ale wymaga on, aby wielokąt przecinał jeden z czterech boków tego pola.Jednym ze sposobów można znaleźć piksele gdzie wielobok przecina się z pudełka zawierającego jest z następującym algorytmem:

For each pair of adjacent points in the polygon, calling them pA and pB: 
    Calculate rounded Y-values: Round(pA.y) and Round(pB.y) 
    For each horizontal pixel edge between these two values: 
     * Solve the simple linear equation to find out at what X-coordinate 
      the line between pA and pB crosses this edge 
     * Round the X-coordinate 
     * Use the rounded X-coordinate to mark the pixels above and below 
      where it crosses the edge 
    Do a similar thing for the other axis 

Tak więc, na przykład, że patrzymy na pA = (1, 1) i pB = (2, 3).

• Najpierw obliczono zaokrąglone wartości Y: 1 i 3.
• Następnie patrzymy na krawędziach pikseli między tymi wartościami: y = 1.5 i y = 2.5 (krawędzie pikselowe są pół-offset z pikseli
• Dla każdego z nich, możemy rozwiązać równanie liniowe znaleźć gdzie pA ->pB krzyżuje się z naszym . krawędzie To daje nam: x = 1.25, y = 1.5 i x = 1.75, y = 2.5
• dla każdego z tych skrzyżowań, bierzemy zaokrąglony X-wartość, oraz wykorzystanie go do zaznaczenia pikseli obu stronach krawędzi
  • x = 1.25 jest zaokrąglana do 1.. (dla krawędzi y = 1.5). Dlatego możemy oznaczyć piksele pod (1, 1) i (1, 2) jako część naszego zestawu.
  • x = 1.75 jest zaokrąglone do 2 (dla krawędzi y = 2.5). Dlatego możemy oznaczyć piksele pod numerami (2, 2) i (2, 3).

Więc to poziome krawędzie załatwione. Następnie spójrzmy na tych pionowych:

• Najpierw obliczamy zaokrąglone X-wartości: 1 i 2
• Następnie patrzymy na krawędzi pikseli. Tutaj jest tylko jeden: x = 1.5.
• W przypadku tej krawędzi znajdujemy miejsce, w którym znajduje się linia pA ->pB. To daje nam x = 1.5, y = 2.
• tego przecięcia bierzemy zaokrąglony wartość Y, a za jego pomocą oznaczenia pikseli po obu stronach granicy:
  • y = 2 zaokrągla się do 2. Dlatego też mogą oznaczać pikseli w (1, 2) i (2, 2).

Gotowe!

Cóż, rodzaj. To da ci krawędzie, ale nie wypełni ciała wielokąta. Można jednak połączyć je z poprzednimi (czerwonymi) wynikami, aby uzyskać kompletny zestaw.

Answer 6

Cóż, myślę, że jestem spóźniony, chociaż ściśle mówiąc, czas nagród był do jutra;). Ale oto moja próba. Najpierw funkcja oznaczająca komórki zawierające/dotykające punktu. Biorąc pod uwagę strukturalną siatkę z rozstawem lx, ly i zbiór punktów o współrzędnych (XP, YP), ustaw zawierających komórki:

function cells = mark_cells(lx, ly, Xp, Yp, cells) 

% Find cell numbers to which points belong. 
% Search by subtracting point coordinates from 
% grid coordinates and observing the sign of the result. 
% Points lying on edges/grid points are assumed 
% to belong to all surrounding cells. 

sx=sign(bsxfun(@minus, lx, Xp')); 
sy=sign(bsxfun(@minus, ly, Yp')); 
cx=diff(sx, 1, 2); 
cy=diff(sy, 1, 2); 

% for every point, mark the surrounding cells 
for i=1:size(cy, 1) 
    cells(find(cx(i,:)), find(cy(i,:)))=1; 
end 
end 

Teraz resztę kodu. Dla każdego segmentu wielokąta (musisz przejść przez segmenty jeden po drugim), przecina segment z liniami siatki. Przecięcie jest wykonywane ostrożnie, dla linii poziomych i pionowych osobno, przy użyciu podanych współrzędnych punktu siatki, aby uniknąć niedokładności numerycznych. Dla znajdując punkty przecięcia Wzywam mark_cells oznaczyć otaczające komórki do 1:

% example grid 
nx=21; 
ny=51; 
lx = linspace(0, 1, nx); 
ly = linspace(0, 1, ny); 
dx=1/(nx-1); 
dy=1/(ny-1); 
cells = zeros(nx-1, ny-1); 

% for every line in the polygon... 
% Xp and Yp contain start-end points of a single segment 
Xp = [0.15 0.61]; 
Yp = [0.1 0.78]; 

% line equation 
slope = diff(Yp)/diff(Xp); 
inter = Yp(1) - (slope*Xp(1)); 

if isinf(slope) 
    % SPECIAL CASE: vertical polygon segments 
    % intersect horizontal grid lines 
    ymax = 1+floor(max(Yp)/dy); 
    ymin = 1+ceil(min(Yp)/dy); 
    x=repmat(Xp(1), 1, ymax-ymin+1); 
    y=ly(ymin:ymax); 
    cells = mark_cells(lx, ly, x, y, cells); 
else 
    % SPECIAL CASE: not horizontal polygon segments 
    if slope ~= 0 
     % intersect horizontal grid lines 
     ymax = 1+floor(max(Yp)/dy); 
     ymin = 1+ceil(min(Yp)/dy); 
     xmax = (ly(ymax)-inter)/slope; 
     xmin = (ly(ymin)-inter)/slope; 
     % interpolate in x... 
     x=linspace(xmin, xmax, ymax-ymin+1); 
     % use exact grid point y-coordinates! 
     y=ly(ymin:ymax); 
     cells = mark_cells(lx, ly, x, y, cells); 
    end 

    % intersect vertical grid lines 
    xmax = 1+floor(max(Xp)/dx); 
    xmin = 1+ceil(min(Xp)/dx); 
    % interpolate in y... 
    ymax = inter+slope*lx(xmax); 
    ymin = inter+slope*lx(xmin); 
    % use exact grid point x-coordinates! 
    x=lx(xmin:xmax); 
    y=linspace(ymin, ymax, xmax-xmin+1); 
    cells = mark_cells(lx, ly, x, y, cells); 
end 

Wyjście na przykład siatki/segmentu:

Idąc przez wszystkich segmentów wielokąta daje wielokąt „halo”.Ostatecznie wnętrze wielokąta uzyskuje się za pomocą standardowej funkcji poligonu. Daj mi znać, jeśli potrzebujesz więcej informacji na temat kodu.