How to do clustering in mathcad ?

[Mathcad111]

 For example i have deployed some random nodes in (200x200), but the problem is i want to form some random cluster's, like the given graph, please look my mathcad file !

[-MFra-]

Your question is not so clear to me. I do not think the answer you're looking for is as simple as mine ...............

[Mathcad111]

no i not looking for this solution i have attached modified mathcad file please go through it (inform me if have some question regarding it) !

[Mathcad111]

I have modified my mathcad but i don't know how to expand for full block !! please check mathcad file !

[-MFra-]

you want something like that expandable as you like. right? in GSM networks, for example, the hexagons are all the same size and adjacent. To the chart, must be added the random positions of the sources,  while the antennas are in the vertices. It's been a long time since I've dealt with the subject.

I'm working on it

[Mathcad111]

Thank for reply, Yes the same!  

[-MFra-]

Basically you should work in the complex plan. See the following example. I leave you to continue. I do not go further.

[Werner_E]

Any additional constraints like same area/size of all clusters or same number of nodes in each cluster?

Do you only need a graphical representation of a hex grid like FM showed or do you need to sort your nodes according to which cluster they are in?

[Mathcad111]

1. There are no constrains so size of the cluster are random 

2. Yes i want to find out what's inside the each cluster (say number of node's which is present inside the cluster) !

[Werner_E]

---

2. Yes i want to find out what's inside the each cluster (say number of node's which is present inside the cluster) !

---

Clustering a plane with hexagons is quite easy but sorting the nodes and assigning each node to a specific cluster od counting the nodes in each cluster can be quite demanding, given that you want a hexagonal area and not a simple rectangle or even square which would make the task much simpler.

There sure are some clever algorithms to determine if a point is inside a given polygon and it may be even simpler in your case as you have regular hexagons.

Furthermore you would have to define what the count should if a point is exactly on a border between two hexagons or is one of the corners belonging to three hexagons.

If you are happy with an approximation you could simply count the nodes within the circumcircle of a hexagon.

[Werner_E]

For whatever its worth here is a crude way to create a hex grid.

For counting the nodes within a hexagon you might search the forum for a routine a I posted quite a while ago which decides for any polygon if a given point is inside or not. Using a quick search here in the forum did not bring up the thread I have in mind but a routine by Stuart which may serve as well.

[Mathcad111]

Thank you ! i got some idea how to find the "node" under the hexogen (i'm not sure whether it will work!) let me check!

[Werner_E]

I found a sheet in my archive which compares a couple of different "Point-in-Polygon" algorithms. Its not the routine (based on the Jordan algorithm) I was talking about in my former post but they may serve as well.

I attach the sheet - maybe it can be of use for you.

[Werner_E · Accepted solution]

OK, now I found the Jordan routine I was talking about.

I added it in the attached worksheet along with some routines to scale, rotate and translate the grid

and also included an example how you may use the program to count the number of points in one hexagon:

[Mathcad111]

Apologies for my late reply, it's looks good can we able to extend for multiple hexogen ? and finding the no. of nodes under the cluster (that you have did already for single hexogen)!

[Werner_E]

---

@Mathcad111 wrote:

Apologies for my late reply, it's looks good can we able to extend for multiple hexogen ? and finding the no. of nodes under the cluster (that you have did already for single hexogen)!

---

The routine will give you the number of nodes in any polygon you feed in.

So you will have to decide for a data structure you'd like to manage the various hexagons with.

Clustering a picture with a hexagon structure is one thing, managing that grid as a bunch of individually addressable areas is another. The grid structure I created consists of a list of vertex coordinates separate by a line of NaN's. So you should have not much troubles to split it into a list of single hexagons which you then could feed in the point counting routine. Maybe a vector consisting of elements representing a hexagon each could be a suitable structure. Depends on your needs and what exactly you have in mind.

You still have not decided what to do if a point lies exactly on the border of the polygon.

My routine will not distinguish between point an a segment of the border (belonging to 2 hexagons) and point being a vertex (belonging to 3 hexagons). If thats an issue the Punkt_in_Polygon and some other routines will have to be modified.

[Mathcad111]

Now it's working for all hexagon (it's small modification are required from what you did already) Big Thanks for all the people! 

[Werner_E]

---

@Mathcad111 wrote:

Now it's working for all hexagon (it's small modification are required from what you did already) Big Thanks for all the people! 

---

Glad to hear you got what you were looking for.

Haven't noticed this reply when I wrote my reply above.

[Mathcad111]

I have some problem with multiple hexagon please see the mathcad file (error) 

[Werner_E]

---

@Mathcad111 wrote:

I have some problem with multiple hexagon please see the mathcad file (error) 

---

The reason you get wrong results is that the "grid" I created is not a polygon!

A polygon is a n x 2 matrix consisting of the coordinates of the vertices of the polygon in the order they should be connected. "grid" is constructed differently as you might have noticed. It consists of single, not connected (separated by NaNs) hexagons in the order which was most convenient for me. basically a collection of rows of separated hexagons. Interpreting "grid" as a polygon where all points are connected in the order given is a different structure with a number of additional border line segments. If you remove the NaN#s in "grid" you see what that "polygon" looks like. What "inside" and whats "outside" of this polygon is sure different from what you had in mind (see picture).

I don't understand why you would want to count the number of points in ALL hexagons, within the whole grid. Given the grid covers the whole area the result should be the total number of points anyway.

If you really want to do so you would have to manually (or using a program) create a polygon representing the border polygon - the outside border of the grid and use this in the counting routine.

But its still not clear to me what exactly you a trying to achieve. I got the impression that you wanted to know how many points are in every single hex cell and now you are trying to count all of them together!?

[Mathcad111]

1. yes your right! i want to know how many points inside each of the hex cell, fact is that it's working for one Hex cell that you did already.

2. what i understand from you (correct me if i'm wrong), "grid" has NaN so that i'm not getting correct result, but i tried by using removing NaN but "grid" points and "pts" are not matching. i don't know what to do for that!

[Werner_E]

The routine I provided will give you the number of points in ONE polygon. If you want to know the number of points in the next hexagon, you would have to call the very same function again with that hexagon as second argument.

The routine PunktInPolygon removes any NaN's anyway - thats not the problem. The problem is that you are looking for a mindreading routine which will give you what you have in mind. If you like you can write a routine yourself which takes the list of points and the grid as arguments and cycles through the grid, stopping at a NaN and call PunktInPolygon with the points in Grid from the last NaN to the next and store those values in a vector. You would have to find a way to find out which number belongs to which hexagon, though.

As already written you will have to make some decisions - the data structure used to store your hexagons, treatment of points on the border, at a vertex, display of the resulting values (how would you know which number belongs to which hexagon), etc.

Mathcad is not a one-button solution to any given problem but its a tool you can solve many problems with. But its necessary to learn how to use this tool and of course its vital that you analyze your problem yourself to sort out which structure to use and decide how to use the tool the best way.

So far you just provided a bunch of random points and asked for a grid. As it came out you don't bother what kind of grid - irregular is OK, hexagon is OK, the way the hexagons are turned does not matter, size seems not to matter, ...

If nothing matters, then use as grid the full 200x200 rectangle. All points are inside - problem solved, done!

Sorry, but to me that doesn't look like you have made much efforts in analyzing the problem.

[-MFra-]

but, on the hypothesis that the hexagons are regular, why do they deform after rotation?

[LucMeekes]

Because, apart from rotating, a different scaling in x- and y- directions is applied...

Luc

[Werner_E]

---

@-MFra- wrote:

but, on the hypothesis that the hexagons are regular, why do they deform after rotation?

---

I have not shown how to rotate the grid, I just mentioned that it could be done.

What I showed was just different scaling in x- and y-direction - you would expect "deformation" when doing so 😉

Apart from using different scaling factors the difference in the last two plots is that the left one scales wrt the origin and the right one wrt (-7/-7), which therefore remains the center of the lower left hexagon. Just playing around as I not really sure what exactly is needed.