Edza Edza - 1 month ago 7
C# Question

I got points on a map.Getting all independent inner polygons that are formed?

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:

  1. You have the polygons themselves.
  2. 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.

Comments