1

I'm relatively new to programming, though I understand how it works at an intermediate level.

I have a LiDAR sensor (YDLiDAR-G4) that is set up on top of a wall, scanning everything across the wall. The goal is to have it so when someone touches the wall, the lidar detects the touch and then converts the polar data into x and y coordinates. The sensor has to be able to detect multiple touch points, for example one on the right side of the sensor and one on the left side. The amount of touch points should theoretically be infinite with a good enough sensor, but of course that's not possible so let's say there are a maximum of 10 touch points.

I have figured out pretty much all of the above, however because the sensor scans many different points, a single "touch point" will look like multiple points that are very close.

Is there a way to turn all of these points into one single "touch point?"

At first I tried running a nested for loop to see if a point is within a certain distance of another point, and if so it filters them out, but this is not super consistent and it doesn't work well.

In this code I have two vectors that hold a structure Point2D (cartesian coordinates), it checks if any points are within a certain distance of another and it only pushes one of them to the next list. List1 has all of the x and y coordinates that the lidar picks up, list 2 is empty.

static void filterPoints(const vector<Point2D>& list1, vector<Point2D>& list2, float distance) { //Modifying the two lists

    for (auto iter = list1.begin(); iter != list1.end(); iter++) {
        auto& inputPoint = *iter;
        bool merged = false;

        for (auto comparePointIter = list1.begin(); comparePointIter != list1.end(); comparePointIter++) {
            auto& comparePoint = *comparePointIter;

            if (pointDistance(inputPoint, comparePoint) < distance) {
                merged = true;
            }
            if (!merged) {
                list2.push_back(inputPoint);
            }
        }
    }
}

I already know this doesn't work because I'm pretty sure this only filters one point out of many, but I have no idea how else I can do this with this method.

So that gets to my question, is there an algorithm that takes the average of outliers only? For example if I have a thick finger and the sensor detects points at (.7,.7), (.72,.71) and (.75,.73), and also (.3,.3), (.29,.29) and (.28,.28) can I take the average of these and output them as individual points (.723,.713) and (.29,.29)?

SUNiMOD
  • 75
  • 2
  • 4
  • This seems like a classical application of a k-means clustering. Can you take a look at whether that task and its relevant algorithms help you? – nanofarad Jun 02 '21 at 04:40
  • @nanofarad thank you for bringing this up, the density-based clustering definitely seems like it would figure out what the points are, but it seems computationally intensive and this needs to be processed in real time. Consider it as if its a screen at 8hz and it needs to filter them out 8 times a second. I'm not super familiar with machine learning though so I could be wrong. – SUNiMOD Jun 02 '21 at 04:54
  • I don't know what hardware you have but k means isn't a terribly intense algorithm (especially in 2D) although it does use an interactive expectation maximization structure. Especially at 8 Hz this doesn't seem intractable unless you're very constrained on compute power. Give it a try and benchmark it first; you may be able to take extra optimizations or stop early. – nanofarad Jun 02 '21 at 05:01
  • @nanofarad okay I will definitely try it out, I've never used these types of algorithms before so it will be a learning curve, I'll get back to you with the results! – SUNiMOD Jun 02 '21 at 05:10
  • @nanofarad I'm trying to implement k-means but I'm finding it difficult because I have no way to determine how many clusters (k) there is. If I am able to find how many clusters (touch points) there are then I've pretty much already solved my issue. Would I start with a set amount K clusters (lets say 10) and then have the algorithm sort it down? Or do I use some other algorithm to estimate the amount: "gap statistic, the Calinski-Harabasz criterion, simple structure index, median (or mean) split silhouette, etc." (I found these in other places) – SUNiMOD Jun 02 '21 at 08:01
  • With just the current info, it's not too clear what the best approach is since I'm not familiar with that specific variation. However, there's a discussion that I found [here](https://stackoverflow.com/q/10136470/1424875). – nanofarad Jun 02 '21 at 20:25

0 Answers0