原帖:

我正在尝试找到凸多边形的最外侧顶点(与多边形外的点P有关).现在,我只关心矩形(但是,我想要一个适用于任何凸多边形的算法).

我的计划是从外部点P到中心点C构造一条线.从该线的参考,我将构建从点线P至点1,2,3和4.由于点2和4将具有距参考线最大(最正)和最小(最负)角度,因此它们将被识别为最外侧顶点.

这是这项工作的最佳算法吗？如何从参考角度(最好用Java)计算角度？

更新澄清:

我绘制了线条(参考线为红色).如您所见,从P到2的线在参考线的一侧创建最大角度,而从P到4的线创建另一侧的最大角度.因此,这些是最外面的顶点.

Open-CV 2.4 Android-Java:

我搜索了等高线(MatofPoint列表),如下所示:

Imgproc.findContours(roi_mat, contours, hierarchy, cfg.retMode, cfg.apxMode);

然后是凸壳(必须是MatofInt的列表)

for (int k=0; k < contours.size(); k++){

     Imgproc.convexHull(contours.get(k), hull.get(k));
}

凸壳需要一个MatofInt,但是drawcontours想要一个MatofPoint ..那么该怎么办？

Thx提前..

编辑:@ OpenCV4Android

for (int k=0; k < contours.size(); k++){
    Imgproc.convexHull(contours.get(k), hullInt);

    for(int j=0; j < hullInt.toList().size(); j++){
        hullPointList.add(contours.get(k).toList().get(hullInt.toList().get(j)));
    }

    hullPointMat.fromList(hullPointList);
    hullPoints.add(hullPointMat);   
}

Imgproc.drawContours( mROI, hullPoints, -1,  new Scalar(255,0,0, 255), 1);

我想用d3在一个分组的力导向图构建周围画一个船体.

我用圆圈构建了图表.但我现在想要加入圆圈与路径(船体)的交叉点.如果没有加入交叉路口,那么围绕这组圆圈绘制船体就足够了.我尝试了使用Convex Hull示例的Force-Directed Layout.但我有文字和圆圈覆盖文本和连接文本的链接.

var vertices = new Array();
var width = 960,
    height = 500;
var color = d3.scale.category10();
var r = 6;
var force = d3.layout.force().size([width, height]);
var svg = d3.select("body").append("svg").attr("width", width).attr("height", height).attr("transform", "translate(" + width / 2 + "," + height / 2 + ")");
$(function() {

    var json = "{\"nodes\":[{\"name\":\"language\",\"group\":1,\"fontsize\":\"45px\",\"title\":null},{\"name\":\"english\",\"group\":1,\"fontsize\":\"35px\",\"title\":null},{\"name\":\"languages\",\"group\":1,\"fontsize\":\"21px\",\"title\":null},{\"name\":\"speak\",\"group\":1,\"fontsize\":\"16px\",\"title\":null},{\"name\":\"religion\",\"group\":1,\"fontsize\":\"16px\",\"title\":null},{\"name\":\"words\",\"group\":1,\"fontsize\":\"16px\",\"title\":null},{\"name\":\"living\",\"group\":1,\"fontsize\":\"16px\",\"title\":null},{\"name\":\"adobe\",\"group\":2,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"malayalam\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"learn\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"multilanguage\",\"group\":3,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"different\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"sarcasm\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"linkedin\",\"group\":4,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"hindi\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"indesign\",\"group\":5,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"city\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"spanish\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"religious\",\"group\":1,\"fontsize\":\"15px\",\"title\":null},{\"name\":\"real\",\"group\":1,\"fontsize\":\"15px\",\"title\":null}],\"links\":[{\"source\":0,\"target\":1,\"value\":1},{\"source\":0,\"target\":2,\"value\":1},{\"source\":0,\"target\":3,\"value\":1},{\"source\":0,\"target\":4,\"value\":1},{\"source\":0,\"target\":5,\"value\":1},{\"source\":1,\"target\":2,\"value\":1},{\"source\":1,\"target\":3,\"value\":1},{\"source\":1,\"target\":5,\"value\":1},{\"source\":1,\"target\":6,\"value\":1},{\"source\":2,\"target\":3,\"value\":1},{\"source\":2,\"target\":4,\"value\":1},{\"source\":2,\"target\":5,\"value\":1},{\"source\":3,\"target\":5,\"value\":1},{\"source\":3,\"target\":8,\"value\":1},{\"source\":4,\"target\":5,\"value\":1},{\"source\":4,\"target\":6,\"value\":1},{\"source\":4,\"target\":11,\"value\":1},{\"source\":5,\"target\":6,\"value\":1},{\"source\":6,\"target\":2,\"value\":1},{\"source\":6,\"target\":11,\"value\":1},{\"source\":6,\"target\":18,\"value\":1},{\"source\":8,\"target\":0,\"value\":1},{\"source\":8,\"target\":2,\"value\":1},{\"source\":8,\"target\":14,\"value\":1},{\"source\":9,\"target\":0,\"value\":1},{\"source\":9,\"target\":1,\"value\":1},{\"source\":9,\"target\":2,\"value\":1},{\"source\":9,\"target\":3,\"value\":1},{\"source\":9,\"target\":8,\"value\":1},{\"source\":11,\"target\":0,\"value\":1},{\"source\":11,\"target\":1,\"value\":1},{\"source\":11,\"target\":2,\"value\":1},{\"source\":11,\"target\":3,\"value\":1},{\"source\":12,\"target\":0,\"value\":1},{\"source\":12,\"target\":1,\"value\":1},{\"source\":12,\"target\":2,\"value\":1},{\"source\":12,\"target\":3,\"value\":1},{\"source\":12,\"target\":14,\"value\":1},{\"source\":14,\"target\":0,\"value\":1},{\"source\":14,\"target\":1,\"value\":1},{\"source\":14,\"target\":2,\"value\":1},{\"source\":14,\"target\":3,\"value\":1},{\"source\":14,\"target\":5,\"value\":1},{\"source\":16,\"target\":0,\"value\":1},{\"source\":16,\"target\":1,\"value\":1},{\"source\":16,\"target\":2,\"value\":1},{\"source\":16,\"target\":9,\"value\":1},{\"source\":16,\"target\":11,\"value\":1},{\"source\":17,\"target\":0,\"value\":1},{\"source\":17,\"target\":1,\"value\":1},{\"source\":17,\"target\":2,\"value\":1},{\"source\":17,\"target\":3,\"value\":1},{\"source\":18,\"target\":2,\"value\":1},{\"source\":18,\"target\":4,\"value\":1},{\"source\":18,\"target\":5,\"value\":1},{\"source\":18,\"target\":11,\"value\":1},{\"source\":19,\"target\":0,\"value\":1},{\"source\":19,\"target\":1,\"value\":1},{\"source\":19,\"target\":2,\"value\":1},{\"source\":19,\"target\":3,\"value\":1},{\"source\":19,\"target\":5,\"value\":1}]}";

    json = htmlDecode(json);

    json = $.parseJSON(json);

    svg.append("svg:rect").attr("width", width).attr("height", height).style("stroke", "#fff").style("fill", "#fff");

    force.nodes(json.nodes).links(json.links).gravity(0.05).linkDistance(120).charge(-200).start();

    var node = svg.selectAll(".node").data(json.nodes).enter().append("g").attr("class", "node");
    var link = svg.selectAll(".link").data(json.links).enter().append("line").attr("class", "link").style("stroke-opacity", …

我是C#的新手,并且很难计算凸包.C#是否有某种数学库？如果没有,那么我想我只需要实现自己的.

我知道在ggplot2一个人可以按照组中的方式将凸包添加到散点图中

library(ggplot2)
library(plyr)
data(iris)
df<-iris
find_hull <- function(df) df[chull(df$Sepal.Length, df$Sepal.Width), ]
hulls <- ddply(df, "Species", find_hull)
plot <- ggplot(data = df, aes(x = Sepal.Length, y = Sepal.Width, colour=Species, fill = Species)) +
    geom_point() + 
    geom_polygon(data = hulls, alpha = 0.5) +
    labs(x = "Sepal.Length", y = "Sepal.Width")
plot

我想知道如何计算并添加alpha包,即最大的凸包,其中至少包含所有点的1-alpha比例？在2d(用ggplot2显示)或3d(用rgl显示).

编辑:我最初的想法是继续"剥离"凸包,因为包含至少一个给定百分点的标准将被满足,尽管在这里的论文中它似乎使用不同的算法(isodepth,这似乎是在R包深度中实现的,在函数isodepth和aplpack :: plothulls似乎也接近我想要的(虽然它产生一个完整的情节而不仅仅是轮廓),所以我想这些我可能会被排序.虽然这些功能仅适用于2D,我也会对3D扩展感兴趣(在rgl中绘制).如果有人有任何指针,请告诉我!

EDIT2:有功能depth::isodepth我找到了一个2d解决方案(见下面的帖子),虽然我还在寻找3D解决方案 - 如果有人碰巧知道如何做到这一点,请告诉我!

建立

给定凸包内的一些节点集,假设该域包含一个或多个凹面区域:

其中蓝点是点,黑线表示域.假设点被保持为points长度的2D数组n,其中n是点对的数量.

然后让我们使用类似scipy.spatial的Delaunay方法对点进行三角测量:

如您所见,人们可能会遇到穿过域的三角形的创建.

题

删除任何跨越域外的三角形的好算法方法是什么？理想但不一定,单面边缘仍然保留域形状(即,没有去除三角形的主要间隙).

由于我的问题似乎继续得到大量的活动,我想跟进我目前正在使用的应用程序.

假设您已定义边界,则可以使用光线投射算法来确定多边形是否在域内.

去做这个:

1. 取每个多边形的质心为C_i = (x_i,y_i).
2. 然后,想象一条线L = [C_i,(+inf,y_i)]:也就是说,一条横跨东部超过域末端的线.
3. 对于边界s_i中的每个边界段S,检查交叉点L.如果是,请向内部计数器添加+1 intersection_count; 否则,什么都不添加.

4. 后之间的所有交叉点的数量L和s_i for i=1..N计算:

   if intersection_count % 2 == 0:
       return True # triangle outside convex hull
   else:
       return False # triangle inside convex hull
   

   Run Code Online (Sandbox Code Playgroud)

如果没有明确定义边界,我发现将形状"映射"到布尔数组并使用邻居跟踪算法来定义它是有帮助的.请注意,此方法假设一个实体域,您需要对其中包含"漏洞"的域使用更复杂的算法.

我正在尝试计算并显示 python 中一些随机点的凸包。

这是我当前的代码：

import numpy as np
import random
import matplotlib.pyplot as plt
import cv2

points = np.random.rand(25,2)   

hull = ConvexHull(points)

plt.plot(points[:,0], points[:,1], 'o',color='c')

for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'r')

plt.plot(points[hull.vertices,0], points[hull.vertices,1], 'r', lw=-1)
plt.plot(points[hull.vertices[0],0], points[hull.vertices[0],1], 'r-')
plt.show()

我的问题：

• 如何在 0 到 9 之间更改 X、Y 标签和点数限制？例如（0,1,2,3,4,5,6,7,8,9）
• 如何用圆标记凸包上的点？ 如示例所示

我正在尝试使用scipy(0.10.1)来快速破解凸形船体.

我可以使用以下代码获取凸包:

vecs = [[-0.094218, 51.478927], [-0.09348,  51.479364], [-0.094218, 51.478927],
        ...
        [-0.094218, 51.478927], [-0.094321, 51.479918], [-0.094218, 51.478927],
        [-0.094222, 51.478837], [-0.094241, 51.478388], [-0.094108, 51.478116],
        [-0.09445,  51.480279], [-0.094256, 51.478028], [-0.094326, 51.500511]]
hull = scipy.spatial.Delaunay(vecs).convex_hull

结果数组如下所示:

[[56,  9], [16,  1], [56,  1], [55,  9], [53, 55], [53, 16]]

数字是顶点索引.我的问题是他们没有订购.我需要它们处于CW或CCW顺序,以便在KML中轻松地将它们可视化.

是否有任何简单的方法让scipy.spatial计算正确的顺时针顺序？

我在np.array中有一个3D点列表pointsList,值为float:

[[1., 2., 10.],
 [2., 0., 1.],
 [3., 6., 9.],
 [1., 1., 1.],
 [2., 2., 2.],
 [10., 0., 10.],
 [0., 10., 5.],
... etc.

此代码使得Delaunay对点云进行三角测量:

import numpy as np
import scipy.spatial 

tri = scipy.spatial.Delaunay(pointsList) 
# Delaunay triangulation

indices = tri.simplices
# indices of vertices

vertices = points[indices]
# the vertices for each tetrahedron

但是,在三角测量步骤之前,我想从列表中删除凸包内部的所有点

解决方案是创建一个新的np.array命名shortlist,并将它们存储在那里.

但是scipy(或任何其他解决方案)的功能是什么呢？

我该如何编程这个操作？

谢谢

我正在完成一个项目，在该项目中我实现了一个暴力算法来解决凸包问题。我还需要为该算法创建视觉效果。我试图在 x 轴和 y 轴上创建一个范围从 (-100, 100) 的坐标平面，绘制完整集中的所有点，并在点之间动态绘制线条以创建凸包。例如，假设我有 4 个点：A(1, 1)、B(3,2)、C(2, 4) 和 D(1,3)。我想首先绘制所有这四个点，然后从 A 到 B，然后从 B 到 C，然后从 C 到 D，最后从 D 到 A 画一条线。到目前为止，我一直在尝试使用 JavaFX 来做到这一点折线图。

//        creating axis
        NumberAxis xAxis = new NumberAxis(-100, 100, 1);
        NumberAxis yAxis = new NumberAxis(-100, 100, 1);
//        creating chart
        LineChart<Number, Number> lineChart = new LineChart<>(xAxis, yAxis);

然后使用画线

   public static void populatePoints(List<Double []> points, LineChart lineChart) {
        XYChart.Series series = new XYChart.Series();
        series.setName("Points of set");
        for (Double[] point : points) { …