Edza - 8 months ago 38

C# Question

I got points on a map and lines connecting those points.

How do I get all independent inner polygons that are formed?

The linked picture describes the problem.

http://i.imgur.com/0LdA3ji.jpg

I'm supposing I need a tree search algorithm that enumerates all the points and connecting lines in a tree structure and then searches for cycles but this job is kinda over my head.

In a perfect world the example would be in C#.)

I found:

Finding all cycles in undirected graphs

but it does not mark independent polygons. It finds all possible polygons even overlapping ones.

I'm using google maps. The use case is: I detect clicks on map and draw points. I detect click on points and then get lines between points. Now I need to automaticaly generate polygons from the lines and points. Sure I can draw polygons. I just dont know which ones (what coordinates - or rather: what points to choose for a polygon)

Answer

I actually have no experience in graphics and how to actually colour a polygon once you've found it, but assuming:

- You have the polygons themselves.
- They do not patialy overlap or any other weird behaviour.

Then the colouring pseudo code could go something like this:

```
while listOfPolygons is not empty
temp <- find smallest polygon in listOfPolygons
colour temp
remove from listOfPolygons all polygons containing temp
remove temp from listOfPolygons
```

Notice that the part about finding the containing polygons might be tricky.

Edit:

Checking if polygon A is in polygon B can be done by checking if any corner (vertex?) of A is located inside B.

Source (Stackoverflow)