polygon from list of points
Eli Brosh
Nathann Cohen
Could you be by any chance trying to compute the convex hull of a set
of points ?
http://en.wikipedia.org/wiki/Convex_hull
Nathann
Alex Ghitza
> Could you be by any chance trying to compute the convex hull of a set
> of points ?
In which case you would want to do for example:
sage: poly = Polyhedron(vertices=[(0, 0), (3, 0), (0, 3), (1, 1)])
sage: poly
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices.
sage: poly.vertices()
[[0, 0], [3, 0], [0, 3]]
Note that Sage realised that (1, 1) was in the interior and ignored it.
There are a bunch of things you can do with your shiny new polygon now,
here is what tab-completion gives me:
sage: poly.
poly.Hrep_generator poly.field poly.projection
poly.Hrepresentation poly.gale_transform poly.pyramid
poly.Vrep_generator poly.graph poly.radius
poly.Vrepresentation poly.ieqs poly.radius_square
poly.adjacency_matrix poly.incidence_matrix poly.ray_generator
poly.ambient_dim poly.inequalities poly.rays
poly.bipyramid poly.inequality_generator poly.rename
poly.bounded_edges poly.intersection poly.render_solid
poly.category poly.is_compact poly.render_wireframe
poly.cdd_Hrepresentation poly.is_simple poly.reset_name
poly.cdd_Vrepresentation poly.line_generator poly.save
poly.center poly.linearities poly.schlegel_projection
poly.db poly.lines poly.show
poly.dim poly.lrs_volume poly.simplicial_complex
poly.dump poly.n_Hrepresentation poly.triangulated_facial_incidences
poly.dumps poly.n_Vrepresentation poly.union
poly.edge_truncation poly.n_equations poly.version
poly.equation_generator poly.n_facets poly.vertex_adjacencies
poly.equations poly.n_inequalities poly.vertex_adjacency_matrix
poly.f_vector poly.n_lines poly.vertex_generator
poly.face_lattice poly.n_rays poly.vertex_graph
poly.facet_adjacency_matrix poly.n_vertices poly.vertex_incidences
poly.facial_adjacencies poly.polar poly.vertices
poly.facial_incidences poly.prism
Feel free to explore these and ask more questions.
Best,
Alex
--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- Australia -- http://www.ms.unimelb.edu.au/~aghitza/
Simon King
If I imagine the typical shape of a hysteresis (see the pictures at
http://en.wikipedia.org/wiki/Hysteresis), I think Convex Hull is not
suitable -- simply since the polygonal region is not convex.
I think what some people do (this would be a very basic example of
persistent homology) is to replace the data points by discs of radius
r. If d discs overlap, then join their centre points by a (d-1)-
simplex; i.e., if two discs overlap, join them by an edge, if three
discs overlap, fill in a triangle.
In that way, a simplicial complex emerges (that of course depends on
the choice of the radius r). The machinery of persistent homology
would now test how long homology elements (geometrically corresponding
to circles, spheres, etc) survive when r varies. The circle that
survives longest apparently gives you the boundary of the polygon that
you are looking for, and it could even cope with some noise in your
data.
I think there is no persistent homology implemented in Sage, is it?
The "persistent group cohomology" in our cohomology spkg has a
different scope and wouldn't help here.
But back to Eli's question: If the data are sufficiently nice, then it
may be worth a try to join each data point with its two nearest
neighbours. Perhaps some hand work will be needed to adjust things,
but I don't think that there is any algorithm that is as good as the
human eye.
Cheers,
Simon
Simon King
I wrote:
[...]
> But back to Eli's question: If the data are sufficiently nice, then it
> may be worth a try to join each data point with its two nearest
> neighbours. Perhaps some hand work will be needed to adjust things,
> but I don't think that there is any algorithm that is as good as the
> human eye.
Hmph. I guess this was too simplistic. In particular, if your data
points lie very dense, the "two nearest neighbours" approach would
miserably fail.
However, the more elaborate approach (have discs of radius r around
your data points and choose r so that the overlapping discs are
topologically a circle) might be worth a try. The notion for it is
Rips complex, see http://en.wikipedia.org/wiki/Rips_complex
Best regards,
Simon
Jaap Spies
I don't think so. But maybe sage can help (as Python) with a naive approach.
If you have a closed polygon of n points with (x_n, y_n) = (x_0, y_0)
the area can be calculated with a well known(?) formula
A = 1/2 sum from i=0 to i=n-1 (y_{i+1} - y_i)(x_{i+1} + x_i)
First we sort the data set in increasing order on the first coordinate
that will give us (x_0, y_0).
Stepping through the data set we try to split it up in two parts.
If x_{i+1} = x_i and abs(y_{i+1} - y_i) < some small value we throw away
that datapoint else we move the point with the larger y value to data set 2.
If y_{i+1} - y_i > a(x_{i+1} - x_i) for some a(?) we move the
point to data set 2 else we keep it in what we call data set 1.
Now we sort data set 2 in decreasing order and put 1 and 2 together.
The formula above gives us the area.
This looks very naive and simplistic, but I hope this helps,
Jaap
kcrisman
I don't think so, but it might make a really great senior project to
implement some basic stuff, as there are now several accessible
introductions at the late-undergrad/early-grad level. Also, do you
know if any of the current implementations correctly licensed to be
done as an spkg?
- kcrisman
Robert Dodier
> I have a scanned digitized graph of a magnetic hysteresis loop.
> That is, I have a list of points [(H0,B0),(H1,B1)....(Hn,Bn)]
> however, the points are not ordered in any meaningful way.
> In order to calculate the hysteresis loss, which is the area enclosed by the
> loop, I need to somehow convert the list of points into a polyngon
> (clockwise or counterclockwise).
Hmm, that's an interesting problem. Since you know the physical
process, how about treating this as a curve fitting exercise,
trying to find the hysteresis curve which best fits the data in
(say) the least orthogonal squares sense. I am assuming that
a hysteresis curve has some well-known parametrization.
Just minimize the goodness of fit over the free parameters of
the curve. (Treating the endpoints as free parameters is probably
going to complicate it, but that's only a practical problem.)
I am assuming that for given parameters, it is easy to compute the
area inside the loop. As a bonus you'll get estimates of the
physical parameters which might be interesting in themselves.
Take a look at Seber & Wild, "Nonlinear Regression".
Dunno if such a problem is in there but you might get some
inspiration.
good luck
Robert Dodier
Eli Brosh
The answer is obviously not a convex hull since the shape of hysteresis loops is not convex.
Currently, it seems to me that the best proposal is to use some known formula for the hysteresis loop and treat the problem as a curve fitting exercise.
I now realize that the original problem is not simple. It is called "polygonization". There are actually some algorithms in the literature to solve this problem for special cases but not a general solution.
For n points there are n! possibilities of ordering them. It is really a mess to sort out of this huge number the arrangements that result in a simple polygon and choose a particular "best polygon" out of this.
But this is too much for me. I will try the curve fitting approach. Perhaps someone else is interested in solving the original problem. It is still interesting.
Regards,
Eli
Jaap Spies
> Thank you for your answers,
> The answer is obviously not a convex hull since the shape of hysteresis
> loops is not convex.
> Currently, it seems to me that the best proposal is to use some known
> formula for the hysteresis loop and treat the problem as a curve fitting
> exercise.
Can you make your actual data set available for experimentation?
Jaap