维护围绕中心点的点列表，保持CCW顺序 [英] Maintain a list of points around a center point, preserving CCW order

问题描述

我有以下类：

  public class Vertex（）{
 private double xCoord; 
私人双yCoord; 
 private ArrayList< Vertex> neighborList（）; 
} 
  

我想支持在neighborList中添加/删除顶点，以CCW顺序在该顶点周围列出（该列表中的第一个并不重要）。如果点是共线的，则应该先指出这一点。我已经尝试了几种方法，但到目前为止总能找到一个不适用于给定方法的反例。

如何以简单高效的方式做到这一点？

解决方案

以极坐标形式表示点坐标

  t = atan2（Y-Yo，X-Xo）
r = sqrt（（X-Xo）^ 2 +（Y-Yo） ^ 2）
  

并在角度和半径上使用字典排序。

I have the following class:

 public class Vertex() {
    private double xCoord;
    private double yCoord;
    private ArrayList<Vertex> neighborList();
 }

And I want to support adding/removing vertices to the neighborList such that the points are listed in CCW order around this vertex (which point is first in the list doesn't matter). If points are collinear, nearer points to this should be first. I've tried several methods but so far have always been able to find a counter example that doesn't work for the given method.

Does anyone have a good idea of how to do this in a simple and efficient manner?

解决方案

Express the point coordinates in the polar form

t = atan2(Y-Yo, X-Xo)
r = sqrt((X-Xo)^2 + (Y-Yo)^2)

and use lexicographical ordering on angle then radius.

这篇关于维护围绕中心点的点列表，保持CCW顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！