[postgis-users] Amoeba Hulls

Stephen Woodbridge woodbri at swoodbridge.com
Wed Jul 5 12:50:48 PDT 2006


Graham,

The algorithm I just posted would not create a convex hull, in fact it 
would look more like your reference below.

William Andersen wrote:
> Thanks for all the suggestions, they are giving me a lot to think about.
> 
> Unfortunately it's not always a convex hull. More complex patterns 
> appear to have wedges taken out of them, like you can see in this image
> 
> http://www.esri.com/software/arcgis/extensions/businessanalyst/graphics/market-boundaries-lg.jpg
> 
> It appears that, in our case, the hulls contain the 80% of closest 
> members as the crow flies (although some of the examples i've seen 
> online seem to use drivetimes). Then they somehow construct a polygon 
> that contains exactly those 80% and none of the remaining 20% - are 
> there any standard routines for that? Presumably once they've got that 
> polygon they replace the line segments with curves.
> 
> If i can create something that meets the same rules and has a similar 
> "look" then i'm sure it would suffice.

This is where the basic problem lies ... no one seems to know what the 
rules are for this. We can only speculate based on the various images 
and examples you have pointed us at. Try my algorithm using postgis 
distance.

-Steve

> Graham
> 
> On 7/5/06, *Mike Leahy * <mgleahy at alumni.uwaterloo.ca 
> <mailto:mgleahy at alumni.uwaterloo.ca>> wrote:
> 
>     Hey there,
> 
>     If you can determine the closest 80% of points by whatever criteria,
>     wouldn't you be able to use the convexhull() function?  I just tried
>     this, and it looks okay to me:
> 
>     testdb=# select astext(convexhull('MULTIPOINT((0 1),(0 0),(1 0),(1
>     1))'::geometry));
>                   astext
>     --------------------------------
>       POLYGON((0 0,0 1,1 1,1 0,0 0))
>     (1 row)
> 
>     I did the same thing after creating a points table with the separate in
>     individual records with the same overall coordinates in the multipoint
>     example above, and it worked okay too:
> 
>     testdb=# select astext(convexhull(collect(p))) from testpoint;
>                   astext
>     --------------------------------
>       POLYGON((0 0,0 1,1 1,1 0,0 0))
>     (1 row)
> 
>     It wouldn't be too hard to modify this to work using where condition
>     that filters out the records of interest...or maybe on a saved view.
> 
>     The only problem is that it wouldn't produce a nice curvy polygon
>     outline like in the sample William provided.
> 
>     Regards,
>     Mike
> 
>     Paul Ramsey wrote:
>      > So my guess is that you use drive-time to segment your population of
>      > customers relative to the store into the "nearest X%" and then
>     draw a
>      > "shape" around that cloud of points.  And drawing the shape is
>     the "fun"
>      > part.
>      >
>      > William Andersen wrote:
>      >> It appears to be the same as this functionality in Business Analyst
>      >>
>      >>
>     http://www.esri.com/software/arcgis/extensions/businessanalyst/about/customer-market.html
>      >>
>     <http://www.esri.com/software/arcgis/extensions/businessanalyst/about/customer-market.html>
>      >>
>      >>
>      >> I thought this was done using some older version of Arcview, but i'm
>      >> not very familiar with esri's offerings.
>      >>
>      >> Will
>      >>
>      >> On 7/5/06, *Paul Ramsey * < pramsey at refractions.net
>     <mailto:pramsey at refractions.net>
>      >> <mailto:pramsey at refractions.net
>     <mailto:pramsey at refractions.net>>> wrote:
>      >>
>      >>     This wouldn't be in vanilla arcview, was it in Network Analyst?
>      >> The top
>      >>     80% of points by drive distance might yield this
>     shape.  Finding the
>      >>     points would be straightforward, and then the hull building
>     would
>      >> be the
>      >>     hand-waving part.
>      >>
>      >>     P
>      >>
>      >>     William Andersen wrote:
>      >>      > Paul, Steve,
>      >>      >
>      >>      > Thanks for the quick replies, unfortunately it's pretty
>     hard to
>      >> tell
>      >>      > from those images if they match.
>      >>      >
>      >>      > I've done some more digging and it turns out that these
>     shapes
>      >> were
>      >>      > created in Arcview 3.x. The notes I have say...
>      >>      >
>      >>      >  > This approach selects a number of the outliers and
>     joins the
>      >>     extreme
>      >>      > points using elliptical arcs.
>      >>      >  > The arcs are all created in a direction moving out
>     from the
>      >>     store.
>      >>      >
>      >>      > However, I dont see customer points at the
>     discontinuities in the
>      >>     hulls,
>      >>      > so it appears that the "extreme points" are perhaps
>     interpolated.
>      >>      >
>      >>      >
>      >>      > Will
>      >>      >
>      >>      > On 7/5/06, *Paul Ramsey* < pramsey at refractions.net
>     <mailto:pramsey at refractions.net>
>      >>     <mailto: pramsey at refractions.net
>     <mailto:pramsey at refractions.net>>
>      >>      > <mailto:pramsey at refractions.net
>     <mailto:pramsey at refractions.net>
>      >>     <mailto: pramsey at refractions.net
>     <mailto:pramsey at refractions.net>>>> wrote:
>      >>      >
>      >>      >     William,
>      >>      >
>      >>      >     It doesn't look like this is a standard algorithm,
>     but more
>      >>     likely a
>      >>      >     particular empirical technique provided by the particular
>      >>     software you
>      >>      >     were using.  So substituting some other technique might
>      >> yield a
>      >>      >     different shape entirely... do any of the techniques
>      >>     mentioned here
>      >>      >
>      >>
>     <http://www.geospatial-online.com/geospatialsolutions/article/articleDetail.jsp?id=1348
>     <http://www.geospatial-online.com/geospatialsolutions/article/articleDetail.jsp?id=1348>
>      >>
>      >>      >     <
>      >>
>      >>
>     http://www.geospatial-online.com/geospatialsolutions/article/articleDetail.jsp?id=1348
>     <http://www.geospatial-online.com/geospatialsolutions/article/articleDetail.jsp?id=1348>>>
>      >>
>      >>      >     sound like what was done to your data?
>      >>      >
>      >>      >     Paul
>      >>      >
>      >>      >     William Andersen wrote:
>      >>      >      >
>      >>      >      > I'm fairly new to postgis, and working to automate a
>      >> number of
>      >>      >      > processes.
>      >>      >      >
>      >>      >      > We are trying to compute market area polygons that
>     look
>      >>     like the
>      >>      >      > attached image. These were created by some older
>     software.
>      >>      >      >
>      >>      >      >
>      >>      >      > They are referred to as Amoeba Hulls, and they
>     contain 80%
>      >>     of a
>      >>      >      > store's customers. However I can't find any solid
>      >>     documentation that
>      >>      >      > would allow me to reproduce them.
>      >>      >      >
>      >>      >      > Does anyone have any ideas how these shapes are
>     created
>      >> or an
>      >>      >      > alternate name that I might be able to google?
>      >>     Additionally, we may
>      >>      >      > be in a position to finance the development of this
>      >> feature.
>      >>      >      >
>      >>      >     _______________________________________________
>      >>      >     postgis-users mailing list
>      >>      >     postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>
>      >>     <mailto:postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>>
>      >>      >     <mailto:postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>
>      >>     <mailto: postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>>>
>      >>      >    
>     http://postgis.refractions.net/mailman/listinfo/postgis-users
>      >>      >
>      >>      >
>      >>      >
>      >>      >
>      >>
>      >>
>     ------------------------------------------------------------------------
>      >>      >
>      >>      > _______________________________________________
>      >>      > postgis-users mailing list
>      >>      > postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>
>      >>     <mailto: postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>>
>      >>      > http://postgis.refractions.net/mailman/listinfo/postgis-users
>      >>
>      >>     _______________________________________________
>      >>     postgis-users mailing list
>      >>     postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>
>      >>     <mailto: postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>>
>      >>    
>     http://postgis.refractions.net/mailman/listinfo/postgis-users
>     <http://postgis.refractions.net/mailman/listinfo/postgis-users>
>      >>
>      >>
>      >>
>      >>
>     ------------------------------------------------------------------------
>      >>
>      >> _______________________________________________
>      >> postgis-users mailing list
>      >> postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>
>      >> http://postgis.refractions.net/mailman/listinfo/postgis-users
>     <http://postgis.refractions.net/mailman/listinfo/postgis-users>
>      >
>      > _______________________________________________
>      > postgis-users mailing list
>      > postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>
>      > http://postgis.refractions.net/mailman/listinfo/postgis-users
>      >
>     _______________________________________________
>     postgis-users mailing list
>     postgis-users at postgis.refractions.net
>     <mailto:postgis-users at postgis.refractions.net>
>     http://postgis.refractions.net/mailman/listinfo/postgis-users
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users




More information about the postgis-users mailing list