On 25 Apr., 01:08, Barb Knox <s...@[EMAIL PROTECTED]
> wrote:
> In article
> <9130961.1209046212624.JavaMail.jaka...@[EMAIL PROTECTED]
>,
>
> misty <luthie...@[EMAIL PROTECTED]
> wrote:
> > hi,
> > i've got such a problem. imagine a curve-partly linear, partly
non-linear. it
> > can be for example part of a circle like ')' or like '(' or like 'U'.
> > what i need is to write fully automatic algorithm that will find left
and
> > right end-points of the curve. as You can see i cannot do for ex. find
min(x)
> > and then find y where x is min. it will be good for ')', but what if
the
> > curve is like '('.
> > also my points are not in order, i mean that x(1), y(1) is not the
left
> > end-point of the curve and x(end), y(end) is not the right end-point.
>
> > can anyone suggest me something?
>
> I suggest that the problem as stated, with an unordered set of points,
> has no solution.
>
> Consider the following 4 points (use a monospaced font):
> * *
>
> * *
>
> They could represent several *different* connected curves, such as:
> *---* * *
> | or | |
> *---* *---*
>
Even though the OP may be interested in discretised pixel curves,
the counter example can in fact be adapted to "true" curves
as the end points of a space filling curve cannot be determined from
only knowing the graph of the curve.
A good idea for an approximate/appropriate solution to the OP problem
might be to consider the graph having all points of the curve as
vertices
and connect these by an edge iff they are adjacent horizontally or
vertically (or diagonally?) and then look for a shortest path between
tow vertices that visits each vertex at least once.
I don't have a good algorithm for that problem either, but a good
idea for a start would be to look for two vertices with maximal
distance
(within the graph, using Floyd-Warshall). In fact, for not-too-weird
curves
this will usually produce the intended solution immediately.
This might even produce useful hints for "thick curves" (e.g. from
a scanner image). But OTOH, it fails with shapes like this (fixed
font):
* *****
* *
* *****
hagman
|
