對角線掃描和一個點與對角線的正交距離

我有一個問題，我需要找到小於或等於給定距離D的點的最大數目D到在二維歐幾里德中繪製的線平面。爲了解決這個問題，我寫了一些算法，如果這條線與x軸或y軸正交，那麼這些算法將計算出可能的最大值。我的問題是隻有一條對角線會產生最大點數。對角線掃描和一個點與對角線的正交距離

給定x和y的最小值爲-1000000且最大值爲1000000的約束條件。我編寫了以下算法來嘗試找出最大值。我似乎沒有得到正確的答案。有人能請我指導我哪裏出錯。我已經嘗試繪製迴歸線，但是使用了垂直距離，這對我的目的不起作用。也許我錯了，這個問題可以作爲一個優化問題來解決。無論如何'任何幫助下降解釋非常感謝。

// diagonal sweep 
     for (int degree = 1; degree < 180; degree++) if (degree % 90 != 0) 
     { 
      int k = 1, degrees = degree; 
      double x1 = -1000000, x2 = 1000000; 
      if (degree > 90 && degree < 180) 
      { 
       degrees = 180 - degrees; 
       k = -1; 
      } 
      //slope 
      double m1 = Math.Tan(Math.PI * degrees * k/180.0); 
      //Point A 
      Point A = new Point(x1, m1 * x1); 
      //Point B 
      Point B = new Point(x2, m1 * x2); 
      for (int i = 0; i < x.Length; i++) 
      { 
       //Point P = household that needs power 
       Point P = new Point(x[i], y[i]); 
       double normalLength = Math.Sqrt((B.X - A.X) * (B.X - A.X) + (B.Y - A.Y) * (B.Y - A.Y)); 
       double segmentLength = 1d * Math.Abs((P.X - A.X) * (B.Y - A.Y) - (P.Y - A.Y) * (B.X - A.X))/normalLength; 
       if (segmentLength <= D) 
        tempCnt++; 
      } 
      maxConnections = Math.Max(maxConnections, tempCnt); 
      tempCnt = 0; 
     } 

     return maxConnections;

來源

2015-02-11 TheJackal

不完全確定我理解你的意圖。你循環度數從0到180，然後在那個角度創建一條線......但是通過什麼原點？ – dbc 2015-02-12 05:49:50

這是關於什麼？你在某個地方有很多點，必須通過它們迴歸一條線，然後選擇距離它一定距離的所有點？因爲OP文本和代碼令我感到困惑（文本意味着你不知道點和代碼是強力加點和線）所以知道什麼是未知的？如果點數未知，他們在某個網格上？（我不是C＃編碼器，所以我可能會缺少一些東西） – Spektre 2015-02-12 07:45:16

順便說一句，看看這裏：http://stackoverflow.com/a/20888844/2521214它可能有點幫助 – Spektre 2015-02-12 07:48:17

如果要定義這個問題作爲優化的問題，你應該這樣做如下，但它不是在我看來，這是否最優化問題是solveable高效地是。

maximize: x_1 + x_2 + ... + x_n + 0*a + 0*b + 0*c 
s.t. 
    x_i * d(p_i, line(a,b,c))/ MAX_DISTANCE <= 1 
    x_i is in {0,1}

說明：

x_i是包含變量 - 可以得到的0/1的值，並且表示如果點P_I是在從線所需的距離。
a,b,c是該行的參數：ax + by + c = 0
的想法是最大化包含的點，使得每個點包含在期望的範圍內的總和。這由約束表示，如果x_i = 0 - 對點p_i沒有限制，因爲約束始終滿足。否則，x_i = 1，並且您需要與行的距離（讓它爲d）滿足1* d/MAX_DISTANCE <= 1 - 這正是您想要的。

雖然我不認爲存在一個最優的有效的解決方案來優化問題，你可能想嘗試這個optiization一些啓發式的解決方案 - 如Genetic Algorithms或Hill Climbing

作爲一個邊注意，我的直覺說這個問題是NP完全的，儘管我還沒有證據 - 並且如果我（或者其他人）能夠想出一個簡化/多項式解決方案，它將更新這部分答案。

來源

2015-02-11 09:35:26 amit

對角線掃描和一個點與對角線的正交距離

回答

相關問題