Prev: The trim function and it's intented purpose?
Next: CHR 2010: Final call for papers
From: mike3 on 28 Mar 2010 23:32
Hi.

I've got an interesting problem here.

(use fixed width font to view this)

Consider the following:
..............
..............
.....1........
..............
...3...2......
..............
..............
..............
..............

We have 3 points, stored so an increment of the number means to go to
the next nearest point in such a manner a clockwise loop is formed.
Now suppose we wanted to add to this list another point:
..............
..............
.....1........
..............
...3...2......
.....X........
..............
..............
..............

This turns it into:
..............
..............
.....1........
..............
...4...2......
.....3........
..............
..............
..............


If we try something like this, however, it has to fail:
..............
..............
....1.2.......
..............
....4.3.......
..............
..............
..............
..............

Bad:
..............
..............
....1.2.......
.....X........
....4.3.......
..............
..............
..............
..............

since we can't run clockwise (or counterclockwise) around those points
in a loop connecting nearest to nearest without revisiting the point
X.

How can one keep a list like this?







From: mike3 on 28 Mar 2010 23:41
Hmm. Now that I read some more, it looks like this may be equivalent
to a
"traveling salesman problem" which has no efficient solution (or is
*believed* to
have none, anyway, as there's no proof yet that P=NP or P!=NP.).
Mmm.....
From: Richard Heathfield on 29 Mar 2010 04:02
mike3 wrote:
> Hi.
>
> I've got an interesting problem here.
>
> (use fixed width font to view this)
>
> Consider the following:
> ..............
> ..............
> .....1........
> ..............
> ...3...2......
> ..............
> ..............
> ..............
> ..............
>
> We have 3 points, stored so an increment of the number means to go to
> the next nearest point in such a manner a clockwise loop is formed.
> Now suppose we wanted to add to this list another point:
> ..............
> ..............
> .....1........
> ..............
> ...3...2......
> .....X........
> ..............
> ..............
> ..............
>
> This turns it into:
> ..............
> ..............
> .....1........
> ..............
> ...4...2......
> .....3........

....which fails, since you will connect 1 and 2, and then 2 and 3, and
then 3 and 4, and then 4 and 3 rather than 4 and 1 (3 is nearer than 1).
It is not clear why you think this is valid input. I know you want to go
clockwise, but let's consider your next example:

> If we try something like this, however, it has to fail:
> ..............
> ..............
> ....1.2.......
> ..............
> ....4.3.......
> ..............
> ..............
> ..............
> ..............
>
> Bad:
> ..............
> ..............
> ....1.2.......
> .....X........
> ....4.3.......

Why? Why not just connect to the nearest *unattached* point, reserving 1
for last?

1 -> 2
2 -> X
X -> 3
3 -> 4
4 -> 1 (not to X, because X has already been used)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
From: cbcurl on 29 Mar 2010 13:54
On Mar 28, 11:32 pm, mike3 <mike4...(a)yahoo.com> wrote:
> Hi.
>
> I've got an interesting problem here.
>
> (use fixed width font to view this)
>
> Consider the following:
> .............
> .............
> ....1........
> .............
> ..3...2......
> .............
> .............
> .............
> .............
>
> We have 3 points, stored so an increment of the number means to go to
> the next nearest point in such a manner a clockwise loop is formed.
> Now suppose we wanted to add to this list another point:
> .............
> .............
> ....1........
> .............
> ..3...2......
> ....X........
> .............
> .............
> .............
>
> This turns it into:
> .............
> .............
> ....1........
> .............
> ..4...2......
> ....3........
> .............
> .............
> .............
>
> If we try something like this, however, it has to fail:
> .............
> .............
> ...1.2.......
> .............
> ...4.3.......
> .............
> .............
> .............
> .............
>
> Bad:
> .............
> .............
> ...1.2.......
> ....X........
> ...4.3.......
> .............
> .............
> .............
> .............
>
> since we can't run clockwise (or counterclockwise) around those points
> in a loop connecting nearest to nearest without revisiting the point
> X.
>
> How can one keep a list like this?

You might want to read up on the Graham scan algorithm for computing a
convex hull of a set of points.


From: mike3 on 29 Mar 2010 20:40
On Mar 29, 2:02 am, Richard Heathfield <r...(a)see.sig.invalid> wrote:
> mike3 wrote:
<snp>
> Why? Why not just connect to the nearest *unattached* point, reserving 1
> for last?
>

Yes. I should've mentioned that obvious qualifier.
 |  Next  |  Last
Pages: 1 2
Prev: The trim function and it's intented purpose?
Next: CHR 2010: Final call for papers