Find the intersection of a square pixel with a closed 2D curve
6 views (last 30 days)
Show older comments
Maura E. Monville
on 17 Jun 2019
Answered: Maura E. Monville
on 4 Jul 2019
Dear MatLab Experts,
I would appreciate your help with the following problem.
I have a set of closed concave 2D curves of arbitrary shape. The coordinates of the polygonal curve are known.
I cover the areas inclosed by the curves with square pixels whose side is a parameter. Therefore the pixels may be smaller or larger.
The rim of the area (curve) must be covered by the square pixels as well. Please, see the attached pictures.
Question:
How can I find the pixels that intesect the curve as distinguished from the pixels totally contained inside the curve?
Thank you in advance for any suggestion and help.
Kind regards,
Maura E. M.
3 Comments
Fabio Freschi
on 18 Jun 2019
Have you got a particular data structure for the pixel?
My approache would be:
- check for each point of the grid if it is inside the curve (see function inpolygon)
- if a pixel has all four corners inside the curve, the pixel is inside (the implementation of this check depends on the data structure)
If you can share the data, I can try to be more specific
Accepted Answer
Maura E. Monville
on 22 Jun 2019
4 Comments
darova
on 23 Jun 2019
I have an idea based on triangulation:
Create grid - number each pixel (pixels have number of nodes)
Loop over all pixels. If inpolygon() returns 0 or 1 nodes inside - delete pixel (pixel is outside), 4 nodes - pixel is inside, 2-3 - create new 4 pixels and delete an old one (double resolution).
Repeat procedure if needed
More Answers (7)
darova
on 24 Jun 2019
1 Comment
Matt J
on 24 Jun 2019
Agreed. The general approach should be
- Use inpolygon to find rectangles whose vertices are entirely inside the polygon. These can be removed from further investigation
- Loop over the remaining rectangles (a greatly reduced number, presumably) and use polyshape.intersect() to determine whether there is an intersection or not.
DAdler
on 23 Jun 2019
Edited: DAdler
on 23 Jun 2019
Hope this will get you started in ~20 lines. It is along the lines of what you described. It can be slow if you use too many pixels, but it's a start. The code uses InterX.
Have you looked at the command polyarea for the area inside the curve?
Remarks:
- I tried this code with your data and it looks fine (to me).
- No pixel refinement is done here. Change N instead!
- You require more than 1 intersection for the boundary curve. This may be problematic if the curve is tangential to the pixel boundaries, thus leaving the boundary open. If you still want this, instead of ~isempty in definining the boundary, use size("same commands InterX etc",2)>1.
clc,clf, clear all, close all
% CURVE, CIRCLE OF RADIUS 3
t = linspace(0,2*pi);
Curve = [3*cos(t);3*sin(t)];
N = 21; % (N-1)X(N-1) PIXELS TO COVER THE DOMAIN
% DEFINE THE BOUNDING BOX AND PIXEL GRID COORDINATES
Xmax = 4; Xmin = -4;
[X,Y] = meshgrid(linspace(Xmin,Xmax,N));
VV = [X(:),Y(:)];
% PIXEL CONNECTIVITY LIST
[x,y] = meshgrid(1:N);
V = [x(:),y(:)];
j = setdiff(1:N^2-N,N:N:N^2-N)';
C = mat2cell([0,1,N+1,N,0]+j,ones(1,(N-1)^2),5);
% BOUNDARY PIXELS
boundary = find(cell2mat(cellfun(@(c)~isempty(InterX([VV(c,1),VV(c,2)]',Curve)),C,'UniformOutput',0)));
% INTERIOR PIXELS
interior = find(cell2mat(cellfun(@(c) all(inpolygon(VV(c,1),VV(c,2),Curve(1,:),Curve(2,:))),C,'UniformOutput',0)));
interior = setdiff(interior,boundary);
figure, hold on
% DRAW PIXELS
for i=boundary'
fill(VV(C{i},1),VV(C{i},2),'k','edgecolor','c')
end
for i=interior'
fill(VV(C{i},1),VV(C{i},2),'m','edgecolor','c')
end
% DRAW CURVE
plot(Curve(1,:),Curve(2,:),'r')
axis equal
4 Comments
DAdler
on 29 Jun 2019
Most likely you are calling InterX incorrectly, i.e you calling it with Xc and Yc being column vectors. They should be row vectors to form a 2xN array,
No, the curves do not need to be of the same length!
It does not matter if the 2 points coincide to close the curve, I guess. The code tests if segments intersect.
DAdler
on 3 Jul 2019
Maybe this would have resolved your issue if you provide XC and YC as column vectors?
P = InterX([sqx;sqy],[XC,YC]')
0 Comments
See Also
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!