Finding parcels in a road network

Hi, does anybody have an idea how I can determine the areas between the strees (marked red in the image)?

What I have is the intersection coordinates of the streets and access to the road models and their vertices.

What I want is a polygon that contains the shape of each area in between the streets.



Any help or idea is highly appreciated!

you could use a flood fill method if you can create from your road data an array or a bitmap with a proper resolution (road width or half of road width).

@PadMalcom, I don't know what you exactly meant, but maybe region, like region_create is your choice.

@Sivan: Thanks for the hint. What I'll try to do is to trace from every vertec to another to create regions.

@rojart: The challenge for me is to determine the edges of the regions not a technical way to define them. But thanks anyway!

This might be helpful, shows a flood fill way of doing it;
http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt (Powerpoint presentation)

Thanks helghast, infact I use Voronoi diagrams as an option to draw my road network. Unfortunately, I want tpe parcels to stick exactly to the polygons that define the borders of the roads and intersections.

In the case you have the links of each vertex sorted clockwise or inverse, you can take a vertex, go to its neighbor and go to the next vertex by the next link until you reach the first vertex, closing the shape.



If you create each link as a couple of links, one per direction starting from each vertex involved in the link, you can disable the links involved on the shape creation until you have no linked vertexes at all.



It will definetively create a shape per zone, but it is a bit complicated...

Hope it helps

I see this solution did not convince you

Any question?

Hey txesmi, thanks for your answer but there are several problems with your approach.


How do I find the neighbour? My roads consist of ~100 vertices.


What if a shape is not closed? If you watch a voronoi diagramm it has ends that don't form a polygon.

Furthermore, there can be more than 2 networks that are not connected. Again a special case that is not covered by your idea.

But thanks anyway! I'm very glad you are thinking with me!

maybe this helps : http://alienryderflex.com/polygon/

I mean that the neighbors to be computed are the crossroads. The roads are created from crossroad to crossroad as links, aren't they? So the points on the shape are crossroads. The segments between points need to follow the road path that connects them, straight or curved, it is not important.


The shape surrounds deadends and always closes itself. Look at this picture:

The only problem is to identify witch shape is the outside, but not really a problem: it is the largest one.


In the moment you have the outside shapes of more than one net, they need to be considered as inside shapes of a global outern shape.



Happy to help... if that helps

I went from theory to practice.

download




Left click to create new cross points. Drag a cross point to another cross point to connect them. Don't try to cross lines without a cross point because it will probably crash... it is just a simple example for proving that the method works

Very nice example txesmi. Thanks for sharing!

Pleased to be useful

I commented the code a bit in order to be more understandable.

Salud!

Nice example, but now try to generate a mesh or a polygon out of all the black areas. Oh and please consider such a network, too



EDIT: This example should result in 2 polygons / meshes.

It is clear that the method is only valid to identify the figures that make up the interstices: a necessary first step to end up doing what you want.