Ruby: how to use self.included meaningfully

The problem

My use case was to provide the same functionality on instance and class level upon include. By default include only adds instance methods and extend only adds class methods. Of course you could do both but that just doesn’t look DRY…

… right? It is especially ugly to give the instructions to the users of your module to do both.

A common idiom

Looking for the solution I stumbled upon self.included mentioned as “A common idiom” for this case. As per ruby-doc it is a “Callback invoked whenever the receiver is included in another module or class”.

Messing around with it you can do the following:

Which will create class_method in the class where it’s included. Or to fit my use case and add all methods as class methods:

Which will do an extend as well upon include.

There’s also a similar callback for extend by the by way: self.extended.

How to make it better

So we have a solution but is it the best one? The first time it took me a while to figure out how it works. Callbacks of this kind are bad in the sense that they describe when they will be executed and NOT what they will do. I wish we could rename the callback to CreateClassMethodsUponInclude but unfortunately that’s not possible.

So let’s do almost that! We know that it has a fixed name and must be in a module. The module of course can have a custom name and can later be included wherever we want to have this logic. That’s great! We can have something like this:

Well that’s pretty descriptive. OK. But what should happen when we include CreateClassMethodsUponInclude? It should create the self.included that does what we want. We can achieve that using some more meta-magic.

Go ahead and copy it into your console. While it works you may think that it’s uglier than what we started with. So..

What did we gain?

The actual implementation may be ugly but no one has to look at it again because we wrapped it into a module that is meaningful and reusable. Using the CreateClassMethodsUponInclude module no-one will have any excessive thinking to do while reading or writing this piece of logic.

This module is part of the free and public reflection-utils gem. While it’s only one actual use case I think this design pattern is worth following for similar problems.

Hacking minesweeper with Cheat Engine

Guest post by a security enthusiast friend.

Several years ago I got an idea to learn how can I use Cheat Engine to make “cheats” or “hacks” to games. The simplest game I knew was the famous Windows game Minesweeper. This article is a tutorial about how to make a simple program to show where are the mines on the field.

Tools NEEDED

To write a program to display some (hidden) data from a game’s memory we have to know where exactly is the desired data in the memory. In our case this means we have to know the address of the minefield and the address of the size too. This is where Cheat Engine comes into play. It is an open source tool with so many great features. We only (have to) use 2-3 of these.

Then if we have those addresses, we need to write a program to read from the game’s memory and display it. Back then when I didn’t know many programming languages I used C++ and WinAPI functions like ReadProcessMemory. Now when I’m writing this post I want to use Python, so we will use the ctypes library to read that data. This will work exactly the same as my old C++ solution, but you know it’s python.

LEt’s GO dIg (in the memory)!

First fire up our game and Cheat Engine. Click on the shiny computer picture then open the game.

1

Okay, now we want to find the size of the minefield in the memory. It’s easy because we know the exact value and we can just search for it. To do this we start a game with a 9 by 9 field, then we search for the value 9. This show us a lot of addresses where the value 9 is presented, but don’t worry we can narrow this list by changing the field size to 16 then hit ‘next search’. This will only show the values that was in the previous list AND their value is 16 now. If we the board to 16 by 30, we can see these values change too.

Great! Next step is to get the board’s address. It will be a bit tricky because we don’t know the exact value of any of the field. We can use some advanced search like selecting ‘Unknown initial value’ then a ‘Value changed/unchanged’ search. Spoiler alert: it takes a lot of time!

The funny thing is when we click the ‘Memory View’ button we arrive into that part of memory we are looking for :). But there is a way to find this without luck too! With the ‘Graphical memory view’ feature we can visually detect where is the memory changing at new game starts. This is because the minefield is re-generated with every restart.

With some messing around with field sizes we can see that the field is stored row continuously as a 30 by 30 matrix. This means that if we play on a 9 by 9 field the memory looks like this: 9 values representing a row then (30-9) unused space then the next row and so on. For example, the 30 by 30 (the biggest playable) field fills up this whole space without unused spaces. Because of this we don’t even have to know the size of the field, we can print out the whole 30*30 values, but it’s not a pretty solution and we are here to practice.

final step

The only thing left is write a program to read and display where are the mines in the memory. My example program is avaible here. I think It’s easily understandable, so I don’t want to write much more about it.

Conclusion

We managed to write a hack to a popular game thanks to Cheat Engine!

Next time we will try something more complicated!

3 ways Amazon fails to fight scammers. Years old scam is on the rise, now worse than ever

So last day I also run into one of the many scams out there, this time on Amazon. Things felt off from the beginning but as I’m not an experienced user of Amazon’s webshop it took some time to verify it. Unfortunately what used to be riddled with typos and strange sings is now a new industry perfecting their product just like everyone else. And it’s good. I mean bad.

I thought ‘hey, since this bullshit took some time already maybe I can turn it into something useful’. So I started looking into it more deeply and anything I found just pissed me off even more. Just by looking at the sheer amount of unashamed scams I thought this is somewhat new and by bringing attention to it things can change for the better. Well, it turns out I was wrong. This has been out there for a long while and now it’s more dangerous than ever! With that in mind I did something Amazon have yet to do in this case. I adapted to the situation. Let me assure you now, this will not be one of those story telling posts. Instead I will categorically point out what Amazon fails to do or fails to do correctly to stop these scammers.

With this essay I hope to bring light to not only the problem but the (missing) solution.

#1 their game, their rules. bad ones.

First off, lets’s start with that this scam takes place (or at least starts) on the site. I understand that other scams over the phone or via mail are harder to keep in control, but that is not the case here. As explained in this post from early 2015 there are used items listed in the shop usually around half the normal price from brand new sellers asking to contact them via email before making a purchase on the site. What I came across was old accounts sometimes even with good rating selling fraudulently several thousand new items below price with the same condition (pictures #1 and #2).

Regardless whether these are new accounts, old ones or hacked ones, whether they slipped through the review, there’s a clear pattern of selling cheap stuff and giving instructions to email them in a very specific location in every case that I saw.

Remember, this is their house. They may impose any criteria or supervision. The rightful question arises: are they even trying hard enough? And let’s not forget that we’re talking about Amazon, the company famous and proud of their solutions to automate otherwise manual tasks.

#2 scammers are not followed through

Remember that I mentioned thousand of listed fraudulent items? I’ll add that since the one day I’ve been paying attention I’ve seen several of these companies come and go. This lets me conclude that it’s a systematic, automated process. It’s more than likely that the people operating these shops don’t even care if one goes down. It probably takes only a couple minutes to set up a new one.

There are however resources that are limited. One of those is a legit-looking email address. I’ve been blessed with outstanding ones like ‘payment@orders-amazon.co.uk’ or ‘amazon@confirmation-amazon.co.uk’ which align with the company and the email content perfectly. Seriously, even anticipating spam I thought that it’s legit for a second. Sure, confirmation@amazon.co.uk or something like that, looks OK.

And speaking of spam here’s the big issue: non of the 4 email addresses they used were flagged as spam (by google at least).

This gives me the feeling that finding and removing such a company is the end of the story. It’s obvious that in order to prevent future scams Amazon should follow-up on these issues, message the seller, find out as much as they can and shut down as much as they can. Instead these shops actually don’t disappear but only their products are removed. Afterwards I wasn’t notified (as someone who had one of their items in my basket therefore likely sent an email to them), even though it might be not too late to save me from giving my money away to criminals.

Keeping that in mind I’ll go one step further in guessing… If I were the seller being able to set up shop by a click of a button I wouldn’t even wait for Amazon to find me. I’d just go online, gather a few candidates who email me and then remove the shop before anyone could even report it and put it up under a different name the next day. This would allow to preserve my scheme and valuable resources (like email addresses) longer. From the looks of it I can very well imagine that this is the case.

#3 community efforts not supported

The above points may require Amazon to introduce changes and invest efforts. Here’s something on the other hand that would have minimal cost and would significantly improve the situation: give means to the community to take action.

But that is not the case, instead even if you successfully identified a scam you have to go through ridiculous efforts to even try to take action – no results guaranteed. Let me walk you trough it step-by-step:

  1. Go to the ‘Seller Profile’ / ‘Detailed Seller Information’ / ‘Seller Storefront’ pages and look for a possibility to report. None found. The story should really end here. Three clicks at most (report seller -> choose scammer option -> send).
  2. Google ‘amazon report scam‘ to find
    • their support page about scams and phishing. Here you can find no mention of this common scamming practice, but information that is outdated (like weak email address example: ‘amazon-fraud@msn.com’) or just simply useless (like a link at the bottom ‘reporting a phishing or spoofed email’ pointing to the home of the help page where there’s no mention about any of those).
    • page about reporting emails or violation report page where again you can only report emails or a violation on existing order.
    • that it seems Amazon doesn’t even acknowledge the problem. To be able to create a proper report you have to be directly involved with the scammers (via a purchase or email), which is exactly what we all want to avoid.
  3. Finally if you search and read relentlessly you will find articles and forum discussions (#1, #2, #3, #4,  #5, and many more, lots of them on Amazon buyer & seller forums actually). There you will find a possible solution: make a phone call. Yeah, we all love customer service. This is most definitely not what you had in mind when you wanted to help (at this point likely a couple hours ago). And then we have testimonials where people are being sent off with lines like: “All of our Amazon marketplace sellers are genuine so you don’t have anything to worry about”.

so what can i do?

Well, if you have the time you can call them every time. That’s good but it’s no long-term solution. What you should do is raise attention to this issue so that Amazon might actually start to care.

Share this post, share others’ posts, comment on Amazon forums, create new ones, create tickets. Let them know that this is an issue you care about as well – even if you’re not a victim.

And as always, educate your family and friends. Encourage them to shop online but tell them what to do and what not to do.

As a proactive measure unfortunately there’s not much you can do. One possibility would be to keep the scammer occupied: engage in discussion and ask lots of questions. This is what members of the 419 Eater community do. The idea is that the scammers do not prey on other victims for the time being. But maybe they even mess up. I made them click on a redirect link that was recording data of visitors. Got an IP and an approximate location that may or may not belong to my scammer. Other than that you could only do the same as they’re doing: scam the scammer.

 

[Update 1 Dec 2016]

I was told to point out specifically that all ‘@xxxxxx-amazon.co.uk’ email addresses are fake. Here’s a picture of the very deceptive mail I’ve received from ‘payment@orders-amazon.co.uk’ and a more transparent one from ‘amazon@confirmation-amazon.co.uk’.

Also another testimonial on Amazon’s stand: “Last time I asked Amazon to check the seller because they were selling a product at 40% of the next lowest price, the rep told me that I would be protected by Amazon’s purchase protection, but refused to make a statement about or look into the seller.” Which means you are protected as long as you’re paying through Amazon and you’re willing to go through the hassle to recover your money of course. But if you happen to contact them via email or vice versa and get scammed that way you’re on your own. It also calls into question whether Amazon actually follows up on these issues.

Finding Catmull-Rom Spline and Line intersection. Part 2: Mathematical approach

As far as I can tell there’s no open-source solution out there for this problem to date. Maybe it’s trivial for those with significant mathetamical knowledge, but for those who are just starting to get familiar with the mathematical foundations of splines this problem may just seem too intimidating. As a result they might resort to a much worse solution they’re comfortable with. So did I at first.

So let this article be a guide for a solution. I will explain the math and also provide an implementation in Java using the libGDX library.

That said if you’re a least bit interested I’d recommend you trying to solve this for youself. All you need is some basic understanding of the Catmull-Rom Spline equation and the Line equation. As a hint I recommend reading this post. Though it actually contains a flaw it will put you on the right track.

catmull-rom formula

To determine a point on the Catmull-Rom Spline we need the 4 sorrounding control points (P0, P1, P2, P3 , predefined), a knot parameter (alpha, predefined) and a value in range of 0-1 (t) that will tell which point of the Spline we’ll get.

The formula can be written as:

q(t) = alpha * ((2*P1) + (-P0+P2) * t + (2*P0 – 5*P1 + 4*P2 – P3) * t^2 + (-P0 + 3*P1 – 3*P2 + P3) * t^3))

Which (if we disregard the predefined values) is a simple Cubic equation:

a*t^3 + b*t^2 + c*t + d = 0

Where

a = alpha*(-P0 + 3*P1 – 3*P2 + P3)

b = aplha*(2*P0 – 5*P1 + 4*P2 – P3)

c = alpha * (-P0+P2)

d = aplha * (2*P1)

Our points (P0-3) consist of two variables: the x and y coordinates. They’re independent so we can handle them seperately. Let’s say:

x = a1*t^3 + b1*t^2 + c1*t + d1

y = a2*t^3 + b2*t^2 + c2*t + d2

Where e.g. ‘a1’ is ‘a’ with the x coordinates substituted for each P point and ‘a2’ is ‘a’ with the y coordinates substituted for each P point and so on with b, c and d.

line FORMULA

Ax+By+C=0

Not much to see here, move along…

combined FORMULA

Substituting the values of x and y from the separated Spline formula into the Line formula we’ll get:

A*(a1*t^3 + b1*t^2 + c1*t + d1) + B*(a2*t^3 + b2*t^2 + c2*t + d2) + C = 0

Rearranged:

(A*a1 + B*a2)*t^3 + (A*b1 + B*b2)*t^2 + (A*c1 + B*c2)*t + (A*d1 + B*d2 + C) = 0

This is again a Cubic equation, combined from the Line’s and the Spline’s equation. If you solve this you can get up to 3 real roots for t.

You remember that t is ranged from 0 to 1, right? Choose those that fit, substitue them into the Spline formula we first talked about and you have the intersection point(s).

If none of them fits they don’t intersect. If more than one fits there’s more than one intersection (3 possible with a knot as seen on the uniform spline here). In case you only need one intersection point you should examine all possibilities and make a conscious decision (e.g. take first/last point on the Line/Spline) otherwise the outcome might be random.

multiple spans

The above solution is simplified to a Spline with 4 control points (1 span). What about Splines that has more spans?

You have to do the same calculation for all spans using their 4 sorrunding control points. Keep in mind that there may be intersections in every span.

implementation

The code (alongside with other Catmull-Rom utilities) is available on GitHub. The Span class takes care of the math, it takes values needed from the Line class’ interface. Finally, the Spline class’ intersect(Line) method will gather the results. There’s a desktop demo where you can try it for yourself.

Finding Catmull-Rom Spline and Line intersection. Part 1: Brute-force

This was an issue I tackled for a while and ended up with a pretty neat optimized solution – at least so I thought at the time. As it turns out it’s completely useless in light of the matchematical approach I later implemented. Still it was a pretty nice try and makes for a good story on how a programmer vs. a mathematician would approach a problem. At the end it seems like I’m both. Lucky me.

Anyway this line of thinking (pun not intended) may actually be useful in other cases where you’re left without a pure mathematical approach.

Brute-force 101

So the problem is given. Assuming you don’t want to take a deep-dive in equations you’re left with one choice. That one’s actually fairly straightforward.

Let’s take all points of your Line and cross-reference it with all points of your Spline and see if they have anything in common. Or at least within a certain margin of error. Being a smart developer you chose a library that has already a built-in way to iterate these objects. Your code might look something like this:

for (float l = 0f; l <= 1f; l+= precision ) {
    linePoint = line.valueAt(l);
    for (float s = 0f; s <= 1f; s += precision) {
        splinePoint = spline.valueAt(s);
        if (linePoint.dst(splinePoint) < delta) return splinePoint;
    }
}

Precision and delta should be chosen carefully. You’d probably want to chose delta first to set a maximum inaccuracy. Then you need to set the precision so that you can actually find the data you’re looking for. This may be much harder than it first seems especially considering how loose some libraries play with precision.

And there you have it: a very low-effort solution that can actually work just fine for you.

complexity cut

Well, it did not quite work for me. If you need to do this more than once, let alone continuously in real-time the above solution will really start to push it.

Time to get creative!

… but first of all you can’t really better anything if you can’t measure it. Assuming your  Line has L points and yor Spline has S the above solution yields a complexity of O(L*S). Simplifying it to a common precision (N) it’s O(N^2). Now even if you don’t know much about the order of algorithms you should know that anything with an exponent is bad.

Given that we’re brute-forcing (i.e. trying all possibilities) we can’t make our algorithm’s complexity independent from the object’s complexity. But maybe we can ignore some possibilities along the way.

X-flat spline

Here comes the idea: let’s construct our Spline in a way that it is continuous on one axis. My setting is vertical so I chose X.

This will enable us to simplify things a lot. Take a random point. Take the first and last point of your Spline. Just by looking at the X coordinates you can tell if that point has no chance at all of being on the Spline (i.e. it’s not between the Spline’s ends). If it does you still have check though but remember, we’re all about eliminating possibilities here. If your iteration allows it you can actually do the same thing with the Spline’s spans (parts between adjacent control points). At this point if your Spline has P control points you essentially saved (P-2)/(P-1)th of the work (that is, the most) not even counting points that are outside of the Spline’s reach ((e.g. if you have 6 control points which result in 5 spans and you identify the span you need to look at you saved looking at the other 4)).

By this point you might have realied that it’s possible to do a binary search on the Spline (or only  on 1 span) for the X coordinate. Once you found the Spline’s point that has the same X coordinate as your random point you check the Y as well for the final verdict. And that actually only takes O(log(S)) time which is a very significant improvement. Your code might look something like this:

var spline, delta;

binaryFindByX (possibleIntersection, firstX, lastX) {
    middleX = firstX + (lastX - firstX) / 2;
    middlePoint = spline.pointAt(middleX);

    if (Math.abs(possibleIntersection.x - middlePoint.x) <= delta)
        return possibleIntersection.dst(middlePoint) <= delta ? possibleIntersection : null;
    else if (possibleIntersection.x < middlePoint.x)
        return binaryFindByX(possibleIntersection, firstX, middleX);
    else
        return binaryFindByX(possibleIntersection, middleX, lastX);
 }

binaryFindByX(pointOfLine, spline.getFirstX, spline.getLastX)

That said you still have to iterate through the Line’s points but do note that I was trying to shorten the processing of the Spline. In my case a Spline was longer and by definition more complex than the Line so it made more sense, but you can very much apply this logic the other way around.

The result is O(L*log(S)) complexity. That is a great improvement even by itself but in practice when we apply these modifications on the more complex object this really makes a huge difference in performance.

implementation

The XFlatSpline implementation (alongside with other Catmull-Rom utilities) is available on GitHub. The ‘calculateIntersection’ function will yield all intersections and uses ‘getPointOnSpline’ which implements the binary search based on the X coordinate. There’s a desktop demo where you can try it for yourself.

JPA – the uniqueness dilemma & solution

The dilemma

JPA does not support non-primary (often referred to as business) keys. In simple words if you want your entity to have an Id (as you normally do) and an additional composite key – you’re on your own. There are numerous articles and discussions on the subject worth checking out (yep, each word is a different link).

Let’s see if we can find a solution…

Solution #1 – Drop the Id and use a composite key

To have an Id is standard for many reasons. Even if you think you don’t need the Id (yes you do) you’re being forced to deviate from the standard just because of the lack of a better solution – no way.

Solution #2 – Keep the Id as your primary key and define unique constraints

It will be hard to read (as you’ll have to annotate the entity class instead of the fields) but it doesn’t sound that bad. Until.. welcome to EDD, exception driven development. – Not as good as TDD. The JPA has no intelligent way of letting you know whether the object already exists (often referred to as mergeOrCreate) instead it just occasionally throws a ConstraintViolationException in your face.

Meaning your implementation will look something like:

  • Try persisting
  • Got an exception? It’s already in the DB, go and fetch it..
  • No exception? Good.

Don’t you dare calling this a solution user453265436 on StackOverflow!

Solution #3 – Keep the Id, keep the constraints and make your own mergeOrCreate

The idea is to check if the object with the given unique fields already exists before trying to insert it into the DB. Luckily for us the good people of the internet offer some pseudo and actual implementations. Now all you have to do is write hashCode and equals functions for all your entities to be able to compare with tarnsient objects. And write equal criteria as well to be able to compare with persisted ones.

Do I seriously have to code this?! I fill sick already. Best part of my day.

Oh and make sure you can test is somehow. Don’t forget to keep hashCode and equals in sync. Also never misuse hashCode as key. Keep in mind what happens with your hash code if you update a collection.

Best part of my week. And we’re nowhere near multithreading yet – oh man, we’re gonna have such a great time!

Do yourself a favour and do it in a genral way as much as posibble. You might want to think about an Interface for your entities to provide their uniqueness criteria and a common EntityFactory or superclass. For some more detailed insight I recommend reading this post in particular from the above ones.

The solution I came up with is available on GitHub.

Below are some additional issues worth addressing. In some cases they’re part of the implementation, in others I’ll explain why they’re not.

Entity relationships

Pssst.. hey! Listen, don’t even bother just put everything in one entity.

If somehow by the grace of the ORM god you didn’t face the issue of uniquness yet, chances are you’re about to when normalizing your schema. Think about building up your entity in-memory that has a ManyToOne connection (Person and City in my example). When persisting it (besides checking the uniqueness of the entity itself) you need to check whether any connected entities already exist.

Solution

You’ll have to implement DAOs for every entity with ManyToOne connection. You’ll need to query that One for each of your Many.

Thought I was exaggerating? Best week ever!

On a sidenote here’s one reason why I prefer Hibernate’s Session API over JPA’s EntityManager API: it updates your object to the persisted state (i.e. assings Id when persisted). It makes synchronizing objects easier.

Those who say the both APIs are the same are dirty liars. They also tend to prefer EM. Don’t listen to them!

PARALLELISM

Aka. just when you thought it shouldn’t get any worse. I don’t even say “it can’t get worse” anymore.

We have to stop here and clarify how the Persistence Context cache works before we make more harm than good. Despite the many articles and examples that indicate otherwise JPA’s EntityManager and Hibernate’s Session offer an extended Persistence Context which means the cache is not bound to transaction but lives across transactions made from the same EntityManager/Session.

This is where Session’s getCurrentSession() comes into play. Another huge advantage of the Session API over EntityManager is that this method allows the threadsafe use of the API.

All you need to do is set ‘hibernate.current_session_context_class’ in your persistence config to ‘thread’. If you forget about it though you’ll get a nice exception during runtime which is, well, not so very nice…

Aaaaand that’s all for the good news. As for the bad news…

As mentioned before when using constraints you will get an ConstraintViolationException when trying to insert an entry that already exists in the DB. This may very well happen when multithreading even if you check whether the objects exists before inserting via mergeOrCreate because another thread may have created it in the meantime.

This might sound unlikely but when working with big amount of data it will happen – and this is exactly the case when you’re relying on your cache the most.

Why is this a problem? The Session / EntityManager object will be invalidated upon an expection and therefore the cache is lost. Meaning parallel execution will likely make your application slower.

Solution

You can avoid the Session invalidation by using nested transactions, however netiher of the mentioned APIs support it. Some others do though (e.g. Spring). If single threading is not an option (e.g. you’re developing a distributed app) you can still use locks.

Batch processing

In some cases this is something that could give you the performance boost you need. It’s not that simple here.

Persisting bigger chunks of data in one Transaction will leave you with probably even more ConstraintViolationExceptions – invalidating the whole Transaction. So instead of persisting multiple entities at once you’ll lose even those that we already persisted within the Transaction and have to start over.

In a single threaded environment that is only the case if the same entries are present within the same chunk. We can actually eliminate this possibility so this might be a possible improvement.

THE final solution?

It’s simple. We kill the batman.

We need support for business keys across application and DB layers. We need a persistence provider that can handle if a business key already exists in the persistence context or the DB.

It’s that simple.

libGDX – Iterating a Catmull-Rom Spline by fixed units

If you want a well defined curve Catmull-Rom is your go-to spline. It’s being used very often in graphics so I was glad to see that libGDX (a cross-platform game development library) has built-in support for it. But if you want to do some more advanced calculations you can easily run into problems.

out of the box iteration with libgdx

The most basic operation you’ll ever do with a spline is iterating over its points. Let’s look at rendering as an example:

path = new CatmullRomSpline<>(controlPoints, false); //false means non-continuous; bad design right there

for (float t = 0f; t <= 1f; t+= precision ) {
 Vector2 point = new Vector2();
 path.valueAt(point, t);
 shapeRenderer.circle(point.x, point.y, height);
}

In the above code we’re rendering small circles on the path of the spline (a dotted line) using libGDX’s CatmullRomSpline API.

Questions is: how do we choose the precision? Essentially it will determine the number of points rendered, therefore the smoothness of the spline but it also highly affects performace. It should obviously correlate with how long or pointed the spline is.

As length is fairly trivial and supported by the API we set up a small demo using something along the lines of:

int precisionOverLength = 5;
float length = path.approxLength(numberOfSamples);
precision = precisionOverLength / length;

Where precision over length determines your relative precision. Assuming length is in pixels: 1 would mean 1 point per pixel (very precise), 5 is 1 point per 5 pixels (less precise).

Let’s see the result:

Capture3

The big dots – in case you’re not familiar with Catmull-Rom splines – are the control points allowing you to shape the curve as it will always pass over those points. The actual curve is calculated from these points using a mathematical equation. Another term I must define is a span. A span is the section of the spline between two control points – this one has seven.

Did you notice the density in spans 3 and 4? Despite our efforts to achieve universal precision in these spans the precision is way higher than expected. The reason is that the number of points we’ll calculate on the spline is divided equally between spans. A shorter span therefore will have a higher density of points, a higher precision.

the upside

In many cases (and especially when rendering) this is helpful as sharp changes in direction in a small area could cause our spline to be fragmented. Having lots of points in these areas will make them smoother.

the downside

It will take as much time to compute a small area as to compute a large one even if that area is very simple and would not warrant a higher precision. Having no control over this may lead to performance issues.

You can’t guarantee a fixed or minimal density of points during iteration. This lack of guaranteed precision is most painful if you’re working with approximations and margins of error.

Imagine you’re looking for a specific point (e.g. one third) or an intersection of your spline. It has one very long and many short spans. If you want to be precise on the long span you’ll end up spending the unnecessarily big efforts on the shorter spans. And there’s still no guarantee that you’ll find what you’re looking for within the margin of error.

iteration by fixed units

Luckily for us there’s another method provided by the API where you can iterate only points of a specific span. This way we can move our precision calculation to the level of spans and bypass the equal point division between spans.

This will require quite some additional logic to keep track of where we are in the spline and what precision we should use in each span.

the result

SinglePointSplineIterator iterator = new SinglePointSplineIterator(path);
SplinePoint splinePoint;

while ((splinePoint = iterator.getNext()) != null) {
    shapeRenderer.circle(splinePoint.point.x, splinePoint.point.y, height);
}

Capture4

The code (alongside with other Catmull-Rom utilities) is available on GitHub. There’s an XFlatSpline class using the iterator (here’s why) and a desktop demo where you can try it for yourself. As a QoL improvement there’re separate single– and double point iterators available as in many cases you’ll need the current and previous points as well during iteration.

Finally a side-by-side comparison:

capture