How to automatically judge points belong to the corresponding sections in a 2D square

I introduce two cutoff points A(x1,y1) and B(x2,y2) to form a linear equation to divide a two-dimensional square (i.e. WB) into two sections (i.e. wb1 and wb2).The figure and code are presented in the following. (WB(i,1) is X coordinates of WB, WB(i,2) is Y coord of WB)

% introduce two cutoff pionts A and B
x1=390407.303; %A x-coord
y1=7130001.528; %A y-coord
x2=392029.915; %B x-coord
y2=7132298.454; %B x-coord
% obtain the coefficients of linear equation
coefficients=polyfit([x1, x2], [y1, y2], 1);
a=coefficients(1);
b=coefficients(2);
% define rows of wb1 and wb2
r_wb=size(WB,1); 
% if L<0,waste blocks belong to wb1
wb1=zeros(r_wb,c);
% if L>0,waste blocks belong to wb2
wb2=zeros(r_wb,c);
[m_WB,n_WB]=size(WB); %read matrix values
%using for loop to judgement
for i=1:m_WB
    if (-a*WB(i,1)-b+WB(i,2))<0
        wb2(i,:)=WB(i,:);
    else
        wb1(i,:)=WB(i,:);
    end
end

Therefore, the above code inspire me to think how to automatically judge the points belong to the corresponding sections , as the square will be divided into N+1 sections if there are N linear equations (N=1,2,3,...), like the following picture shows

For example, there are 4 sections S1, S2, S3, S4 in a square, and 8 points (x1,y1)....(x8,y8), so is there have any solutions to automatically determine that these 8 points are located in the corresponding sections, like using for loop?

Many thanks in advance for your help!

Answer 1

[DGM]

This is something in that direction. There are probably canonical ways of doing this, but I'm not familiar with that. Instead of building a sparse point list, this simply generates a set of masks that describe whether the query points are to the left of each given line. To further locate where the points lie, simply calculate the logical combination of the masks and then use the result to logically index within the array of query points. How complicated that is depends entirely on how orderly we can expect the dividing lines to be (e.g. are they parallel, or can the dividing lines intersect each other within the ROI?)

% query points
M = rand(10,2);

% dividing lines [x1 y1; x2 y2]
% put things into arrays so that you can index them
cp1 = [0 0; 0.5 1];
cp2 = [0.5 0; 1 1];
CP = cat(3,cp1,cp2);

% build masks
nlines = size(CP,3);
leftof = false(size(M,1),nlines);
for c = 1:nlines
    cf = polyfit(CP(:,1,c),CP(:,2,c),1);
    leftof(:,c) = M(:,2) >= (cf(1)*M(:,1)+cf(2));
end
% each column vector describes where the points in M are WRT each line in CP
leftof 

leftof = 10×2 logical array
   0   1
   0   1
   1   1
   1   1
   1   1
   0   1
   0   1
   0   1
   0   0
   0   1

% double-check by plotting
for c = 1:nlines
    subplot(nlines,1,c)
    plot(CP(:,1,c),CP(:,2,c)); hold on
    plot(M(leftof(:,c),1),M(leftof(:,c),2),'bx');
    plot(M(~leftof(:,c),1),M(~leftof(:,c),2),'bo');
end

% for this specific example, we know that cp1 is entirely to the left of cp2
% so if you wanted to group the points by region, you could do this
leftpoints = M(leftof(:,1),:)

leftpoints = 3×2

0.0080 0.6564 0.1502 0.3019 0.0588 0.7605

middlepoints = M((~leftof(:,1) & leftof(:,2)),:)

middlepoints = 6×2

0.6780 0.6359 0.4443 0.6790 0.4481 0.0251 0.7133 0.8264 0.6502 0.6506 0.4994 0.6321

rightpoints = M(~leftof(:,2),:)

rightpoints = 1×2

0.6555 0.2687

For other cases, you'll have to figure out where the lines are WRT each other and figure out the logical combinations required to group the points.

[Chao Zhang]

Thank you very much!

[Chao Zhang]

can i ask a question? how to deal with this situation if the dividing lines are variable like 2,3,...n?

[DGM]

Variable in what sense? A variable number of lines should (I imagine) be able to be processed the same way, so long as you can find the A,B endpoints.

I don't think we ever got into how A and B were determined. Is the calculation of A and B the problem?

[Chao Zhang]

Thanks a lot! I know how to deal with this question if there are a variable number of lines

[DGM]

So long as the lines don't intersect, you can do it by logical operations on the leftof vectors as described. It would be necessary to know the relative positions of the lines, so it might be good to determine their order (e.g. from left to right) and then sort before generating any masks.

So I guess the idea would be to start with the line endpoints

1. make sure they don't intersect
2. sort them in order from left to right
3. group points in a loop, starting with the leftmost group and working right

Making something that works for cases where lines intersect is an extra complication.