# How to evalutate AREA from connected points?

1 view (last 30 days)
Veronica Taurino on 30 Aug 2017
Commented: darova on 26 Nov 2019
I have a group of points and their connectivity matrix (how the points are connected, actually I'm working on a water network). I need to evaluate all the areas between all the lines (you can see the example picture). I've found different functions but I don't know if there is something more specific. I thought first to create polygons and then to evaluate the area but I don't know how to create polygons using the connectivity matrix.
The image above represents my points as a graph

KALYAN ACHARJYA on 30 Aug 2017
Veronica Taurino on 30 Aug 2017
Hi, thank you.
I've seen it before but I don't know how to use it in my case. I have 2 matrices: 1) the first one identified the points of my net (x, y coordinates for each point); 2) the second one has connecvity matrix, it means 3 columns: the first 2 columns defined the 2 linked nodes, the third column define the distance between them.
To use 'patch' I should reorder my points and I can't do it manually, they are 20'000 nodes. Moreover now I can just SEE the network (points connected with lines, using the connectivity matrix) but I have no information on the 'closed shape' defined, that means you see them but you can't interact with them (they are just lines, not polygons).
My net is very big (20'000 nodes) so I need to find a way to do everything with code.

Veronica Taurino on 26 Nov 2019
I solved my problem with a second software: I used ArcGIS!
Thank you for all your suggestions, it helped me to change my PoV on the matter.

#### 1 Comment

darova on 26 Nov 2019
Finally! Took two years!

Guillaume on 30 Aug 2017
There are a fair number of graph analysis functions that were introduced in R2015b, I'm not sure any of them are that useful for your purpose though.
The main difficulty will be to identify the smallest polygons created by your graph. I'm not sure how you'd do that. It's probably been done before so I would search the literature. Once you have identified the polygons, calculating their area is done with polyarea.

Veronica Taurino on 31 Aug 2017
I was thinking the same thing, thank you. I'm gonna try something different
Veronica Taurino on 31 Aug 2017
Have you got any suggestions about free alternative? Thank you
José-Luis on 1 Sep 2017
If you want a GUI, then probably GRASS or SAGA.

John D'Errico on 31 Aug 2017
Edited: John D'Errico on 31 Aug 2017
It is often true that what looks easy to the eye/brain is not so trivial do do by computer. And even if it may be easy, but if nobody else ever identifies a need to do that, then somebody will need to write the code for it. I've never seen anyone else asking for this, so what do you expect?
I'd suggest a simple algorithm.
1. Identify any nodes that have only one edge that touches them. This will prune away all edges that cannot belong to any polygon. Repeat this step if new nodes appear that connect to only one other node.
2. Find any closed polygon. Does that polygon have any nodes that branch off internally into the polygon? If so, then unless that branch terminates, then you can split the polygon into smaller polygons. Repeat the dissection on each piece recursively, until all polygons are minimal. Now find another polygon, one that does not include those you have already found. (This last part may be the least easy.)
Another simple scheme:
0. Maintain a list of all polygons that have been found so far. The list will be empty to start.
1. Identify any nodes that have only one edge that touches them. This will prune away all edges that cannot belong to any polygon. Repeat this step if new nodes appear that connect to only one other node.
2. Pick any point at random in the domain. Does it belong to a polygon that is in our list? If not, then any ray that extends from the point will intersect some edge of the enclosing polygon. Follow that polygon, going in a consistent direction (clockwise, for example.) When the polygon closes on itself, add it to the list of identified minimal polygons.
Repeat step 2 until the sum of all identified polygonal areas is the total area. You are now done.
I'm sure I can think of other heuristics that will be workable.

#### 1 Comment

Veronica Taurino on 31 Aug 2017
...my problem actually is HOW identify polygons with matlab: I have 15'000 nodes and 19'000 links, how can I detect them with matlab? I can't do it manually of course.
As I said, I'm using this now: https://it.mathworks.com/matlabcentral/fileexchange/10722-count-loops-in-a-graph
the problem is the huge amount of loops, it's been 24 hours of elaborations now, maybe it's the wrong way to do it