Subdividing a 2-D Polygonal Shape Using Values Given in an Array

Hi,

I have a 2D polygonal shape, let’s assume it’s 1000 m2, and an array containing some values. What I want to do is to create subdivisions within the polyshape corresponding to the values ​​in the array. It doesn't necessarily have to be as regular as shown in the example image below. I’ve tried many things but couldn’t succeed. Any suggestions would be greatly appreciated.

Thanks in advance,

Mel

Answer 1

[John D'Errico]

Sadly, this is an impossible task to do perfectly. Even imperfectly is difficult. And wanting quadrilaterals makes it harder yet. (Yes, that is doable too, but more work.) And if you want to specify the number of objects in the dissection, again, that will be a significant problem.

A simple solution is perhaps better, that would be based on a triangulation.

1. Subdivide the polyshape into triangles. You already have a polyshpe utility to triangulate a region, so this is trivial.
2. Compare the areas of each triangle. Find the largest triangle in area. If it is too large, the split it in half, probably by splitting the longest edge of that triangle in half. That will SOMETIMES force you to also divide another triangle into two triangles, because the edge you chose was a shared edge. Such is life.

Essentially, the above is a pretty simple solution. It results in a triangulation, and you can simply enough make the triangles not too different in area.

Could you form a dissection that always resulted in a set of convex quadrilaterals? Yes. Not difficult, but not so easy if you want to fix the number of quads in the result, or to give a target for their area. That is, I just told you above how to dissect a polyshape into triangles. Now take each triangle and dissect it into quadrilateral regions. That is easy enough to do, splitting any triangle into exactly THREE quadrilateral subdomains. (Think about it. Is there an easy way to solve that problem?)

help polyshape/triangulation

  TRIANGULATION Construct a 2D triangulation object from polyshape
 
  tri = TRIANGULATION(pshape) triangulates a polyshape and returns a 2-D
  triangulation object.
 
  Example:
   rect = polyshape([0 0 1 1], [0 3 3 0]);
   tri = triangulation(rect);
 
  See also triplot, regions, holes, polyshape, triangulation

    Documentation for polyshape/triangulation
       doc polyshape/triangulation

For example...

xy = [0 0;1 0;1.2 2.5;1 4;0 4];
ps = polyshape(xy);
plot(ps)
axis equal

So qualitatively a similar shape, I was feeling too lazy to replicate the exact one shown by @Melanie VT.

Now we can triangiulate it.

pstri = triangulation(ps)

pstri = 
  triangulation with properties:

              Points: [5×2 double]
    ConnectivityList: [3×3 double]

trimesh(pstri.ConnectivityList,pstri.Points(:,1),pstri.Points(:,2))
axis equal
hold on
plot(ps)
hold off

Again, if one of those triangles is too large, we can subdivide it as needed. Or, I could subdivide each triangle into 3 quads. For example, given this triangulation, I'll pick one triangle, then split it into three quad regions.

T1 = pstri.ConnectivityList(1,:)

T1 = 1×3

2 1 4

xy1 = pstri.Points(T1,:)

xy1 = 3×2

0 4.0000 0 0 1.2000 2.5000

xy1 = [xy1;[.5 .5 0;.5 0 .5;0 .5 .5;1/3 1/3 1/3]*xy1]

xy1 = 7×2

0 4.0000 0 0 1.2000 2.5000 0 2.0000 0.6000 3.2500 0.6000 1.2500 0.4000 2.1667

Q1 = [1 4 7 5;2 4 7 6;3 5 7 6];

% replot, with the subdivided triangle added on top
trimesh(pstri.ConnectivityList,pstri.Points(:,1),pstri.Points(:,2))
axis equal
hold on
plot(ps)

plot(xy1(:,1),xy1(:,2),'ko')
line(reshape(xy1(Q1',1),4,3),reshape(xy1(Q1',2),4,3))

I dissected one of those triangles into 3 quads. This would be doable for all of the triangles in one vectorized operation too.

Honestly, I don't know the final goal of this question. Why do you need to quadrangulate a polyshape? (Is quadrangulation even a word? Dissect into quadrilateral subdomains is probably a correct description of the request.) But even then, I don't know the final goal, or what would be an acceptable solution. My recommendation is, since triangulations are so easy to work with, and since the tools in MATLAB to handle triangulations are all there, to learn to work with them instead.

[Melanie VT]

Dear @John D'Errico,

Thank you very much for your detailed explanation. The aim of this implementation is sort of a simple land parcelling as shown in the examples below:

https://www.researchgate.net/profile/David-Grandgirard/publication/274077288/figure/fig1/AS:651951670833170@1532448799913/Example-of-Land-Parcel-Identification-System.png

https://auctioneersoftware.s3.amazonaws.com/baer/2022/7/large/F2YmtKOIiB6s6-HqQgXXQsYZ.png

Although 4(or higher)-sided shapes are important to be realistic, the main point here is to be able to segment using the values ​​in the array. So the fields can also be triangles, but they need to get their values ​​from the list. That’s the main concern.

I’m very grateful for your contribution