2

I'm trying to implement LOGO with a physical turtle. I got all the basics done, but I got completely sunk when implementing the "Window" mode.

Original LOGO had 3 modes: "Border" - the turtle bumps into border of the screen and stops there, "Wrap" - the screen is a torus, turtle rides out the left side of the screen, reappears directly right from the exit point, and "Window" - the turtle can travel over enormous playfield stretching far outside the borders of the screen, and whatever happens off-screen is simply never drawn. It was the favored mode as it wouldn't spoil the drawn part if the picture exceeded past the screen borders.

Now, I got to the point where the 'forward' command can generate carthesian start and end coordinates of any move. In 'Window' mode they may happen anywhere, on screen or off screen. If they happen on screen, the turtle normally moves along the line from start to end. If they exit, the turtle drives up to the border, while virtual 'cursor' continues to the end coord. If they both occur off-screen nothing happens physically, just the 'cursor' is moved in memory. If they re-enter the screen, the turtle is moved from wherever it was to the entry point without drawing, then proceeds to the end point, drawing or not depending on pen settings.

This all happens with floating point maths, so numbers are never exact - I've set an 'epsilon' of 0.0001mm of tolerance, anything closer should be considered a match.

I have methods for:

- is_outside_eps(point) # more than epsilon from border - is_outside(point) # just floating point comparison, no epsilon tolerance - is_at_border(point) # within epsilon from border - go(startpoint,endpoint) # perform normal turtle movement, using pen settings - nodraw(startpoint,endpoint) # move the turtle from startpoint to endpoint, no drawing - dummymove(startpoint,endpoint) #move the cursor from startpoint to endpoint, no physical results - find_intersects(startpoint,endpoint)

...and a number of derived helpers. If more is needed, more will be written.

find_intersects returns a list of coords where the vector start->end crosses any borders, alongside with direction (1 = into, -1 = out of). It can return two entry points or two exits if the vector passes through a corner, though this isn't a problem - they are in the same spot, so one can be ignored safely.

Where I got stumped is all the edge conditions. I found 16 so far, and I really, really hope this can be simplified, and I don't have to cover all the combinations:

all possible edge conditions

For example, a turtle at the border, when told to move directly outside, should stay put, only the virtual cursor moved. But the same turtle told to turn towards center of the drawing area and move 1000 units forward (way outside the drawing area on the opposite side) should cross over to the opposite border and stop there while the cursor continues.

Is there some smart way to handle that, or am I sentenced to writing at least 16 different cases for handling all the possible situations?

Improve this question
3
  • Some community trolls here seem to downvote every question, regardless if its a good one or bad one. Come one, this is a focussed and well written question for a specific problem, clearly on-topic, shows own research and clearly answerable. What more do you want? Commented Sep 11, 2023 at 19:14
  • 1
    A physical turtle sounds like an actual 🐢 animal. Maybe it might help to add a small half sentence upfront explaining the niche you’re likely talking about. In the absence of more keywords I think it might help readers. Commented Sep 13, 2023 at 3:25
  • @AdamB Sorry, I forgot most of population nowadays doesn't know about the turtle that was used with LOGO (and somewhat famous) back in the day. Commented Sep 13, 2023 at 8:48

3 Answers 3

Reset to default
3

The way I would approach this problem is to start with the cursor movements alone. For this step, one does not need to take the screen rectangle or the physical turtle into account, it is just a an unbounded vector calculation in memory (one only has to care for overflows / underflows in regards to the maximum range of the chosen floating point datatype).

Then, let us look at the line segment L between two cursor endpoints produced by the latest move command.

Apply a standard rectangle clipping algorithm, typically Cohen-Sutherland, to cut L to the screen rectangle:

  • when L is completely outside the screen, there is nothing more to do.

  • when L touches the screen, Cohen-Sutherland gives you the clipped line L' with two endpoints A and B, which might be inside the screen or at it's border.

Now, you move the turtle from the current position to A, without drawing, and then to B, drawing a line with the current settings. This shouldn't require any special treatment for edge cases. It should work

  • regardless of A and B being equal or different,
  • regardless of A being identical to the current turtle position (or not), and
  • regardless of L' being completely at the screens border or being inside.

Note also this approach does not require any artificial tolerance to be introduced, since neither Cohen-Sutherland nor the turtle movements require any tests for equality, only "smaller" and "greater" comparisons.

Improve this answer
1

This is a solved problem. There's a whole literature on it.

The OpenCV call you're looking for is

 assert len(p1) == len(p2) == 2 rect = (0, 0, width, height) ret, p1, p2 = cv2.clipLine(rect, p1, p2) if ret: ... # the point(s) were clipped to fit the viewport rectangle

I invite you to post the code you finally settle on.

Improve this answer
3
  • You missed the "physical turtle" part, didn't you? :) My precision is about 0.01mm while working on an almost 300x300x400mm volume. And it's not even clipped down to integers, min_z=0.2 Commented Sep 11, 2023 at 19:49
  • Sorry. I misinterpreted "physical" to mean "the outline of a turtle displayed at border of viewport", in contrast to a cursor that can go anywhere. I thought that 53-bit significand would dominate the errors, but it turns out that repeatability of sending a physical turtle here or there will offer the biggest errors. I also didn't get the "40 cm high" aspect. Maybe this question is more about printing objects than about drawings from 2D turtles? That field has its own literature. Commented Sep 11, 2023 at 19:56
  • J_H I'm writing 3D LOGO for a 3D Printer. The nozzle is the turtle. Extrusion is drawing. The printer operates in absolute cartesian coords, so conversion from turtle motion to cartesian is my work. But this being a 3D problem is mostly irrelevant, only different clipping algorithms, the core of the problem is the same. Commented Sep 11, 2023 at 20:12
0

I decided to trust my intersection finding function much more, ignore the situation "at border" (conflating it with "inside", scratching the exact match, renaming is_inside_eps to is_inside) and it allowed me to reduce the amount of cases massively.

def windowed_move(start, end) # first handle standard move if is_inside(start) and is_inside(end): go(end) else # handle intersections in_point, out_point = find_isects(start,end) # If there's an entry point, move there if in_point is not None: nodraw(in_point) # If there's an exit point, draw up to it if out_point is not None: go(out_point) # If the end is inside, draw up to it. elif is_inside(end): go(end) # else do nothing: there's no exit and end is outside # Regardless of everything else, move the cursor to the endpoint dummymove(end)
Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.