[vtkusers] (no subject)

[Benjamin King]

Hello Shyam,

I'll try to explain the method I proposed with more detail, so you can see 
if it's applicable for you.

You are interested in the boundary of a closed polygon that is described by 
a set of points. The more you know about the possible forms of the polygon 
and about the distribution of the points, the easier it is to find the 
solution.

The proposed method generalizes as follows:

1) Find a point c from which all the polygon edges are visible. I think the 
set of all such points is called the kernel of that polygon, but I'm not 
quite sure. For convex polygons it is easy to find - the whole area of the 
polygon is the kernel and the mean of all the points belongs to it. It will 
also work for certain non-convex polygons like the bean shaped one you 
mentioned or a star shaped one, but it may be harder to find a suitable 
point because you don't know the edges of the polygon in advance.

2) Sort the points with respect to the angle of the line segment between 
them and c and you're done.

So my advice to you is to check if the polygons you want to find have a 
non-empty kernel and if it is easy to find a point of the kernel with only 
the pointset you have.

If that is not the case but your points are dense, you can also start with 
two sets of points, a connected set A (empty in the beginning) and an 
unconnected set B (all remaining points). Move any point from B to A. And 
now iteratively seek the closest pair (a, b) with a in A and b in B, 
connect them and move b to A until B is empty. As the last step you would 
have to connect the first and the last point.

And if the points on the boundary of the polygon aren't even dense but you 
have only a few points, you can connect each one to every other one - form 
a 'clique' in graph theoretic terms - and try to find the shortest path 
that visits each point expect for the first exactly once and the first 
twice. Such a path is called a hamilton path (and the graph is called 
hamiltonian) and it is computationally intensive to find. It can still 
happen that this scheme finds a polygon that you don't expect, but at least 
it won't intersect with itself.

There may be other suitable methods for your problem, but you have to 
specify it in more detail to find them.


Hope that helps,
  Benjamin


> Hello Benjamin,
> 		Thanks for the reply. Sorry that I did not explain the
> problem completely. The cross section whose perimeter I am trying to
> determine may not be circle always. I doubt I can use the method you
> mentioned for irregular cross section (for instance, consider a bean
> shaped c/s). Please let me have your views.
>
> Thanks
> Shyam
>
> -----Original Message-----
> From: vtkusers-admin at vtk.org [mailto:vtkusers-admin at vtk.org] On Behalf
> Of Benjamin King
> Sent: Tuesday, October 14, 2003 3:01 PM
> To: Shyam Prakash; vtkusers at vtk.org
> Subject: Re: [vtkusers] (no subject)
>
> Hello Shyam,
>
> I'm not sure if there is a direct solution in VTK, but you could first
> find another point c inside the circle (i.e. the mean of all the points 
> or
> just the point at the top) and then build an array that associates each
> pointid i with the angle of the line between c and i. If you sort that 
> array by
> the angle values, you get a suitable sequence of point ids. This is also 
> a resonably fast way to do this because the time for the sort (O(n log n))
>
> will always dominate the time for creating the array (O(n)). And you
> won't get away without sorting.
> You could also use any convex hull algorithm, but I don't think vtkHull 
> will do.
>
> Hope it helps,
> Benjamin
>
>> Hi,
>> My output polydata represents a circle. The point ids on
>> this poly data are distributed randomly(please refer the attached
>> image). Is it possible to get the ordered points (for example if I
> start
>> with point id 0, then the preferred enumeration order will be
>> 0 - 1 - 2 - 4 - 6 - 9 - 10 - 11 - 8 - 7 - 5 - 3 or in the
> anticlockwise
>> direction.
>> The basic idea is to find the perimeter of the circle (i.e by
> measuring
>> the distance between set of points and finally adding all the
> individual
>> distances) . For this I need the points in the order of appearance.
> Can
>> you please suggest a way to achieve this.
>> Thanks
>> Shyam
>>
>
>
>



-- 
Benjamin King
Institut für Medizinische Informatik
Medizinische Hochschule Hannover
Tel.: +49  511  532-2663