Search code examples
javamathhashmapcoordinate-systems

How to divide a polygon into sub polygons and assign id to them

I have a polygon with the co-ordinates

(1,2)
(3,2)
(1,1)
(3,1)

I want to divide the polygon into 9 parts and assign each part a number.For exampleenter image description here

So I tried like 

double width =  3-1=2;
double height = 2-1=1;

subpolygon width=2/3=0.667
subpolygon height=1/3=0.33

Now I want to have the subpolygon id and their co-ordinates like

1  ->  (1,2),(1.67,2),(1,1.67),(1.67,1.67)

and so on.So I need a hash map like below to store the information.

HashMap<Integer, Double[]> hmap = new HashMap<Integer, Double[]>();

Any help is appreciated.

Solution

  • I'll give you a hint to get started. What you really want is a clever or efficient way to loop through all the vertices of your polygon. Let's start by simply looking at the positioning of the top left corner of each subpolygon.

    Starting at the top left corner of your polygon, we will first loop left to right, and then top to bottom. Let sw denote your subwidth and sh denote your subheight.

    So what's the formula for top left corner of each subpolygon? Well, we start at (min x, max y). This is the top left corner of subpolygon 1. Then we add sw to the x-value to get the top left corner of subpolygon 2 (min x + sw, max y). Then the top left corner of subpolygon 3 is (min x + 2 * sw, max y).

    Then we need to drop down a height of sh to get the top left corner of subpolygon 4. This is (min x, max y - sh). Then we go left to right again: (min x + sw, max y - sh) for subpolygon 5, (min x + 2 * sw, max y - sh).

    See a pattern yet? Drop down another height of sh, and go left to right again: (min x, max y - 2 * sh), (min x + sw, max y - 2 * sh), (min x + 2 * sw, max y - 2 * sh).

    So if I let my index i range from 0 to 8 (which will correspond to your subpolygons 1 through 9), you can see that the general pattern for the top left corner subpolygon (i+1) is:

    (min x + (i % 3) * sw, max y - (i / 3) * sh).

    Note that the preceding (i / 3) is integer (round down) division, e.g. for subpolygon 8, i = 7, and 7 / 3 = 2.

    I believe this is enough to get you started. I personally would have preferred to start at the bottom left corner and work left to right, bottom to top, but I went based on your numbering. You can find similar formulas for the other corners, and a bit of thinking can help you generalize this formulas into different partitions (i.e. look at the divide by 3 and modulo 3 parts).