how to order polygon vertices
bhaskar dongare
in clockwise or anti clockwise direction
helper
Assuming you are working with a convex polygon, you can sort the
vertices using something like:
[ignore I] = sort(angle(complex(x-mean(x),y-mean(y))));
x = x(I)
y = y(I)
PB
Hi helper!
I assume that you meant:
[ignore I] = sort([angle(complex(x-mean(x),y-mean(y)))])
Otherwise, y-mean(y) would denote the dimension, which would probably
lead to an error.
Also using [I I]=sort..., saves some space, avoiding the extra
variable "ignore".
Just my 0.05 kr
/PB
/PB
bhaskar
I was looking for non-convex polygon vertices.
David Epstein
>
>
> Thanks for your help !!
> I was looking for non-convex polygon vertices.
>
If you define vertices using some random process, and if the polygon
you want to extract from this is not convex, then your problem is not
well-defined. Take, for example, three points. These give a triangle.
A fourth point, inside the triangle, defines three DIFFERENT polygons
with four sides. Each possible ordering of the four vertices will
define one of these three polygons. (There are 24=4! orderings. There
are 8 orderings corresponding to each of the three polygons, given by
cyclic permutation, and changing clockwise order to anti-clockwise.)
There are a vast number of difficult and distinct problems that could
be possible interpretations of your question. If you really want an
answer, you will need to make your question much more precise. I
would imagine that very few of these problems have feasible solutions
if there are more than a handful of vertices.
David
helper
>
>[ignore I] = sort([angle(complex(x-mean(x),y-mean(y)))])
I'm sorry PB, I'm not following you. The one-liner I gave should be
equivalent to:
tmp = complex(x-mean(x),y-mean(y));
tmp = angle(tmp);
[ignore I] = sort(tmp);
As far as I know, COMPLEX doesn't use a dimension argument. How does
using [] change things?
> Also using [I I]=sort..., saves some space, avoiding the
> extra variable "ignore".
Good tip. I typically use the name "ignore" to indicate to future
readers of my code that the variable will be intentionally ignored.
However, using [I I] along with a comment in the code would equally
as descriptive.
bhaskar wrote:
> I was looking for non-convex polygon vertices.
The difference between working with convex and noncovex polygons here
is in what you select as your point of reference. Using a different
point of reference can result in a different ordering.
For a convex polygon, selecting any point within the polygon will
result in the same ordering. In my previous example, I selected the
center point (using MEAN).
For a nonconvex polygon, you will need to define your point of
reference, then proceed from there. Simply replace "mean(x)" and
"mean(y)" in the previous code with "xr" and "yr" that you have
defined.
bhaskar
Thanks !!
I am sorry not to make it clear.I am using the alpha shape algorithm
to come up with non convex boundary and it gives me vertices in some
order, I need put in order (clocksiwe or anti clockwise) and then use
INPOLYGON to determine whether a given point is inside this non
convex boundary. Hope this will make clear.
PB
>
>
>> PB wrote:
>>
>>[ignore I] = sort([angle(complex(x-mean(x),y-mean(y)))])
>>> Just my 0.05 kr
>
> I'm sorry PB, I'm not following you. The one-liner I gave should be
> equivalent to:
>
> tmp = complex(x-mean(x),y-mean(y));
> tmp = angle(tmp);
> [ignore I] = sort(tmp);
>
wrong, splitting your complex call and making sort handle it as the
dimension argument ( the one I tried to refer to). Sorry for the
inconvienience.
/PB
David Epstein
Sorry, it's still unclear, at least to me. I don't know much about
it, but I think that alpha shapes are not necessarily polygons. In
general, they are graphs in the plane.
But let's assume your alpha shape is a polygon, or at least that you
somehow have a polygon given, lying inside an alpha shape. The
question then is whether your data includes knowledge of the edges of
the polygon. If so, you just follow them around cyclically, and that
answers your question. If you aren't given the edges, and have no way
of computing them, then the question is not well-defined.
I don't think that sorting the vertices on the angles, as discussed
by PB and helper, will work. It will work if the polygon is
star-shaped, and the reference point is chosen correctly---but is
there an easy way to choose a reference point (from which one can
"see" all the edges) for a star-shaped polygon?. Sorting by angles is
not necessary if you are able to just follow the edges round, as I
explained in the previous paragraph.
If you take any polygon at all, then I think that, by adding extra
vertices spread fairly uniformly all over the polygon's edges, you
can make it into an alpha shape for a suitable value of alpha. So
your alpha shape is not going to be star-shaped in general.
David
Kelly
> Thanks !!
> I am sorry not to make it clear.I am using the alpha shape
> algorithm
> to come up with non convex boundary and it gives me vertices in
> some
> order, I need put in order (clocksiwe or anti clockwise) and then
> use
> INPOLYGON to determine whether a given point is inside this non
> convex boundary. Hope this will make clear.
If you have the Mapping Toolbox, you can use poly2cw or poly2ccw.
-Kelly
bhaskar
**************************
David,
Thanks a lot !!
Yes, you are right I got the edges at the end of alpha shape
algorithm but the problem is that they are not in sequence. So
question here is how to arrange all those edges cyclically ??
thanks in advance
David Epstein
> **************************
> David,
> Thanks a lot !!
> Yes, you are right I got the edges at the end of alpha shape
> algorithm but the problem is that they are not in sequence. So
> question here is how to arrange all those edges cyclically ??
>
> thanks in advance
Your question is still unclear. Maybe we are not making progress and
this thread should be closed?
1. There is a question about the definition of an alpha shape. For
example, are edges allowed to cross or not? This would not be a
question for this newsgroup, but for a newsgroup in computational
geometry.
2. There is the problem that alpha shapes are not, in general,
polygons, but graphs. This is not an issue appropriate to this ng.
3. Assuming that you are indeed working with a polygon, there is the
question of how that polygon is represented in your Matlab data. The
algorithm needed is obvious, so you may well be having some other
difficulty that may or may not be relevant to this ng. (Please think
about this before posting again.) Here is the obvious algorithm:
Find an edge.
Find an endpoint of this edge.
Find the other edge with this endpoint.
Find the other endpoint of this edge.
Continue until the original edge is repeated.
Efficient implementation of this obvious algorithm in Matlab will
depend on how your data is arranged, via arrays, or cell arrays, etc
etc. Are the two endpoints of an edge readily computable from knowing
the edge? Are the two edges meeting at a vertex readily computable
from knowledge of the vertex?
I'm assuming the number of vertices is large, otherwise there is no
point in worrying about efficiency. At the moment, I see no way of
avoiding loops, but it's possible that there is a clever way of
changing the way you store your data so that the obvious algorithm
can be vectorized.
David
Mohit Kumar
> in clockwise or anti clockwise direction