Boundary edges of a set of points

I have a set of unstructured (x,y) points which I would like to
compute a boundary polygon for. I don't want the convex hull.

I was able to use matplotlib.tri to get a Delaunay triangulation for
my points by following the examples online, but I'm having trouble
masking everything but the triangles with a boundary edge.
Additionally, once I get this, I'm not clear on how to plot just the
boundary.

Here is what it seems like the mask should be, assume triang comes
from matplotlib.tri.Triangulation().

mask = np.where(np.where(triang.neighbors < 0, 0, 1).all(axis=1), 1, 0)
triang.set_mask(mask)

but, when I plot triang using plot.triplot(), or plt.plot() to plot
the edges, I am getting a bunch of extra stuff that isn't just the
boundary triangles/edges.

Anybody have example code for properly masking and plotting only the
boundary edges?

~Luke

···

--
"Those who would give up essential liberty to purchase a little
temporary safety deserve neither liberty nor safety."

-- Benjamin Franklin, Historical Review of Pennsylvania, 1759

Luke,

I am not entirely clear exactly what you want to do, but I’ll try to help.

Your masking of the triangulation masks the triangles not the edges, and so your triplot call displays those triangles that include a boundary edge but also the other edges of those triangles. As you say, this isn’t what you want.

I’ve attached an example script that follows on from your idea of testing triang.neighbors to determine the boundary edges, and displays just those edges. However, this is the convex hull as, by definition, the boundary of an unconstrained Delaunay triangulation is the convex hull. As you don’t want the convex hull, I am not clear what you want instead.

If I have misunderstood your requirements and/or you have further questions, please post your example code as it is much easier for others on the mailing list to correct existing code than come up with their own freestanding example.

I hope some of this helps!
Ian Thomas

tri_boundaries.py (970 Bytes)

···

On 28 April 2011 08:51, Luke <hazelnusse@…287…> wrote:

I have a set of unstructured (x,y) points which I would like to

compute a boundary polygon for. I don’t want the convex hull.

I was able to use matplotlib.tri to get a Delaunay triangulation for

my points by following the examples online, but I’m having trouble

masking everything but the triangles with a boundary edge.

Additionally, once I get this, I’m not clear on how to plot just the

boundary.

Here is what it seems like the mask should be, assume triang comes

from matplotlib.tri.Triangulation().

mask = np.where(np.where(triang.neighbors < 0, 0, 1).all(axis=1), 1, 0)

triang.set_mask(mask)

but, when I plot triang using plot.triplot(), or plt.plot() to plot

the edges, I am getting a bunch of extra stuff that isn’t just the

boundary triangles/edges.

Anybody have example code for properly masking and plotting only the

boundary edges?

~Luke

Ian,
  Thanks for the response and the example code. I guess what I'm
trying to do might be well defined. Here is a plot that should
illustrate the data I'm working with:

http://biosport.ucdavis.edu/blog/copy_of_steady_benchmark_tau.png

The green and red regions are being displayed by plotting each and
every point in my data set that is stable. So the set of points I was
describing in my original message looks like these green and red
regions.

What I would like is just the boundary of the stable region, which
maybe isn't a very well defined statement. The convex hull of these
points would enclose a part of the x-y plane that isn't stable, so I
don't want to include it in my plot.

I am thinking that perhaps the approach I should be taking should
involve contouring the real part of the eigenvalues which determine
the stability, and then plot the zero-level curve. I'll have to think
about that some more.

Is it clear what I am trying to do? If so, do you think the Delaunay
triangulation is the right way to go?

~Luke

···

On Thu, Apr 28, 2011 at 2:14 PM, Ian Thomas <ianthomas23@...287...> wrote:

On 28 April 2011 08:51, Luke <hazelnusse@...287...> wrote:

I have a set of unstructured (x,y) points which I would like to
compute a boundary polygon for. I don't want the convex hull.

I was able to use matplotlib.tri to get a Delaunay triangulation for
my points by following the examples online, but I'm having trouble
masking everything but the triangles with a boundary edge.
Additionally, once I get this, I'm not clear on how to plot just the
boundary.

Here is what it seems like the mask should be, assume triang comes
from matplotlib.tri.Triangulation().

mask = np.where(np.where(triang.neighbors < 0, 0, 1).all(axis=1), 1, 0)
triang.set_mask(mask)

but, when I plot triang using plot.triplot(), or plt.plot() to plot
the edges, I am getting a bunch of extra stuff that isn't just the
boundary triangles/edges.

Anybody have example code for properly masking and plotting only the
boundary edges?

~Luke

Luke,

I am not entirely clear exactly what you want to do, but I'll try to help.

Your masking of the triangulation masks the triangles not the edges, and so
your triplot call displays those triangles that include a boundary edge but
also the other edges of those triangles. As you say, this isn't what you
want.

I've attached an example script that follows on from your idea of testing
triang.neighbors to determine the boundary edges, and displays just those
edges. However, this is the convex hull as, by definition, the boundary of
an unconstrained Delaunay triangulation is the convex hull. As you don't
want the convex hull, I am not clear what you want instead.

If I have misunderstood your requirements and/or you have further questions,
please post your example code as it is much easier for others on the mailing
list to correct existing code than come up with their own freestanding
example.

I hope some of this helps!
Ian Thomas

--
"Those who would give up essential liberty to purchase a little
temporary safety deserve neither liberty nor safety."

-- Benjamin Franklin, Historical Review of Pennsylvania, 1759

If you generate a big list of all the edges from the triangle data,
you should get repeat entries only for all the internal edges. You
could then find all the duplicates using this recipe
http://stackoverflow.com/questions/1920145/how-to-find-duplicate-elements-in-array-using-for-loop-in-python-like-c-c
i.e.
dups = [x for x in list_a if list_a.count(x) > 1]

After removing all of these, you should be left with just the boundary edges.

Gary R.

···

On Fri, Apr 29, 2011 at 7:56 AM, Luke <hazelnusse@...287...> wrote:

Ian,
Thanks for the response and the example code. I guess what I'm
trying to do might be well defined. Here is a plot that should
illustrate the data I'm working with:

http://biosport.ucdavis.edu/blog/copy_of_steady_benchmark_tau.png

The green and red regions are being displayed by plotting each and
every point in my data set that is stable. So the set of points I was
describing in my original message looks like these green and red
regions.

What I would like is just the boundary of the stable region, which
maybe isn't a very well defined statement. The convex hull of these
points would enclose a part of the x-y plane that isn't stable, so I
don't want to include it in my plot.

I am thinking that perhaps the approach I should be taking should
involve contouring the real part of the eigenvalues which determine
the stability, and then plot the zero-level curve. I'll have to think
about that some more.

Is it clear what I am trying to do? If so, do you think the Delaunay
triangulation is the right way to go?

~Luke

On Thu, Apr 28, 2011 at 2:14 PM, Ian Thomas <ianthomas23@...287...> wrote:

On 28 April 2011 08:51, Luke <hazelnusse@...287...> wrote:

I have a set of unstructured (x,y) points which I would like to
compute a boundary polygon for. I don't want the convex hull.

I was able to use matplotlib.tri to get a Delaunay triangulation for
my points by following the examples online, but I'm having trouble
masking everything but the triangles with a boundary edge.
Additionally, once I get this, I'm not clear on how to plot just the
boundary.

Here is what it seems like the mask should be, assume triang comes
from matplotlib.tri.Triangulation().

mask = np.where(np.where(triang.neighbors < 0, 0, 1).all(axis=1), 1, 0)
triang.set_mask(mask)

but, when I plot triang using plot.triplot(), or plt.plot() to plot
the edges, I am getting a bunch of extra stuff that isn't just the
boundary triangles/edges.

Anybody have example code for properly masking and plotting only the
boundary edges?

~Luke

Luke,

I am not entirely clear exactly what you want to do, but I'll try to help.

Your masking of the triangulation masks the triangles not the edges, and so
your triplot call displays those triangles that include a boundary edge but
also the other edges of those triangles. As you say, this isn't what you
want.

I've attached an example script that follows on from your idea of testing
triang.neighbors to determine the boundary edges, and displays just those
edges. However, this is the convex hull as, by definition, the boundary of
an unconstrained Delaunay triangulation is the convex hull. As you don't
want the convex hull, I am not clear what you want instead.

If I have misunderstood your requirements and/or you have further questions,
please post your example code as it is much easier for others on the mailing
list to correct existing code than come up with their own freestanding
example.

I hope some of this helps!
Ian Thomas

--
"Those who would give up essential liberty to purchase a little
temporary safety deserve neither liberty nor safety."

-- Benjamin Franklin, Historical Review of Pennsylvania, 1759

------------------------------------------------------------------------------
WhatsUp Gold - Download Free Network Management Software
The most intuitive, comprehensive, and cost-effective network
management toolset available today. Delivers lowest initial
acquisition cost and overall TCO of any competing solution.
http://p.sf.net/sfu/whatsupgold-sd
_______________________________________________
Matplotlib-users mailing list
Matplotlib-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/matplotlib-users

That involves iterating through your list_a a number of times to look for elements. It probably would be much faster to use something like the Counter class to just get the items that occur once or more than once:

http://docs.python.org/library/collections.html#counter-objects

Thanks,

Jason

···

On 4/28/11 9:03 PM, gary ruben wrote:

http://stackoverflow.com/questions/1920145/how-to-find-duplicate-elements-in-array-using-for-loop-in-python-like-c-c
i.e.
dups = [x for x in list_a if list_a.count(x)> 1]

I am thinking that perhaps the approach I should be taking should

involve contouring the real part of the eigenvalues which determine

the stability, and then plot the zero-level curve. I’ll have to think

about that some more.

This sounds like a very sensible approach and is quick and easy to try out using tricontour/tricontourf. You may have to use a very small positive value for the contour level rather then zero to get what you want.

Is it clear what I am trying to do? If so, do you think the Delaunay

triangulation is the right way to go?

Yes, it is clear what you are trying to do. I think that you shouldn’t be concerned with the triangulation, Delaunay or not, as this is at too low a level for what you are attempting. Stick to the high-level data analysis and presentation functions like tricontour and ignore details of the underlying triangulation. If you are having to manipulate a triangulation then you are becoming a computational geometrist - it is a completely valid and interesting thing to do but is probably taking your attention away from your real work.

Ian

···

On 28 April 2011 22:56, Luke <hazelnusse@…287…> wrote: