 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Math Forum / Mathematics / Undergraduate Math / April 2008end points of a curve
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? In article <9130961.1209046212624.JavaMail.jakarta@nitrogen.mathforum.org>, > hi, > i've got such a problem. imagine a curve-partly linear, partly non-linear. it [quoted text clipped - 7 lines] > > 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 | | *---* *---*  Signature--------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | Quidquid latine dictum sit, | B B a a r b b | altum viditur. | BBB aa a r bbb | ----------------------------- yes, i'm very close to become convinced that this problem is unsolved. thanks anyway for replying! kind regards! > In article > <9130961.1209046212624.JavaMail.jaka...@nitrogen.mathforum.org>, [quoted text clipped - 23 lines] > | 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 |
Reply to this Message |
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2010 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.