[postgis-users] Amoeba Hulls
Mike Leahy
mgleahy at alumni.uwaterloo.ca
Wed Jul 5 15:24:04 PDT 2006
Hello again,
Here's another idea...what about creating a TIN from your point sets? I
don't know if this has been done in PostGIS yet, but I'm pretty sure you
could find one or more algorithms for generating a TIN in various
spatial analysis textbooks, or online somewhere.
If you can make a TIN, then your area of interest could be generated by
the geomunion of all triangles in the TIN where all three of triangle's
vertices are one of the 80% closest points. If I'm thinking right, then
this should produce a shape that is not necessarily convex. Does that
sound right to anyone else?
Just thought I'd put the idea out there...
Mike
William Andersen wrote:
> Steve,
>
> I think you are onto something.
>
> There are exactly 101 points in each of the polygons in the (small)
> sample set that I have.
>
> When i get a little more time i'll plot these with 3.6 degree wedges and
> see if anything jumps out at me.
>
> My working theory is that there are a set of rules determining what
> happens at each control point. In some cases it's pretty simple as we
> have enough points to pick one that includes the 80% points but not the
> 20% points. In other cases it seems to be extrapolated from the
> neighboring points using some kind of fitted curve.
>
> Will
>
> On 7/5/06, *Stephen Woodbridge* <woodbri at swoodbridge.com
> <mailto:woodbri at swoodbridge.com>> wrote:
>
> Paul,
>
> Would you not just connect the dots, like this.
>
> 1) determine the 80% points, say by distance or whatever
> 2) order the points by radial angle increasing and radius decreasing
> 3) use something like a window say plus/minus 1/2 degree and select the
> maximum radius in the window and add that point to the polygon
> 4) step 1/2 degree and repeat 3)
> 5) close the polygon
>
> You probably need to have some special handling if there is a sudden
> change in radius to make sure no points get clicked out of the polygon.
>
> Anyway I think this would be a good start to the algorithm.
>
> -Steve
>
> Paul Ramsey wrote:
> > Indeed, nice to see that everything can be strung together. I am
> trying
> > to visualize what a "squishyhull" function would have to do to work
> > though :) It's a not uncommon request... the calculated
> equivalent of
> > someone squinting and drawing a line around a group of points.
> >
> > P
> >
> > Mike Leahy 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
> <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
> >>>>
> >>>>
> >>>>
> >>>>
> ------------------------------------------------------------------------
> >>>>
> >>>>
> >>>> _______________________________________________
> >>>> 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
> <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
> <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