0

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.

https://i.stack.imgur.com/RRWQX.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)

Community
  • 1
  • 1
Edza
  • 1,364
  • 3
  • 14
  • 24

1 Answers1

1

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.

shapiro yaacov
  • 2,308
  • 2
  • 26
  • 39
  • I think I got the code for finding all polygons (the link in the update). Also I think this is the solution. I will leave the question open for a bit. Thanks :) They only overlap in the sense that smaller polygons are part of larger ones. – Edza Apr 29 '15 at 13:30
  • Hmmm.. I'm wondering will this work if two polygons are side by side and share a vertex. I dont think so. – Edza Apr 29 '15 at 13:35
  • Two polygons with a common edge (yellow and green in your picture) do not have any corners that are located IN the other... – shapiro yaacov Apr 29 '15 at 13:42