Given a set of points in 2d coordinates system, how to calculate the minimum distance and the path if we visit all the points only once?

Question

The limit conditions are as below:

1. A fix threshold is set which makes distance larger than threshold are calculated by the distance itself and distance less than or equal to distance are regarded as a constant value;

2. It is better to let the path increases with the x coordinates (that is p1.x <= p2.x <= ... <= pn.x), but condition.1 is considered first, then the condition.2;

3. We can only visit each point for only once.

Answer 1

Note for optimization: So, basically a shortest Hamiltonian path with 2 twists (condition 1 & 2). Considering shortest HP can be solved with a Travelling Salesman algorithm (with a dummy city with zero distance from all others), for a better optimised solution you could try manipulating your distance matrix according to condition 1 before feeding it to a TSP algorithm. More on how to use TSP for this shortest HP here.

Brute force approach

I'm gonna call your points [A, B, ...C] for readability. Let's represent our points like this:

+---+---+---+
|   | X | Y |
+---+---+---+
| A | 0 | 0 |
| B | 4 | 3 |
| C | 0 | 3 |
+---+---+---+

Then create a distance matrix with the Pythagorean theorem:

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 5.00 | 3.00 |
| B | 5.00 | 0.00 | 4.00 |
| C | 3.00 | 4.00 | 0.00 |
+---+------+------+------+

My understanding of your first condition (fix threshold) is that any distance lower than a certain value is considered zero. Apply that condition to the distance matrix (let's say it's 3.50 in our case).

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 5.00 | 0.00 |
| B | 5.00 | 0.00 | 4.00 |
| C | 0.00 | 4.00 | 0.00 |
+---+------+------+------+

Now, if we keep to our brute force approach, we must fund all possible permutations of routes. In our case, it's going to be simply

+------+-----------+--------------+
| Path | Distances | Total Length |
+------+-----------+--------------+
| ABC  | 5+4       |            9 |
| ACB  | 0+4       |            4 |
| BAC  | 5+0       |            5 |
| BCA  | 4+0       |            4 |
| CAB  | 0+5       |            5 |
| CBA  | 4+5       |            9 |
+------+-----------+--------------+

Remove routes that are the same but reverse.

+------+-----------+--------------+
| Path | Distances | Total Length |
+------+-----------+--------------+
| ABC  | 5+4       |            9 |
| ACB  | 0+4       |            4 |
| BAC  | 5+0       |            5 |
+------+-----------+--------------+

Take the shortest by total length and that is your solution.

2nd condition - distance covered on X is preferable to distance covered on Y

As far as I understood, this condition only activates if there is a tie in Total Length. In that case, create a distance matrix by using the absolute value of the difference in the points' X coordinates:

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 4.00 | 0.00 |
| B | 4.00 | 0.00 | 4.00 |
| C | 0.00 | 4.00 | 0.00 |
+---+------+------+------+

Sum up the distances according to your tied routes and use the min of that to decide which one should be preferred.