Home > Archive > Matlab > March 2007 > closest polygon segment to points
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
closest polygon segment to points
|
|
| Darren 2007-03-30, 8:11 am |
| Just wondering if anyone has a good method for this one...
You have a bunch of points in a 2D plane and for each point you would
like to find the closest wall segement in a (non-convex) polygon.
A brute-force solution is to loop through each point and for each
point to loop through every wall in the polygon, find the normal
distance between point and polygon and save the minimum as you go.
If you have N points and M walls this is an O(M*N) operation - not
good.
I know that the fast marching method is a good choice for
constructing the distance function (approximately) but I'm more
interested in finding the closest wall segment specifically.
The point cloud is also scattered (in this case).
Darren
| |
| John D'Errico 2007-03-30, 8:11 am |
| Darren wrote:
>
>
> Just wondering if anyone has a good method for this one...
>
> You have a bunch of points in a 2D plane and for each point you
> would
> like to find the closest wall segement in a (non-convex) polygon.
>
> A brute-force solution is to loop through each point and for each
> point to loop through every wall in the polygon, find the normal
> distance between point and polygon and save the minimum as you go.
>
> If you have N points and M walls this is an O(M*N) operation - not
> good.
>
> I know that the fast marching method is a good choice for
> constructing the distance function (approximately) but I'm more
> interested in finding the closest wall segment specifically.
>
> The point cloud is also scattered (in this case).
>
> Darren
Hi Darren,
I wrote a 3-d solver once for a
general non-convex object. I used
the circum-circles for faces of the
3-d polyhedron to discard faces that
I knew were farther away than the
closest point I'd found so far.
I was working with points outside
the polyhedron, so most of the time
I'd be able to avoid testing a large
fraction of the facets. If your
points lie inside the polygon, the
worst case would then be one where
the point lies near the centroid of
an almost convex polygon.
HTH,
John
| |
| Nasser Abbasi 2007-03-30, 8:11 am |
|
"Darren" <d_engwirda@hotmail.com> wrote in message
news:ef52ae5.-1@webcrossing.raydaftYaTP...
> Just wondering if anyone has a good method for this one...
>
> You have a bunch of points in a 2D plane and for each point you would
> like to find the closest wall segement in a (non-convex) polygon.
>
> A brute-force solution is to loop through each point and for each
> point to loop through every wall in the polygon, find the normal
> distance between point and polygon and save the minimum as you go.
>
> If you have N points and M walls this is an O(M*N) operation - not
> good.
>
> I know that the fast marching method is a good choice for
> constructing the distance function (approximately) but I'm more
> interested in finding the closest wall segment specifically.
>
> The point cloud is also scattered (in this case).
>
> Darren
Do not know what fast marching method does. But as an approximation, how
about first find the "center of mass" of the bunch of point.
Then find the closest wall to this center point.
On average, this wall, and walls in the neighborhood of this wall, will be
the closest to more points in the cloud than any other walls, So, may be you
can take advantage of this by speeding up your search.
Nasser
| |
| Damian Sheehy 2007-03-30, 7:11 pm |
| Hi Darren,
If I understand your problem correctly you have a non-convex polygon and
a set of test points in the 2D plane. For each test point you would like to
find the closest edge of the polygon.
As it turns out there is an elegant way to solve this problem, but
unfortunately it is not available in MATLAB. The best solution is to compute
the voronoi diagram of the polygon (not to be  with voronoi diagram
of the point set) . This geometric construct is similar to the medial axis;
the medial axis being a subset of the voronoi diagram.
The following image illustrates the voronoi diagram of a rectangle.
http://www.cs.jhu.edu/~jcorso/r/deformat/
It partitions the polygon into 4 territories; the voronoi regions. Locating
the edge that is closest to a test point reduces to locating the voronoi
region that contains the point.
In practice, you can approximate the voronoi regions using a constrained
Delaunay triangulation of a set of points that are sampled from the polygon
boundary. The voronoi region containing the point could then be computed
from a triangle location walk (similar to tsearch). Unfortunately, a
constrained Delaunay is not currently available in MATLAB either.
So, what to do. . .
If an approximation is an acceptable solution for your algorithm, you may be
able to get away with using an unconstrained Delaunay (the one in MATLAB) if
you have dense sampling of points on the boundary of the polygon. Otherwise
you may be able to source a constrained Delaunay and mex the file.
As an experiment, you may wish to compute the voronoi and Delaunay of a
point set sampled from a rectangle, display them together and you will begin
to understand how you can leverage this technique.
If you wish to follow either of these approaches you will need to do some
further research, Google will generate many sources.
I will track an enhancement request for this feature in MATLAB.
Damian
"Darren" <d_engwirda@hotmail.com> wrote in message
news:ef52ae5.-1@webcrossing.raydaftYaTP...
> Just wondering if anyone has a good method for this one...
>
> You have a bunch of points in a 2D plane and for each point you would
> like to find the closest wall segement in a (non-convex) polygon.
>
> A brute-force solution is to loop through each point and for each
> point to loop through every wall in the polygon, find the normal
> distance between point and polygon and save the minimum as you go.
>
> If you have N points and M walls this is an O(M*N) operation - not
> good.
>
> I know that the fast marching method is a good choice for
> constructing the distance function (approximately) but I'm more
> interested in finding the closest wall segment specifically.
>
> The point cloud is also scattered (in this case).
>
> Darren
| |
| Darren 2007-03-30, 7:11 pm |
| Thanks guys,
I've been thinking about voronoi diagrams with this for a while, so
I'll pursue it a little further and see where it goes.
It would be great if matlab supported cdt's (constrained delaunay
triangulations) at least in 2d/3d. I've been thinking for a while now
of coding the divide-and-conquer algorithm as a C-mex file (which can
be made cdt), but hey, life is short...
Just out of interest, you can get "almost" cdt's out of qhull in alot
of cases by first forming the unconstrained triangulation and then
doing a point-in-polygon test on the centroids and throwing away
those that don't lie within the domain. A few important cases where
this won't work though...
Darren
|
|
|
|
|