如何生成凹多邊形的回波路徑

我需要一種算法來繪製任意多邊形的回波路徑。如果一個多邊形是凸的問題很容易解決。要理解我的意思，請查看下圖，黑色是原始多邊形，紅色是原始圖像生成的多邊形。如何生成凹多邊形的回波路徑

d是給出

β角度回聲路徑之間的距離很容易計算知道，我們有

頂點座標所以你可以看到每個頂點，我們可以計算出L，因此下一個回波路徑有新的頂點。

問題是當我們在某個點上有凹多邊形時，我們會得到一個醜陋的自交多邊形圖片。請看看這張照片。

我想要做的是生成沒有自交叉部分的回聲多邊形，即沒有虛線的部分。一個算法或java代碼將是非常有用的。謝謝。

編輯

只是添加一塊如此，因爲它被要求在評論爲凸多邊形產生回聲路徑的代碼。

public List<MyPath> createEchoCoCentral(List<Point> pointsOriginal, float encoderEchoDistance, int appliqueEchoCount){ 

    List<Point> contourPoints = pointsOriginal; 
    List<MyPath> echoPaths = new ArrayList<>(); 
    for (int round = 0; round < appliqueEchoCount; round++) { 

     List<Point> echoedPoints = new ArrayList<>(); 
     int size = contourPoints.size()+1;//+1 because we connect end to start 

     Point previousPoint = contourPoints.get(contourPoints.size() - 1); 
     for (int i = 0; i < size; i++) { 
      Point currentPoint; 
      if (i == contourPoints.size()) { 
       currentPoint = new Point(contourPoints.get(0)); 
      } else { 
       currentPoint = contourPoints.get(i); 
      } 
      final Point nextPoint; 
      if (i + 1 == contourPoints.size()) { 
       nextPoint = contourPoints.get(0); 
      } else if (i == contourPoints.size()) { 
       nextPoint = contourPoints.get(1); 
      } else { 
       nextPoint = contourPoints.get(i + 1); 
      } 
      if (currentPoint.x == previousPoint.x && currentPoint.y == previousPoint.y) continue; 
      if (currentPoint.x == nextPoint.x && currentPoint.y == nextPoint.y) continue; 

      // signs needed o determine to which side of polygon new point will go 
      float currentSlope = (float) (Math.atan((previousPoint.y - currentPoint.y)/(previousPoint.x - currentPoint.x))); 
      float signX = Math.signum((previousPoint.x - currentPoint.x)); 
      float signY = Math.signum((previousPoint.y - currentPoint.y)); 
      signX = signX == 0 ? 1 : signX; 
      signY = signY == 0 ? 1 : signY; 

      float nextSignX = Math.signum((currentPoint.x - nextPoint.x)); 
      float nextSignY = Math.signum((currentPoint.y - nextPoint.y)); 
      nextSignX = nextSignX == 0 ? 1 : nextSignX; 
      nextSignY = nextSignY == 0 ? 1 : nextSignY; 

      float nextSlope = (float) (Math.atan((currentPoint.y - nextPoint.y)/(currentPoint.x - nextPoint.x))); 
      float nextSlopeD = (float) Math.toDegrees(nextSlope); 

      //calculateMidAngle - is a bit tricky function that calculates angle between two adjacent edges 
      double S = calculateMidAngle(currentSlope, nextSlope, signX, signY, nextSignX, nextSignY); 
      Point p2 = new Point(); 

      double ew = encoderEchoDistance/Math.cos(S - (Math.PI/2)); 
      p2.x = (int) (currentPoint.x + (Math.cos(currentSlope - S)) * ew * signX); 
      p2.y = (int) (currentPoint.y + (Math.sin(currentSlope - S)) * ew * signX); 

      echoedPoints.add(p2); 
      previousPoint = currentPoint; 


     } 

     //createPathFromPoints just creates MyPath objects from given Poins set 
     echoPaths.add(createPathFromPoints(echoedPoints)); 
     //remove last point since it was just to connect end to first point 
     echoedPoints.remove(echoedPoints.size() - 1); 
     contourPoints = echoedPoints; 
    } 
    return echoPaths; 
}

來源

2016-08-01 Vilen

你能告訴我們你的凸多邊形的算法/代碼嗎？這太開放了，沒有看到你如何實現這一點。骨架會幫助某人填補空白。 –

@AndrewCheong這是一段很長的代碼，但通常我只是遍歷所有頂點計算兩個相鄰邊之間基於該角度的角度找到一個點與頂點的距離等於L並將該點添加到點列表下一個路徑。一旦我接近我的PC，我將添加代碼 – Vilen

因此，您不希望在底部示例中的「C」中包含孤立的三角形？ – samgak

好吧，找到一個庫，可以做我所需要的。它叫做Clipper

如果有人感興趣的話，它也有java的實現here。

隨着代碼的Java庫兩行做的伎倆

Path originalPath = new Path(); 
    for (PointF areaPoint:pointsOriginal){ 
     originalPath.add(new LongPoint((long)areaPoint.x, (long)areaPoint.y)); 
    } 
    final ClipperOffset clo = new ClipperOffset(); 
    Paths clips = new Paths(); 
    Paths solution = new Paths(); 
    clips.add(originalPath); 
    clo.addPaths(clips, Clipper.JoinType.SQUARE, Clipper.EndType.CLOSED_LINE); 
    float encoderEchoDistance = (float) UnitUtils.convertInchOrMmUnitsToEncoderUnits(this, inchOrMm, appliqueEchoDistance); 
    clo.execute(solution, encoderEchoDistance); 
    // Now solution.get(0) will contain path that has offset from original path 
    // and what is most important it will not have self intersections.

它是開源的，所以我會潛水的實施細節。感謝所有試圖幫助的人。

來源

2016-08-02 09:38:44 Vilen

您正在尋找straight skeleton：

^{（圖片來自Wikipedia）}

來源

2016-08-02 00:21:51

這個問題被稱爲計算多邊形偏移。有解決這個問題的兩種常用方法：

1）的最有效的方法是通過計算繞組的數字（如我理解來計算抵消多邊形，該算法是由限幅合約的庫使用）

2）計算直框架圖，這有助於你建立抵消多邊形有關這個主題的

有趣的文章：

陳，多邊形通過計算圈數

抵消Felkel的算法COMPU te直骨架

來源

2016-08-03 07:42:59 LmTinyToon

如何生成凹多邊形的回波路徑

回答

相關問題