#StackBounty: #java #algorithm #game #collision Handling collision on a turn-based 2D game

Bounty: 100

I have implemented a collision check algorithm that I have created for my game, and the algorithm uses recursion.

Now it all works fine, and I thought to myself, what if there was a way to solve this algorithm, without using recursion, and more something with promise callbacks, or something, but unfortunately after researching, I could not find any way that I can think of at this time, so I thought I should ask there.

Now by turn-based I mean that the game is basically a big board of rectangles where each rectangle is a tile position, and there are ships, each ship can be on a tile unless its a rock, or another ship on there.

Now the collision is handled server-sided, so the coordinates are always integers, so it’s not some graphical collision check, don’t get me wrong.

There’s an Example of collision, you can see that the ship selected the moves Right, Left, Right, and the left move collided, because the other ship does not move at that turn of the move.

So how does my algorithm work

    // Loop through all turns
    for (int turn = 0; turn < 4; turn++) {
        // Loop through phases in the turn (split turn into phases, e.g turn left is 2 phases, turn forward is one phase).
        // So if stopped in phase 1, and its a turn left, it will basically stay in same position, if in phase 2, it will only
        // move one step instead of 2 full steps.
        for (int phase = 0; phase < 2; phase++) {

             // Go through all players and check if their move causes a collision
             for (Player p : players) {

                 // If a player is already collided in this step, we don't want him to move
                 // anywhere, so we skip this iteration
                 if (p.getCollisionStorage().isCollided(turn)) {

                 // Checks collision for the player, according to his current step #phase index and turn
                 collision.checkCollision(p, turn, phase, true);

So basically checkCollision(Player p, int turn, int phase, boolean setPos) is where the collision is handled, and is a big method. This method basically goes through the collision rules and saves into players’ collision storage if it collided or not.

But here comes the recursion part: When a tile is already claimed, in the method, we check if the claimed player has a move placed on that turn, if yes, we will run the checkCollision method on that player that claimed it, if the player collided during his move, the method will return true, and then we know that this claimed player did not move, so the player we check for will collide with him. And now imagine a line of ships, and ship A wants to move forward, so we check ship B, ship B checks ship C and on and on and makes sure that every checkCollision returned false, so ship A can move and rest can move as-well.

Now I am curious, if there is a better way on implementing this besides using a recursion?

 * Checks if a player has a collision according to his move, in the given turn and move-phase
 * @param p             The player to check
 * @param turn          The turn
 * @param phase         The move-phase step
 * @param setPosition   If to set the next position or not on non-collided result
 * @return  <code>TRUE</code> If the player was collided, <code>FALSE</code> if not.
public boolean checkCollision(Player p, int turn, int phase, boolean setPosition) {
    // The current selected move of the player
    MoveType move =  p.getMoves().getMove(turn);

    // If this player was bumped, and a move was not selected, we want to process the bump animation
    // But we have to check if the position to be bumped is available to be claimed
    if (move == MoveType.NONE && p.getCollisionStorage().isBumped()) {
        Position pos = p.getCollisionStorage().getBumpAnimation().getPositionForAnimation(p);
        Player claimed = players.getPlayerByPosition(pos.getX(), pos.getY());
        // Claiming checking for the new position for bump
        return claimed != null && (claimed.getMoves().getMove(turn) == MoveType.NONE || checkCollision(claimed, turn, phase, false));

    // Use the current position as default, imply we have already set it
    Position position = p;

    // If not set by default.txt on previous loops, gets the next position on the map for the given phase on the given move
    if (!p.getCollisionStorage().isPositionChanged()) {
        position = move.getNextPositionWithPhase(p, p.getFace(), phase);
    // If the player has moved since his last position
    if (!position.equals(p)) {
        // Check for bounds collision with the border
        if (checkBoundCollision(p, turn, phase) || checkRockCollision(p, turn, phase)) {
            return true;
        // Check if the next position is claimed by another player, null result if not
        Player claimed = players.getPlayerByPosition(position.getX(), position.getY());

        // If the result is not null, the position is claimed
        if (claimed != null) {
            Position claimedNextPos = claimed;
            if (!claimed.getCollisionStorage().isPositionChanged()) {
                claimedNextPos = claimed.getMoves().getMove(turn).getNextPositionWithPhase(claimed, claimed.getFace(), phase);

            // Check if the claimed position doesn't move away
            if (claimed.getMoves().getMove(turn) == MoveType.NONE || claimedNextPos.equals(claimed)) {
                if (move != MoveType.FORWARD || claimed.getVessel().getSize() >= p.getVessel().getSize()) {
                    collide(p, claimed, turn, phase);

                if (move == MoveType.FORWARD && canBumpPlayer(p, claimed, turn, phase)) {
                    bumpPlayer(claimed, p, turn, phase);


                return true;
            else if (claimedNextPos.equals(p)) { // If they switched positions (e.g nose to nose, F, F move)
                collide(p, claimed, turn, phase);
                collide(claimed, p, turn, phase);
                return true;
            else {
                // Make sure that the claimed position moves away successfully
                if (!checkCollision(claimed, turn, phase, false)) {
                    if (setPosition) {
                        // Moved successfully, claim position
                else {
                    // did not move successfully, collide
                    collide(p, claimed, turn, phase);
                    collide(claimed, p, turn, phase);
                    return true;
        } else {
            // List of players that collided with this player, while performing this move, in this phase
            List<Player> collisions = getPlayersTryingToClaim(p, position, turn, phase);

            if (collisions.size() > 0) { // Collision has happened

                Player largest = getLargestSize(collisions);

                if (countPlayersForSize(collisions, largest.getVessel().getSize()) > 1) {
                    // Stop players from movement
                    for (Player pl : collisions) {
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, pl, turn, phase);
                else {
                    for (Player pl : collisions) {
                        if (pl == largest) {
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, largest, turn, phase);
                    if (!largest.getCollisionStorage().isPositionChanged()) {
                return true;
            } else {
                if (setPosition) {

    return false;

Get this bounty!!!

#StackBounty: #java #algorithm #recursion #comparative-review #backtracking Two approaches to print all permutations – returning versus…

Bounty: 50

I have noticed many of the backtracking problems have two ways of solving.

One is to return “whatever’s the required list”, vs passing-through the “result” to every call and appending to it. What is the downside of returning (is it less memory/time efficient)? Example – To print all possible permutations, what makes this solution inefficient vs the second one.

public List<List<Integer>> perm(int[] nums){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(nums.length == 0){
        result.add(new ArrayList<Integer>());
        return result;        
    for(int i= 0;i<nums.length;i++){
        int first = nums[i];
        int[] remnums = new int[nums.length-1];
        int j = 0;
        for(int cur : nums){
            if(cur != first){
                remnums[j] = cur;j++;
        List<List<Integer>> tmp = perm(remnums);

        for(List<Integer> t : tmp){

    return result;

2nd approach —

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);

Get this bounty!!!

#StackBounty: #java #performance #algorithm #swing #computational-geometry Java algorithm to declutter rectangles

Bounty: 100

I’ve been working on an algorithm to declutter rectangles. It seems to work fine when I have less than 1,000 rectangles, but becomes much slower when there are 10,000, which I believe to be because the algorithm is inefficient with large datasets. I’m looking to find ways to optimize to perform better with more rectangles.

The code I have is based on this algorithm (which is based on this SO answer from another similar question: https://stackoverflow.com/a/3266158/33863):

Find the center C of the bounding box of your rectangles.

For each rectangle R that overlaps another:

  • Define a movement vector v.
  • Find all the rectangles R’ that overlap R.
  • Add a vector to v proportional to the vector between the center of R and R’.
  • Add a vector to v proportional to the vector between C and the center of R.
  • Move R by v.
  • Repeat until nothing overlaps.

This incrementally moves the rectangles away from each other and the center of all the rectangles. This will terminate because the component of v from step 4 will eventually spread them out enough all by itself.

Here is the code I’m working with:

public class Rectangles extends JPanel {

    // Create sample rectangles laid out in frame
    List<Rectangle2D> rectangles = new ArrayList<Rectangle2D>();
        // x,y,w,h
        // random rectangles
        rectangles.add(new Rectangle2D.Float(300, 50, 50, 50));
        rectangles.add(new Rectangle2D.Float(300, 50, 20, 50));
        rectangles.add(new Rectangle2D.Float(100, 100, 100, 50));
        rectangles.add(new Rectangle2D.Float(120, 200, 50, 50));
        rectangles.add(new Rectangle2D.Float(150, 130, 100, 100));
        rectangles.add(new Rectangle2D.Float(0, 100, 100, 50));
        rectangles.add(new Rectangle2D.Float(690, 229, 388, 114));
        rectangles.add(new Rectangle2D.Float(347, 341, 347, 425));
        rectangles.add(new Rectangle2D.Float(107, 515, 179, 158));
        rectangles.add(new Rectangle2D.Float(55, 487, 174, 153));
        rectangles.add(new Rectangle2D.Float(458, 553, 125, 128));
        rectangles.add(new Rectangle2D.Float(109, 566, 125, 128));
        rectangles.add(new Rectangle2D.Float(138, 166, 125, 128));

        int numRowsAndColumns = 20;
//      int numRowsAndColumns = 50;
//      int numRowsAndColumns = 100;
//      Add more rectangles
        for (int i = 0; i < numRowsAndColumns; i++) {
            for (int j = 0; j < numRowsAndColumns; j++) {
                rectangles.add(new Rectangle2D.Float(i * 20, j * 10, 25, 20));

        System.out.println("Num Rectangles " + rectangles.size());

    //The list of rectangles that are drawn on the screen
    List<Rectangle2D> rectanglesToDraw;

    //reset the view back to the unaffected rectangles
    protected void reset() {
        rectanglesToDraw = rectangles;


    //Given a rectangle, find the rectangles from the rectList that intersect with it
    private List<Rectangle2D> findIntersections(Rectangle2D rect, List<Rectangle2D> rectList) {

        ArrayList<Rectangle2D> intersections = new ArrayList<Rectangle2D>();

        for (Rectangle2D intersectingRect : rectList) {
            if (!rect.equals(intersectingRect) && intersectingRect.intersects(rect)) {

        return intersections;

    //main algorithm that attempts to declutter the rectangles.    
    protected void fix() {
        rectanglesToDraw = new ArrayList<Rectangle2D>();

        //make copies to keep original list unaffected
        for (Rectangle2D rect : rectangles) {
            Rectangle2D copyRect = new Rectangle2D.Double();

        // Find the center C of the bounding box of your rectangles.
        Rectangle2D surroundRect = surroundingRect(rectanglesToDraw);
        Point center = new Point((int) surroundRect.getCenterX(), (int) surroundRect.getCenterY());

        int numIterations = 0;

        int movementFactor = 10; //ideally would be 1

        boolean hasIntersections = true;

        //keep going until there are no intersections present    
        while (hasIntersections) {

            //initialize to false within the loop.  
            hasIntersections = false;

            for (Rectangle2D rect : rectanglesToDraw) {

                // Find all the rectangles R' that overlap R.
                List<Rectangle2D> intersectingRects = findIntersections(rect, rectanglesToDraw);

                if (intersectingRects.size() > 0) {

                    // Define a movement vector v.
                    Point movementVector = new Point(0, 0);

                    Point centerR = new Point((int) rect.getCenterX(), (int) rect.getCenterY());

                    // For each rectangle R that overlaps another.
                    for (Rectangle2D rPrime : intersectingRects) {
                        Point centerRPrime = new Point((int) rPrime.getCenterX(), (int) rPrime.getCenterY());

                        int xTrans = (int) (centerR.getX() - centerRPrime.getX());
                        int yTrans = (int) (centerR.getY() - centerRPrime.getY());

                        // Add a vector to v proportional to the vector between the center of R and R'.
                        movementVector.translate(xTrans < 0 ? -movementFactor : movementFactor,
                                yTrans < 0 ? -movementFactor : movementFactor);


                    int xTrans = (int) (centerR.getX() - center.getX());
                    int yTrans = (int) (centerR.getY() - center.getY());

                    // Add a vector to v proportional to the vector between C and the center of R.
                    movementVector.translate(xTrans < 0 ? -movementFactor : movementFactor,
                            yTrans < 0 ? -movementFactor : movementFactor);

                    // Move R by v.
                    rect.setRect(rect.getX() + movementVector.getX(), rect.getY() + movementVector.getY(),
                            rect.getWidth(), rect.getHeight());

                    // Repeat until nothing overlaps.
                    hasIntersections = true;




        System.out.println("That took " + numIterations+ " iterations.");



    //find the Bounding rectangle of the list of rectangles
    //by iterating over all rectangles and 
    //finding the top left and bottom right corners
    private Rectangle2D surroundingRect(List<Rectangle2D> rectangles) {

        Point topLeft = null;
        Point bottomRight = null;

        for (Rectangle2D rect : rectangles) {
            if (topLeft == null) {
                topLeft = new Point((int) rect.getMinX(), (int) rect.getMinY());
            } else {
                if (rect.getMinX() < topLeft.getX()) {
                    topLeft.setLocation((int) rect.getMinX(), topLeft.getY());

                if (rect.getMinY() < topLeft.getY()) {
                    topLeft.setLocation(topLeft.getX(), (int) rect.getMinY());

            if (bottomRight == null) {
                bottomRight = new Point((int) rect.getMaxX(), (int) rect.getMaxY());
            } else {
                if (rect.getMaxX() > bottomRight.getX()) {
                    bottomRight.setLocation((int) rect.getMaxX(), bottomRight.getY());

                if (rect.getMaxY() > bottomRight.getY()) {
                    bottomRight.setLocation(bottomRight.getX(), (int) rect.getMaxY());

        return new Rectangle2D.Double(topLeft.getX(), topLeft.getY(), bottomRight.getX() - topLeft.getX(),
                bottomRight.getY() - topLeft.getY());

    //Draws the rectangles in the frame from the rectanglesToDraw data structure  
    public void paintComponent(Graphics g) {
        Graphics2D g2d = (Graphics2D) g;

        for (Rectangle2D entry : rectanglesToDraw) {
            g2d.setStroke(new BasicStroke(1));
            // g2d.fillRect((int) entry.getX(), (int) entry.getY(), (int) entry.getWidth(),
            // (int) entry.getHeight());


    //create GUI components and display it to the user
    protected static void createAndShowGUI() {
        Rectangles rects = new Rectangles();


        JFrame frame = new JFrame("Rectangles");
        frame.setLayout(new BorderLayout());
        frame.add(rects, BorderLayout.CENTER);

        JPanel buttonsPanel = new JPanel();

        JButton fix = new JButton("Fix");

        fix.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent e) {

                long start = System.currentTimeMillis();
                long end = System.currentTimeMillis();

                System.out.println("That took "+TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.MILLISECONDS)+ " ms");


        JButton resetButton = new JButton("Reset");

        resetButton.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent e) {


        frame.add(buttonsPanel, BorderLayout.SOUTH);

        frame.setSize(1920, 900);

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {

            public void run() {



Here are a couple of screenshots to illustrate what its doing:



Get this bounty!!!

#StackBounty: #collision-detection #algorithm #tile Tile-based board game collision mechanism algorithm

Bounty: 100

I am looking to see ideas for an algorithm which will handle collisions for some battle-ship tile-based board game.

A little about the game

The game is pretty simple. Basically there is a board, which usually sized 20x36 tiles. One tile is a position that a ship can be at, unless the tile is a rock tile.

Many ships are in the game, and all players have 35 seconds to select 4 moves that their ship will perform. After these 35 seconds, all ships will perform the selected moves parallel, by doing the first selected move, then going to the second, third and fourth, and then 35 seconds again to select new moves.

A ship can either move Forward, Left or Right.

Now these are the collision rules for the game:

  1. All ships that are moving (regardless of direction) attempt to “claim” the space that started directly in front of them. That space has five possibilites:
    a. That space is empty and unclaimed. Then move the ship into that space.
    b. That space contains a stationary ship. Then execute a “bump” (see below).
    c. That space contains a ship that is moving, and claiming the first ship’s space. Then stop movement entirely (with a collision).
    d. That space is empty but claimed by a ship of the same or larger class. Then stop movement entirely (with a collision).
    e. That space is empty but claimed by a ship of smaller class. Then move the ship into that space (with a collision).
  2. All ships that are turning but have not “stopped entirely” then attempt to claim their destination space. Now that space also has five possibilities:

2.a. That space is empty and unclaimed. Then move the ship into that space.

2.b. That space contains a stationary ship OR a ship that moved there in step 1. Then stop movement entirely (with a collision).

2.c. That space contains a ship that is moving, and claiming the first ship’s space. Then stop movement entirely (with a collision).

2.d. That space is empty but claimed by a ship of the same or larger class. Then stop movement entirely (with a collision).

2.e. That space is empty but claimed by a ship of smaller class. Then move the ship into that space (with a collision).
Note: At the end, all ships have their orientation changed if they tried to turn… even if they had “stopped entirely.”
Note that (2b) does not depend on the ship’s class. This allows a small ship to move forward into a tile even if a larger ship is attempting to turn into that tile. If two ships both try to move into the same tile for any other reason, the larger ship succeeds.


So let’s say you select the forward move on your ship, and there is another ship on the target tile you are aiming to (forward). So what do you need to make sure?

You need to check if that target tile is unclaimed. If it’s not unclaimed, you can check if its a rock or another ship. If it is a rock, cancel movement. If it’s another ship, and it does not move, push it by 1 tile and stay in the same location. If that ship does move, you have to ask it if that ship has successfully moved, but for it to return a success message, that other ship has to check if it can move, and that can have a lot of cases with a lot of callbacks and might end up not efficient.

So my question is, how can this be done, in the proper way?

Read more here about the collision mechanism rules

Get this bounty!!!

#StackBounty: #security #cryptography #cryptonote #cryptonight #algorithm Is CryptoNight the hash function which plays the role of the …

Bounty: 50

Is CryptoNight the hash function which plays the role of the “random oracle” in the random oracle model under which certain properties of CryptoNote are mathematically proven in the original paper? Or am I confusing concepts?

If I’m confusing concepts, what is the “random oracle” hash function in CryptoNote?

And how much do we know about the likelihood that the algorithm is good enough to reasonably approximate the behavior of a random oracle and how does that impact the validity of the proofs in the paper, do we have reasons to worry that it might have some bad behavior which would invalidate the Linkability/Exculpability/Unforgeability/Anonimity properties?

Get this bounty!!!

#StackBounty: #regex #algorithm regular expression algorithm beyond leetcode

Bounty: 50

The problem is the leetcode question,
which uses the pattern(characters with . and/or *) to match the string(characters without * and .), what I want to ask is that is it possible for a pattern to match with the pattern in the scenerio of this question.


‘.’ can be replaced with any single character.

‘*’ can be replaced with zero or more of the preceding element.

For example, try to use bdbaa.* to match bdb.*daa

I know the solution to the original problem can be dynamic programming or backtracking, but I don’t know how I can solve the pattern-matching-pattern version of the problem.

Get this bounty!!!

#StackBounty: #javascript #node.js #algorithm Punch multiple strings into a single (shortest possible) string that includes all the cha…

Bounty: 50

My purpose is to punch multiple strings into a single (shortest) string that will contain all the character of each string in a forward direction. The question is not specific to any language, but more into the algorithm part. (probably will implement it in a node server, so tagging nodejs/javascript).

So, to explain the problem:

Lets consider I have few strings

["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"]

The Resultant string should be something like:


jack: sjmachppoalidveonrk

apple: sjmachppoalidveonrk

solid: sjmachppoalidveonrk

====================================>>>> all in the forward direction

These all are manual evaluation and the output may not 100% perfect in the example.

So, the point is all the letters of each strings have to exists in the output in
FORWARD DIRECTION (here the actual problem belongs), and possibly the server will send the final strings and numbers like 27594 will be generated and passed to extract the token, in the required end. If I have to punch it in a minimal possible string it would have much easier (That case only unique chars are enough). But in this case there are some points:

  1. Letters can be present multiple time, though I have to reuse any
    letter if possible, eg: for solid and hold o > l > d can be
    reused as forward direction but for apple (a > p) and spark
    (p > a) we have to repeat a as in one case it appears before p
    for apple, and after p for sparks so either we need to repeat
    a or p. we cannot do p > a > p as it will cover both the case
    because we need two p after a

  2. We directly have no option to place a single p and use the same
    index twice in time of extract, we need multiple p with no option
    left as the input token contains that

  3. I am (not) sure, that there is multiple output possible for a set of
    strings. but the concern is it should me minimal in length,
    the combination doesn’t matter if its cover all the tokens
    in a forward direction. all (or one ) outputs of minimal possible length
    need to trace.

I have tried, by starting with a arbitrary string, and then made a analysis of next string and splitting all the letters, and place them accordingly, but after some times, it seems that current string letters can be placed in a better way, If the last string’s (or a previous string’s) letters was placed according to the current string. But again that string was analyzed and placed based on something (multiple) what was processed, and placing something on the favor of something what is not processed seems difficult, because to that we need to process that. Or might me maintaining a tree of all processed/unprocessed tree will help, building the building the final string. Any better way than it, It seems a brute force!

Note: I know there are a lot of other transformation possible, please try not to suggest anything else to use, we are doing a bit research on it, and anything in the context of question will be highly appreciated. If anything is not clear or need any further explanation feel free to comment. Thanks a ton for reading the entire problem with patience.

Get this bounty!!!

#StackBounty: #java #algorithm #apache-spark #spark-streaming Build path for different events and assign globalID

Bounty: 50

We are working with spark 1.6 and we are trying to keep global identity for similar events. There can be few “groups”of events with identical ID (in the example as number. letters are added just for uniqueness). And we know that some of these events are similar so we are able to connect them. We want to keep something like:

Z -> 1, 2, 3
X -> 4

so in a future if some events with id 4 will come we can assign X as a global identity.

Please check example for better illustration:

Let’s say we have some streaming data coming into spark job.


Since event 1 is our first appearance we want to assign 1 to Z.
Next what we know is that 1b and 2c are similar. so we want to keep somewhere 2->1 mapping. Same thing is for 2e and 3f so we need mapping 3-2. So for now we have 3 pairs 1->Z, 2->1, 3->2.

And we want to create “historical” path: Z <- 1 <- 2 <- 3
At the end we will have all events with ID = Z.

1a -> Z
1b -> Z
2c -> Z
2d -> Z
2e -> Z
3f -> Z
3g -> Z
3h -> Z
4i -> X

We tried to use mapwithstate but only thing we were able to do was that 2->1 and 3->2. With mapwithstate we were not able to get state for “parent” in state for current event – eg. current event 3 with parent 2 and not able to get 2 -> 1 and neither 1 -> Z.

Is it possible to have some global mapping for this? We already tried accumulators and broadcast but looks like not very suitable. And we were not able to replace events 1 for first mapping and events 2 for second mapping with Z.

If new event 5 will come and it is similar with 3h for example we need to assign mapping 5->Z again.

Get this bounty!!!

#StackBounty: #algorithm #vector #3d #projection #triangulation Project and triangulate a vector. From 3D to 2D and viceversa

Bounty: 50

I’m having some issues when projecting a 3D vector in an image with known pose, and triangulating two 2D lines in two images with known poses.

Project 3D vector

Let’s suppose we have a vector v_world = (x_v, y_v, z_v) in world coordinates. I want to project it in an image taken from a camera with known intrinsic and extrinsic parameters. The pose of this camera is an homogeneous matrix 4×4 Tcw. For a vector projection, I only need the rotation 3×3 submatrix Rcw. Let’s get the vector v in camera coordinates.

v_camera = Rcw * v_world

This would be the same as.

(v_camera, 0) = Tcw * (v_world, 0)

To get now the vector in 2D, I just have to ignore the depth dimension and realize this operation.

v_camera_2D = atan2(v_camera[1], v_camera[0])

Triangulate two 2D lines


Let’s suppose I want to triangulate two lines. The first one pass through the pixel (x_1, y_1) in the first image with known optical center (cx_1, cy_2), focal length (fx_1, fy_1) and pose Tcw_1. Second line pass through the pixel (x_2, y_2) in the second image with known optical center (cx_2, cy_2), focal length (fx_2, fy_2) and pose Tcw_2. Both lines’ orientation are also known, v_1 and v_2, in given images.

I want to triangulate these lines to get the world orientation of the 3D line.

My first step is to construct the plane that contains the 2D line and the optical center of the camera. The 3D line will be the the intersection of the two constructed planes in both images. This is, the cross products of the planes’ normal vector.

I just need then the normal vector of the desired planes. For this, I calculate the vector from the optical center to the line point.

v_plane1 = ( (x_1 - cx_1) / fx_1, (y_1 - cy_1) / fy_1, 1)

And convert it to world coordinates.

v_plane1_world = (Rcw)^T * v_plane

I convert too the 2D line orientation to 3D world coordinates.

v_line1 = ( cos(v_1), sin(v_1), 0 )
v_line1_world = (Rcw)^T * v_line1

The normal vector of the desired plane is the cross product of its two containing vectors.

v_normal_plane1_world = v_plane1_world x v_line1_world

And the orientation of the 3D line will be.

v_world = v_normal_plane1_world x v_normal_plane2_world 

I have implemented it and doesn’t work. I create an initial 3D line. I project it in two images, and triangulate both projections again. The triangulation and the initial 3D line should be the same (with a float precision threshold). Both lines are the same when I create a basic 3D line (an horizontal line, for example) and project it in two basic images (with any rotation). But the lines don’t match when doing the same with rotated and translated images.

Is there any step I am wrongly doing? I don’t pay attention to the vectors’ magnitude, because I only want the orientation. I can upload my code to a repository if it’s needed.

Get this bounty!!!

#StackBounty: #python #performance #algorithm #strings #search Naive implementation of KMP algorithm

Bounty: 50

After reading this answer to the question “High execution time to count overlapping substrings”, I decided to implement the suggested Knuth-Morris-Pratt (KMP) algorithm. I used the pseudo-code listed on Wikipedia for the functions kmp_table and kmp_search.

However, when running it on some corner-cases, I have observed that it is a lot slower than the standard str.find, which apparently uses a modified Boyer-Moore-Horspool algorithm and should thus have worse worst-case performance.

The specific case I looked at is:

$ ipython -i kmp.py
In [1]: text = "A"*1000000 + "B"
In [2]: word = "A"*100 + "B"
In [3]: %timeit kmp_search(text, word)
1 loop, best of 3: 410 ms per loop
In [4}: %timeit text.find(word)
1000 loops, best of 3: 703 ┬Ás per loop

So the difference is about a factor 1000 for this input. This is probably due to the fact that the native one is written in C and this is written in Python, but I still wanted to see if I did anything stupid here or missed any obvious optimization.

def kmp_table(word):
    table = [0] * len(word)
    position, candidate = 2, 0
    table[0] = -1

    while position < len(word):
        if word[position - 1] == word[candidate]:
            table[position] = candidate + 1
            candidate += 1
            position += 1
        elif candidate > 0:
            candidate = table[candidate]
            table[position] = 0
            position += 1
    return table

def kmp_search(text, word):
    m, i = 0, 0
    table = kmp_table(word)
    while m + i < len(text):
        if word[i] == text[m + i]:
            if i == len(word) - 1:
                return m
            i += 1
            if table[i] > -1:
                m += i - table[i]
                i = table[i]
                m += 1
                i = 0
    return len(text)

Get this bounty!!!