# Polygon Puzzle

9 replies to this topic

### #1 Josh Posted 02 November 2007 - 03:00 PM

Josh

Contributor

• Validated Member
• 25 posts
• Gender:Male
• Location:San Francisco
• Interests:wild mushrooms, kites &amp; kite boarding, climbing, bouldering, graphic design, dive bars, dive restaurants, diving, museums, movies from the 70z, downloading music that i'll never listen to, politics, bitching about politics, comics (yes...i still read comics but i don't have a star trek outfit), project management, cute girls walking down the street, a perfect latte, good wine (bad wine too), and all that keeps me entertained during the day.
• United States

Hey Everyone,

This might be an easy problem to solve, but I couldn't really describe it without a bunch of examples, so i created a word.doc that has a step by step description of what I'm trying to do and where I'm coming to a dead end.
The quick description is that I have a bunch of city streets with common attribute that makes a coverage area. I need to create a polygon for each street grouping. If there is a way I can do it with either MapInfo or ESRI I'd be stoked!

Cheers,

Josh

### #2 Hans van der Maarel Posted 02 November 2007 - 03:34 PM

Hans van der Maarel

CartoTalk Editor-in-Chief

• 4,178 posts
• Gender:Male
• Location:The Netherlands
• Interests:Cartography, GIS, history, popular science, music.
• Netherlands

From the word doc:

I’m guessing Hans will have a tool that can do it easily

Initially I was thinking of the ConvexHullAccumulator tool in FME, which does more or less the same as what you've already done with MapInfo. Since that's not what you're looking for, I'm thinking maybe creating Voronoi polygons using the VoronoiDiagrammer, although that wants points as input, not lines.

Definately an interesting problem. I assume the area and shape of the polygons is of lesser importance, as long as they cover the appropriate lines, right? Could you perhaps send me some sample data?
Hans van der Maarel - Cartotalk Editor
Red Geographics

### #3 Josh Posted 02 November 2007 - 04:25 PM

Josh

Contributor

• Validated Member
• 25 posts
• Gender:Male
• Location:San Francisco
• Interests:wild mushrooms, kites &amp; kite boarding, climbing, bouldering, graphic design, dive bars, dive restaurants, diving, museums, movies from the 70z, downloading music that i'll never listen to, politics, bitching about politics, comics (yes...i still read comics but i don't have a star trek outfit), project management, cute girls walking down the street, a perfect latte, good wine (bad wine too), and all that keeps me entertained during the day.
• United States

Hans you rock! I'll send it to your email right now.
Thanks
Josh

### #4 bruce Posted 02 November 2007 - 09:09 PM

bruce

Contributor

• Validated Member
• 17 posts
• Gender:Male
• Location:Camden, Maine
• United States

Josh,

I am interested in any solutions that may come out of this problem. I work with service areas and response/travel time for fire apparatus, a problem maybe similar to your fire box areas. Are you dealing with response time at all or simply defining an outline to show coverage around the fire boxes? I have used Network Analyst to do this in a couple of projects. It is easy and does a good job, but to get accurate results care must be taken refining the attributes of the road segments. Fire apparatus operators will often avoid certain roads if they can do so. For accurate response times in Network Analyst I would have to make allowances for changes in speed of travel, say up and down hills. Anyway, I am looking forward to seeing a solution. Good luck!

bruce
Bruce Hensler

### #5 gregsd Posted 03 November 2007 - 04:01 PM

gregsd

Master Contributor

• Validated Member
• 171 posts
• Gender:Male
• Location:Surrey, England.
• Interests:Cycling, mostly off-road (MTB) riding.
• United Kingdom

Josh, a similar question was posted on the Google MapInfo-L list awhile back. Have a look here at the thread (hopefully you'll be able to see the thread?). As you'll see, my suggestion of using the convex-hull option didn't work(!), but he went with a solution based on creating voronoi polygons based on the centroid of each line and pline.

HTH

Greg.

Greg Driver

GIS Analyst
MapInfo User...!

### #6 Hans van der Maarel Posted 04 November 2007 - 02:19 AM

Hans van der Maarel

CartoTalk Editor-in-Chief

• 4,178 posts
• Gender:Male
• Location:The Netherlands
• Interests:Cartography, GIS, history, popular science, music.
• Netherlands

Josh, a similar question was posted on the Google MapInfo-L list awhile back. Have a look here at the thread (hopefully you'll be able to see the thread?). As you'll see, my suggestion of using the convex-hull option didn't work(!), but he went with a solution based on creating voronoi polygons based on the centroid of each line and pline.

That's pretty much what I ended up doing in FME:
- Shortened all streets by 5% on either end
- Inserted extra points at 100m intervals
- Replaced the lines with their individual points
- Created Voronoi polygons for all the points
- Dissolved those Voronoi polygons based upon the FIRE_L attribute
- Clipped the whole thing to the accumulated bounding box of the original data (because the Voronoi polygons along the edges stretch quite a distance away)

There was some weird stuff happening around the (elevated) freeways, as sometimes overlapping ramps had different FIRE_L attributes, but apart from that it worked reasonably well.
Hans van der Maarel - Cartotalk Editor
Red Geographics

### #7 bruce Posted 04 November 2007 - 05:29 PM

bruce

Contributor

• Validated Member
• 17 posts
• Gender:Male
• Location:Camden, Maine
• United States

Josh, a similar question was posted on the Google MapInfo-L list awhile back. Have a look here at the thread (hopefully you'll be able to see the thread?). As you'll see, my suggestion of using the convex-hull option didn't work(!), but he went with a solution based on creating voronoi polygons based on the centroid of each line and pline.

That's pretty much what I ended up doing in FME:
- Shortened all streets by 5% on either end
- Inserted extra points at 100m intervals
- Replaced the lines with their individual points
- Created Voronoi polygons for all the points
- Dissolved those Voronoi polygons based upon the FIRE_L attribute
- Clipped the whole thing to the accumulated bounding box of the original data (because the Voronoi polygons along the edges stretch quite a distance away)

There was some weird stuff happening around the (elevated) freeways, as sometimes overlapping ramps had different FIRE_L attributes, but apart from that it worked reasonably well.

Hans,
A question for you if you have the tome. I have just a basic idea of principles behind the Voronoi diagram. One of those being that all locations within an area are closer to the object (here a fire box) than any other object in the set. Because as Josh described situations where an occasional might street segment juts out into what would be another fire box's area this could violate (?) the Voronoi principle. Correct? And, if that was the case, how would you deal with the problem? Did that happen at all with the elevated freeway ramps? Thanks.
bruce
Bruce Hensler

### #8 Hans van der Maarel Posted 05 November 2007 - 01:42 PM

Hans van der Maarel

CartoTalk Editor-in-Chief

• 4,178 posts
• Gender:Male
• Location:The Netherlands
• Interests:Cartography, GIS, history, popular science, music.
• Netherlands

A question for you if you have the tome. I have just a basic idea of principles behind the Voronoi diagram. One of those being that all locations within an area are closer to the object (here a fire box) than any other object in the set. Because as Josh described situations where an occasional might street segment juts out into what would be another fire box's area this could violate (?) the Voronoi principle. Correct? And, if that was the case, how would you deal with the problem? Did that happen at all with the elevated freeway ramps? Thanks.

You're right, the Voronoi principle doesn't deal well with features overlapping eachother. In this case, it looks like Josh doesn't actually need the freeways in there, so I can easily filter those out and redo the process (although there would still be some tunnels causing problems).

If you want to get a really nice result out of this, you're probabely going to end up doing some manual touch-ups in difficult areas.

This is the result after filtering out the freeways:

Hans van der Maarel - Cartotalk Editor
Red Geographics

### #9 bruce Posted 05 November 2007 - 07:34 PM

bruce

Contributor

• Validated Member
• 17 posts
• Gender:Male
• Location:Camden, Maine
• United States

A question for you if you have the tome. I have just a basic idea of principles behind the Voronoi diagram. One of those being that all locations within an area are closer to the object (here a fire box) than any other object in the set. Because as Josh described situations where an occasional might street segment juts out into what would be another fire box's area this could violate (?) the Voronoi principle. Correct? And, if that was the case, how would you deal with the problem? Did that happen at all with the elevated freeway ramps? Thanks.

You're right, the Voronoi principle doesn't deal well with features overlapping eachother. In this case, it looks like Josh doesn't actually need the freeways in there, so I can easily filter those out and redo the process (although there would still be some tunnels causing problems).

If you want to get a really nice result out of this, you're probabely going to end up doing some manual touch-ups in difficult areas.

This is the result after filtering out the freeways:

Thank you Hans for the answer (and Josh for posting the problem). I now see applications for a tool I might have otherwise ignored.
Bruce Hensler

### #10 Josh Posted 07 November 2007 - 05:33 PM

Josh

Contributor

• Validated Member
• 25 posts
• Gender:Male
• Location:San Francisco
• Interests:wild mushrooms, kites &amp; kite boarding, climbing, bouldering, graphic design, dive bars, dive restaurants, diving, museums, movies from the 70z, downloading music that i'll never listen to, politics, bitching about politics, comics (yes...i still read comics but i don't have a star trek outfit), project management, cute girls walking down the street, a perfect latte, good wine (bad wine too), and all that keeps me entertained during the day.
• United States

Hey Everyone,

I haven't been in the office till today(so without my PC that has all my programs on it). Hans shot me an email that looks promising, so I need to check that out too!

Bruce....that is exactly what I am doing with this (I am working for SF DEM right now). when I have the easiest solution (since i'm sure there are a bunch) I'll let you know!

Cheers,
Josh

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

-->