[postgis-users] Amoeba Hulls
Jessica M Salmon
jmsalmon at fs.fed.us
Wed Jul 5 12:57:53 PDT 2006
William,
We group points into polygons to generate fire perimeters from discrete
active fire detections (from satellites images). To do this, we use an
algorithm known as Alpha Shapes.
http://n.ethz.ch/student/fischerk/alphashapes/as/
The picture you reference below looks similar to these Alpha Shapes.
I have not yet implemented this processing in our postgis database. If I
do, I will post the function to the mailing list, but honestly it's not
very high priority ATM.
Cheers,
Meghan
"William
Andersen"
<wkandersen at gmail To
.com> "PostGIS Users Discussion"
Sent by: <postgis-users at postgis.refractions.
postgis-users-bou net>
nces at postgis.refr cc
actions.net
Subject
Re: [postgis-users] Amoeba Hulls
07/05/2006 01:40
PM
Please respond to
PostGIS Users
Discussion
<postgis-users at po
stgis.refractions
.net>
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.
Graham
On 7/5/06, Mike Leahy <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>> 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>>> 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
>>
>>
>> > 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>>
>> >
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
>
> _______________________________________________
> postgis-users mailing list
> 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
_______________________________________________
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