[Met_help] [rt.rap.ucar.edu #61092] History for Convex hull and boundary
John Halley Gotway via RT
met_help at ucar.edu
Fri Apr 26 17:07:32 MDT 2013
----------------------------------------------------------------
Initial Request
----------------------------------------------------------------
Hi,
I would like to have more details on how the convex hull and the boundary of an object are calculated in the MODE tool. I also, wonder how the boundary is calculated for a composite of single objects, once the merging is done.
Thanks
Anna-Belle Filion
----------------------------------------------------------------
Complete Ticket History
----------------------------------------------------------------
Subject: Re: [rt.rap.ucar.edu #61092] Convex hull and boundary
From: Randy Bullock
Time: Thu Apr 25 15:32:35 2013
Hello Anna Belle -
You had some questions about the convex hull and also about
object boundaries.
(1) The convex hull algorithm first finds a lowest (ie, smallest
y-coordinate) point in the object, and then proceeds in
a counterclockwise direction around the object, drawing
straight lines to the next point on the hull. The algorithm
stops when we return to the starting point. This is a simple
algorithm that I developed when I was writing the original
MODE code years ago. It's not very efficient, but it seems
to work.
(2) Object boundaries are polylines outlining the collection
of grid squares that constitute the object. If the object
is in several pieces (as in the case of a composite object
consisting of several simple objects) then there will be
several such outlines, one for each piece of the object.
Hope this helps.
Randy Bullock
On Thu, Apr 25, 2013 at 03:22:21PM -0600, John Halley Gotway via RT
wrote:
>
> Thu Apr 25 15:22:21 2013: Request 61092 was acted upon.
> Transaction: Given to bullock by johnhg
> Queue: met_help
> Subject: Convex hull and boundary
> Owner: bullock
> Requestors: treblecharger34 at hotmail.com
> Status: new
> Ticket <URL:
https://rt.rap.ucar.edu/rt/Ticket/Display.html?id=61092 >
>
>
> This transaction appears to have no content
------------------------------------------------
Subject: Convex hull and boundary
From: Anna-Belle Filion
Time: Thu Apr 25 18:35:44 2013
Hi Randy,
I would like more precision on the convex hull algoritmh.
I am not sure of how the convex hull is created.
Can you elaborate a bit more about what happens after the lowest point
is found and that the algorithm proceeds in a coutnterclockwise
direction around the object.
If you have an illustration it might help as well.
Thanks
Anna-Belle Filion
> Subject: Re: [rt.rap.ucar.edu #61092] Convex hull and boundary
> From: met_help at ucar.edu
> To: treblecharger34 at hotmail.com
> Date: Thu, 25 Apr 2013 15:32:35 -0600
>
>
> Hello Anna Belle -
>
> You had some questions about the convex hull and also about
> object boundaries.
>
> (1) The convex hull algorithm first finds a lowest (ie, smallest
> y-coordinate) point in the object, and then proceeds in
> a counterclockwise direction around the object, drawing
> straight lines to the next point on the hull. The algorithm
> stops when we return to the starting point. This is a simple
> algorithm that I developed when I was writing the original
> MODE code years ago. It's not very efficient, but it seems
> to work.
>
> (2) Object boundaries are polylines outlining the collection
> of grid squares that constitute the object. If the object
> is in several pieces (as in the case of a composite object
> consisting of several simple objects) then there will be
> several such outlines, one for each piece of the object.
>
>
> Hope this helps.
>
> Randy Bullock
>
> On Thu, Apr 25, 2013 at 03:22:21PM -0600, John Halley Gotway via RT
wrote:
> >
> > Thu Apr 25 15:22:21 2013: Request 61092 was acted upon.
> > Transaction: Given to bullock by johnhg
> > Queue: met_help
> > Subject: Convex hull and boundary
> > Owner: bullock
> > Requestors: treblecharger34 at hotmail.com
> > Status: new
> > Ticket <URL:
https://rt.rap.ucar.edu/rt/Ticket/Display.html?id=61092 >
> >
> >
> > This transaction appears to have no content
>
------------------------------------------------
Subject: Re: [rt.rap.ucar.edu #61092] Convex hull and boundary
From: Randy Bullock
Time: Fri Apr 26 08:45:35 2013
Hi Anna-Belle -
It's kind of hard to explain without drawing some pictures, but
I'll try.
We first hollow out the object by removing interior points, since
those points cannot influence the convex hull. Then the remaining
points
are ordered in a "dictionary" fashion, the point (x1, y1) being
less than (x2, y2) if (a) y1 < y2, or if (b) y1 = y2 and x1 < x2.
Orders like this are called dictionary orders in set theory
and topology.
Now that we've got our "smallest" point according to this dictionary
order, we take the horizontal line through that point and consider
that to
be our baseline. We then search through the points of the object to
find the one that makes the smallest angle with the horizontal
baseline.
The line through the current point and this new point becomes a new
baseline, and we search again through the points of the object
to find a point that makes the smallest angle with the new baseline.
As we keep creating new baselines, the baseline rotates
counterclockwise around the outside of the object and traces
out the convex hull.
As for pictures, the wikipedia article on convex hulls at
http://en.wikipedia.org/wiki/Convex_hull
has pictures that are as good as anything I could send you.
Just so you know: I'll be on vacation next week, so if you
have more questions, it'll be a while before you get an answer.
Sorry.
Anyway, I hope this helps.
Randy
On Thu, Apr 25, 2013 at 06:35:44PM -0600, Anna-Belle Filion via RT
wrote:
>
> <URL: https://rt.rap.ucar.edu/rt/Ticket/Display.html?id=61092 >
>
> Hi Randy,
>
> I would like more precision on the convex hull algoritmh.
>
> I am not sure of how the convex hull is created.
>
> Can you elaborate a bit more about what happens after the lowest
point is found and that the algorithm proceeds in a coutnterclockwise
direction around the object.
>
> If you have an illustration it might help as well.
>
> Thanks
> Anna-Belle Filion
>
> > Subject: Re: [rt.rap.ucar.edu #61092] Convex hull and boundary
> > From: met_help at ucar.edu
> > To: treblecharger34 at hotmail.com
> > Date: Thu, 25 Apr 2013 15:32:35 -0600
> >
> >
> > Hello Anna Belle -
> >
> > You had some questions about the convex hull and also about
> > object boundaries.
> >
> > (1) The convex hull algorithm first finds a lowest (ie, smallest
> > y-coordinate) point in the object, and then proceeds in
> > a counterclockwise direction around the object, drawing
> > straight lines to the next point on the hull. The algorithm
> > stops when we return to the starting point. This is a simple
> > algorithm that I developed when I was writing the original
> > MODE code years ago. It's not very efficient, but it seems
> > to work.
> >
> > (2) Object boundaries are polylines outlining the collection
> > of grid squares that constitute the object. If the object
> > is in several pieces (as in the case of a composite object
> > consisting of several simple objects) then there will be
> > several such outlines, one for each piece of the object.
> >
> >
> > Hope this helps.
> >
> > Randy Bullock
> >
> > On Thu, Apr 25, 2013 at 03:22:21PM -0600, John Halley Gotway via
RT wrote:
> > >
> > > Thu Apr 25 15:22:21 2013: Request 61092 was acted upon.
> > > Transaction: Given to bullock by johnhg
> > > Queue: met_help
> > > Subject: Convex hull and boundary
> > > Owner: bullock
> > > Requestors: treblecharger34 at hotmail.com
> > > Status: new
> > > Ticket <URL:
https://rt.rap.ucar.edu/rt/Ticket/Display.html?id=61092 >
> > >
> > >
> > > This transaction appears to have no content
> >
>
------------------------------------------------
Subject: Convex hull and boundary
From: Anna-Belle Filion
Time: Fri Apr 26 16:13:04 2013
Thanks!
It is clear now!
Anna-Belle
> Subject: Re: [rt.rap.ucar.edu #61092] Convex hull and boundary
> From: met_help at ucar.edu
> To: treblecharger34 at hotmail.com
> Date: Fri, 26 Apr 2013 08:45:35 -0600
>
>
> Hi Anna-Belle -
>
> It's kind of hard to explain without drawing some pictures, but
> I'll try.
>
> We first hollow out the object by removing interior points, since
> those points cannot influence the convex hull. Then the remaining
points
> are ordered in a "dictionary" fashion, the point (x1, y1) being
> less than (x2, y2) if (a) y1 < y2, or if (b) y1 = y2 and x1 < x2.
> Orders like this are called dictionary orders in set theory
> and topology.
>
> Now that we've got our "smallest" point according to this dictionary
> order, we take the horizontal line through that point and consider
that to
> be our baseline. We then search through the points of the object to
> find the one that makes the smallest angle with the horizontal
baseline.
> The line through the current point and this new point becomes a new
> baseline, and we search again through the points of the object
> to find a point that makes the smallest angle with the new baseline.
> As we keep creating new baselines, the baseline rotates
> counterclockwise around the outside of the object and traces
> out the convex hull.
>
> As for pictures, the wikipedia article on convex hulls at
> http://en.wikipedia.org/wiki/Convex_hull
> has pictures that are as good as anything I could send you.
>
>
>
> Just so you know: I'll be on vacation next week, so if you
> have more questions, it'll be a while before you get an answer.
> Sorry.
>
>
> Anyway, I hope this helps.
>
> Randy
>
>
>
> On Thu, Apr 25, 2013 at 06:35:44PM -0600, Anna-Belle Filion via RT
wrote:
> >
> > <URL: https://rt.rap.ucar.edu/rt/Ticket/Display.html?id=61092 >
> >
> > Hi Randy,
> >
> > I would like more precision on the convex hull algoritmh.
> >
> > I am not sure of how the convex hull is created.
> >
> > Can you elaborate a bit more about what happens after the lowest
point is found and that the algorithm proceeds in a coutnterclockwise
direction around the object.
> >
> > If you have an illustration it might help as well.
> >
> > Thanks
> > Anna-Belle Filion
> >
> > > Subject: Re: [rt.rap.ucar.edu #61092] Convex hull and boundary
> > > From: met_help at ucar.edu
> > > To: treblecharger34 at hotmail.com
> > > Date: Thu, 25 Apr 2013 15:32:35 -0600
> > >
> > >
> > > Hello Anna Belle -
> > >
> > > You had some questions about the convex hull and also about
> > > object boundaries.
> > >
> > > (1) The convex hull algorithm first finds a lowest (ie,
smallest
> > > y-coordinate) point in the object, and then proceeds in
> > > a counterclockwise direction around the object, drawing
> > > straight lines to the next point on the hull. The
algorithm
> > > stops when we return to the starting point. This is a
simple
> > > algorithm that I developed when I was writing the original
> > > MODE code years ago. It's not very efficient, but it seems
> > > to work.
> > >
> > > (2) Object boundaries are polylines outlining the collection
> > > of grid squares that constitute the object. If the object
> > > is in several pieces (as in the case of a composite object
> > > consisting of several simple objects) then there will be
> > > several such outlines, one for each piece of the object.
> > >
> > >
> > > Hope this helps.
> > >
> > > Randy Bullock
> > >
> > > On Thu, Apr 25, 2013 at 03:22:21PM -0600, John Halley Gotway via
RT wrote:
> > > >
> > > > Thu Apr 25 15:22:21 2013: Request 61092 was acted upon.
> > > > Transaction: Given to bullock by johnhg
> > > > Queue: met_help
> > > > Subject: Convex hull and boundary
> > > > Owner: bullock
> > > > Requestors: treblecharger34 at hotmail.com
> > > > Status: new
> > > > Ticket <URL:
https://rt.rap.ucar.edu/rt/Ticket/Display.html?id=61092 >
> > > >
> > > >
> > > > This transaction appears to have no content
> > >
> >
>
------------------------------------------------
More information about the Met_help
mailing list