3

Given an already defined path p in Metapost/Metafont: How can I determine whether a segment like subpath (0,1) of p is a line? I am aware that I can simply check if the control points lie on the line (e.g. with the crossproduct of the vectors from the control points to the end points). But is there a more straight forward way to do so (like a command straight(p))?

4
  • Rotate the path such that begin and endpoint line up parallel to the x-axis. Then check that the bounding box has zero height (or maybe height of the linewidth?). Commented Jan 28, 2023 at 20:27
  • @HenriMenke I am pretty sure that this is slower than using cross products. I was looking for a solution that is kind of already predefined in Metapost. Commented Jan 29, 2023 at 21:28
  • 1
    I don't see how rotate + bbox will be slower than checking the control points for each an every segement in the path. Granted, if the path whose straightness you want to check is only a single segment that might be true. If you are looking for something builtin to MetaPost, then the answer to your question is simply “No”. Commented Jan 30, 2023 at 11:57
  • @HenriMenke Yes, I was asking for a single segment only. I agree that your solution is generally faster for paths made of several segments. Indeed, I was looking for something built in to Metapost. I will accept your "No" as the answer to my question when you add it as answer instead of a comment. Commented Jan 30, 2023 at 12:10

1 Answer 1

6

Here's one I did earlier, based on the area test.

vardef twice_area(expr a, b, c) = 
    (xpart b-xpart a)*(ypart c-ypart a) - (ypart b-ypart a)*(xpart c-xpart a)
enddef;

vardef collinear(expr a, b, c) = if abs(twice_area(a,b,c)) < 1.6 eps: true else: false fi enddef;

vardef straight(expr p) = (collinear(point 0 of p, postcontrol 0 of p, precontrol 1 of p)
                       and collinear(postcontrol 0 of p, precontrol 1 of p, point 1 of p)) enddef;

but this is not very robust because the determinant calculation is a bit ill-conditioned and with the default scaled number system will often give numbers slightly bigger than zero, especially for straight lines that are not horizontal or vertical. It can also over flow easily with values longer than about 64bp.

That may not be so much of a problem in Metafont where the sizes of your characters are normally fairly small, but it is a nuisance in Metapost, where sizes are usually bigger. So here is a rather simpler, and better straight macro, for Metapost.

vardef straight(expr p) = arclength p - length (point length p of p - point 0 of p) < eps enddef;

This compares the length of the given path to the length of the straight line between the first and last points of the path. In my (admittedly limited) testing this seems to be reasonably general and robust. But I would welcome feedback or improvements.

Notes

  • arclength p returns the length -- in PostScript points -- of the given path p. This is a Metapost-only command.

  • length p returns the length of the given path p in MP's notion of time, so for example fullcircle has length 8 and unitsquare has length 4.

  • point 0 of p gives you the first point of the path p

  • point length p of p gives you the last point of the path (even if the path is a cycle).

  • (point length p of p - point 0 of p) returns a pair that represents the vector between the start and end of your path.

  • length <pair> returns the length in Postscript points of the vector represented by the <pair>

So length (point length p of p - point 0 of p) must always be less than or equal to arclength p. Allowing for a little rounding, we can say that p is straight if

arclength p - length (point length p of p - point 0 of p) < eps

The quantity eps is defined in plain.mp to be 0.00049.

The two different meanings of length are perhaps unfortunate, but not that hard to manage in practice.

  • length <path> returns length in "time"
  • arclength <path> returns the length in Postscript points
  • length <pair> returns the length in Postscript points of the vector represented by <pair>

Finally note that because a <path> in MP can consist of a single point, you will find that the macro as defined above thinks that a single point is a straight path. So (for example):

show straight(origin);

will put

>> true

in your log file.

3
  • Your "area suggestion" is my already mentioned "cross product suggestion". If you norm the vectors to unitvectors before applying the cross product you will have no arithmetic overflow and actually calculate the sinus of the angle between the vectors. I think it's rather robust. I agree, that some tolerance must bei given due to the number system in Metapost. The arclength idea is interesting. However: It is probably slower than our other solution. Hence, when I would implement an own solution, I would rather use that. Commented Jan 29, 2023 at 21:24
  • I have not timed it, but I doubt that a macro with calculations (not to mention unitvector and sind) is faster than arclength. It would be interesting to do some performance tests.
    – Thruston
    Commented Jan 29, 2023 at 22:34
  • unitvector has to be calculated only twice for a segment and the ++ operation is quite optimized afaik, whereas arclength relies on a numerical integral. sind is not needed with the cross product, I just wanted to point out the connection u × v = |u| |v| sin(ϑ). Of course, a performance test would show the tendencies but may depend on the number of straight segments to be expected (arclength is recursive and therefore probably faster for straight paths). Commented Jan 30, 2023 at 12:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .