Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Efficient algorithm needed for closest value evaulation...

Subject: Efficient algorithm needed for closest value evaulation...

From: Ian Cowley

Date: 14 Oct, 2002 12:24:57

Message: 1 of 2

This is more of a maths issue than a Matlab issue, but here goes.

We have a rectangular space, the long sides of which can be modulated by
moving bars to make the space non-rectangular: (fixed-width font required
for 'drawing')

__________________________________
| |
| |
| __ ___ |
| __ __| |__| | |
| | | __ __| | | | | |
|___| |__| |__| | | | | |____|

We have two nx1 arrays specifying the vertical positions of the bottom and
top bars (I've only drawn the lowers ones here), and need an algorithm for
the following.
When an x,y coordinate (x and y being somewhere in the whole rectangle) is
passed, we need to calculate the distance to the nearest edge of a bar, be
it the side or top of that bar. We only need the distance to the nearest
edge, not the direction or the bar number.

At present we have a very time-consuming for next loop across all the bars,
but we're sure there must be an easier way. None of us here are versed in
MATLAB enough to vectorize our code, and are hoping that someone may have a
solution for us.

Many thanks
--
Ian Cowley
ian at iancowley dot co dot uk
Cambridge, UK

Subject: Efficient algorithm needed for closest value evaulation...

From: John D'Errico

Date: 14 Oct, 2002 08:55:33

Message: 2 of 2

In article <aoe9hs$c1c$1@pegasus.csx.cam.ac.uk>, "Ian Cowley"
<null@null.null> wrote:

> This is more of a maths issue than a Matlab issue, but here goes.
>
> We have a rectangular space, the long sides of which can be modulated by
> moving bars to make the space non-rectangular: (fixed-width font required
> for 'drawing')
>
> __________________________________
> | |
> | |
> | __ ___ |
> | __ __| |__| | |
> | | | __ __| | | | | |
> |___| |__| |__| | | | | |____|
>
> We have two nx1 arrays specifying the vertical positions of the bottom
> and
> top bars (I've only drawn the lowers ones here), and need an algorithm
> for
> the following.
> When an x,y coordinate (x and y being somewhere in the whole rectangle)
> is
> passed, we need to calculate the distance to the nearest edge of a bar,
> be
> it the side or top of that bar. We only need the distance to the nearest
> edge, not the direction or the bar number.
>
> At present we have a very time-consuming for next loop across all the
> bars,
> but we're sure there must be an easier way. None of us here are versed
> in
> MATLAB enough to vectorize our code, and are hoping that someone may have
> a
> solution for us.

Assuming that you will need to do this for many
points, it will be worth your while to do some
pre-processing.

Create a set of polygons, akin to Voronoi polygons,
such that any point inside a given polygon is
closer to a specific bar than to any other bar.
You only do this once, so it need not be highly
vectorized.

Having done that, its simply a quick call to the
function inpolygon to determine which bar a point
is associated with. You will still need to loop
over the distinct polygons, but inpolygon is
quite fast, and it is possible to pass in all of
your points to inpolygon at once.

HTH,
John D'Errico

--

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us