在給定的矩形中最大化點 - （int spacing，int deviation）

我需要一個返回點數組的函數，它必須最大化矩形中的點數。該功能必須支持100毫米的間距（在任何方向），但它可以偏離x（整數）來創建幾乎適合的點。我們也想盡量減少偏差。在給定的矩形中最大化點 - （int spacing，int deviation）

在給定的區域內有形狀，點不能落入其中。我有一個工作函數boolean isCollide（Point point）。

這實際上是一個CAD問題，邏輯將應用於Catia v5。我希望獲得sudo代碼。矩形大小是不變的，並且用PLATEXMAX和PLATEYMAX來確定尺寸。

我的解決方案必須是詳盡的，我所有的嘗試都只提供啓發式解決方案。算法效率不是問題。任何人都面臨類似的問題，或有任何建議？

我創建了一個插圖來顯示我的問題的視覺表示。 http://tinypic.com/r/vebtj5/8

編輯：

點[] tempArray =新點[]

對於i = 0至PLATEXMX {

for j=0 to PLATEYMAX{ 

    Point test = new Point(i,j) 
    Boolean found = false 

    foreach tpoint in tempArray{ 
    if !found{ 
     for n=0 to deviation{ 
     if tpoint.distanceTo(test) < (100 + n){ 
       if !(isCollide(test){ 
        tempArray.add(test) 
        break 
       } else{ 
        //check points offset from this point 
        //check every offset point 360deg around test 
        //increase checking radius to max deviation 

       } 
      } 
     } 
    }

來源

2015-05-28 Lloyd

你是什麼意思100毫米的間距？你有什麼試過？我想你也會找到它的僞碼！ – Luke

另外，你期望有多少點？ – Luke

我期望在10-40點之間。 – Lloyd

如果只有幾個點，它可能是可行'嘗試每個解決方案'。所以如果你有8個點，嘗試所有包含/不包括的點的2^8排列，檢查該點集是否適合給定的矩形。這將是最容易實現的：使用for循環，其中的整數i從0到2^n，並使用位掩碼在測試中包含/不包含某些元素。

作爲一個稍微弱一點的方法，嘗試回溯。本質上，你嘗試所有的點排列，但一旦解決方案無效就停止（即，如果一組點不適合給定的矩形，Wiki提供了僞代碼中的這種實現方式

來源

2015-05-28 04:06:44 Luke

在給定的矩形中最大化點 - （int spacing，int deviation）

回答

相關問題