修改凸包以排除不需要的点

在我的C＃-Silverlight 3程序中，我有一组点。这些点可以是不同的颜色，绿色，红色或蓝色。然后我为不同的点创建一个凸包：一个绿色的船体，一个红色的船体和一个蓝色的船体。现在它可能发生，每种颜色的船体内都是来自另一种颜色的点，例如绿色船体内的红色点。修改凸包以排除不需要的点

是否有任何算法来修改船体，以便那些其他颜色的点将从船体中排除（此时不再凸出）？

由于提前，弗兰克

2009-10-20 Aaginor

你是什么意思排除？你的意思是删除这些点？但是，删除某些点时，可能会“破坏”现有的凸包。当绿色凸包的所有点位于红色凸包内时会发生什么？需要更多的细节来回答这个问题。一个具体的例子也会有帮助。 – 2009-11-08 20:48:12

通过“打破”一个凸包，我的意思是移除凸包中5个点的3个，因为这3个点位于另一个船体内部。然后你最终得到2个不能成为凸包的剩余点。 – 2009-11-08 20:49:46

翻译成经典的旅行商问题。

使用生成此船体的点并添加您希望它们排除的其他点。现在找到了这个点shotrest路径和你有这样的新船体

编辑

我们需要找到过点之一noncrossing路径。

复杂性，现在是N *日志（N）

2009-10-20 13:42:36

密码回答，但正确的结论是：这是一个NP难题。 – 2012-11-30 02:51:54

@Clint Tseng我现在在想，这是没有必要的，一旦你找到了这个排除在外的路径，那么它就是最好的。它只是为了体现。在点上寻找非交叉路径最差N * log（N）。 – 2012-11-30 17:36:39

我自从发现http://research.cs.queensu.ca/home/daver/Pubs/MyPDF/CCMSP_EadesRappaport.pdf，这可能会对您感兴趣。 :) – 2013-01-09 03:07:05

回答