java计算点在圆内外_java – 在O((n s)log n中计算圆交叉点)

我会带着你远行 2022-11-08 14:24 128阅读 0赞

我试图弄清楚如何设计一个能够以O((n s)log n)复杂度完成此任务的算法.是交叉点的数量.我试过在网上搜索,却找不到东西.

无论如何,我意识到拥有一个好的数据结构是关键.我在java：TreeMap中使用Red Black Tree实现.我还使用着名的(？)扫描线算法来帮助我处理我的问题.

让我先解释一下我的设置.

我有一个调度程序.这是一个PriorityQueue,我的圈子根据最左边的坐标排序(升序). scheduler.next()基本上轮询PriorityQueue,返回下一个最左边的圆圈.

public Circle next()

\{ return this.pq.poll(); \}

我这里也有一个包含4n个事件点的数组.授予每个圆圈有2个事件点：大多数左x和最右x.调度程序有一个方法sweepline()来获取下一个事件点.

public Double sweepline()

\{ return this.schedule\[pointer++\]; \}

我也有状态.扫描线状态更加精确.根据该理论,状态包含有资格相互比较的圆圈.在整个故事中拥有扫描线的关键在于你能够排除很多候选人,因为他们根本不在当前圈子的半径范围内.

我使用TreeMap< Double,Circle>实现了Status. Double是circle.getMostLeftCoord().

此TreeMap保证O(log n)用于插入/删除/查找.

算法本身的实现方式如下：

Double sweepLine = scheduler.sweepline();

Circle c = null;

while (notDone)\{

while((!scheduler.isEmpty()) && (c = scheduler.next()).getMostLeftCoord() >= sweepLine)

status.add(c);

/\*

\* Delete the oldest circles that the sweepline has left behind

\*/

while(status.oldestCircle().getMostRightCoord() < sweepLine)

status.deleteOldest();

Circle otherCircle;

for(Map.Entry entry: status.keys())\{

otherCircle = entry.getValue();

if(!c.equals(otherCircle))\{

Intersection\[\] is = Solver.findIntersection(c, otherCircle);

if(is != null)

for(Intersection intersection: is)

intersections.add(intersection);

\}

\}

sweepLine = scheduler.sweepline();

\}

编辑：Solver.findIntersection(c,otherCircle);返回最多2个交叉点.重叠的圆圈不被认为有任何交叉点.

SweepLineStatus的代码

public class BetterSweepLineStatus \{

TreeMap status = new TreeMap();

public void add(Circle c)

\{ this.status.put(c.getMostLeftCoord(), c); \}

public void deleteOldest()

\{ this.status.remove(status.firstKey()); \}

public TreeMap circles()

\{ return this.status; \}

public Set> keys()

\{ return this.status.entrySet(); \}

public Circle oldestCircle()

\{ return this.status.get(this.status.firstKey()); \}

我测试了我的程序,我显然有O(n ^ 2)的复杂性.

我在这里想念的是什么？您可能提供的任何输入都非常受欢迎.

提前致谢！

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关轮廓圆度计算方式

Halcon中圆度计算方式设p为区域中心点（质点），p\_i为轮廓上全部像素点，F为轮廓面积（此处指轮廓像素点个数，并不是轮廓所围成区域的面积） ![201912031

心已赠人/ 2023年05月21日 15:27/ 0 赞/ 7 阅读

相关计算圆面上的点到圆心的距离

实验要求计算圆面上的点到圆心的距离，必须对用户输入的点坐标进行判断，如果不是圆面上的点坐标，显示错误信息。实验原理放置好窗体控件后，定义double型变量x

心已赠人/ 2023年02月17日 12:25/ 0 赞/ 5 阅读

相关利用Java计算圆的面积

计算圆的面积 import java.util.Scanner; public class yuan { pu

我不是女神ヾ/ 2022年11月22日 12:41/ 0 赞/ 210 阅读

相关 Java学习之计算圆面积

我们在Java学习中会遇到计算圆面积的案例，下面这个案例是通过调用nextDouble()方法来读取带小数点的半径值。案例代码： import java.util

╰半夏微凉°/ 2022年11月11日 05:23/ 0 赞/ 189 阅读

相关 java计算点在圆内外_java – 在O((n s)log n中计算圆交叉点)

我试图弄清楚如何设计一个能够以O((n s)log n)复杂度完成此任务的算法.是交叉点的数量.我试过在网上搜索,却找不到东西. 无论如何,我意识到拥有一个好的数据结构是关键

我会带着你远行/ 2022年11月08日 14:24/ 0 赞/ 129 阅读

相关 java 计算圆的面积_java使用对象计算圆的面积

普通的计算圆的面积 ![4eaa0f4e9a0852d67dac363478b5f007.png][] public class ComputerCircleArea \{

Dear 丶/ 2022年11月02日 06:51/ 0 赞/ 228 阅读

相关 Java：计算圆的面积和周长

import java.util.Scanner; public class yuan \{ public static void main(String\[\] ar

淡淡的烟草味﹌/ 2022年06月07日 10:40/ 0 赞/ 375 阅读

相关 Java小程序-计算圆的面积

import java.util.Scanner; public class ComputeArea {//从控制台输入圆的半径，输出圆的面积

àì夳堔傛蜴生んèń/ 2022年05月21日 07:19/ 0 赞/ 212 阅读

相关计算圆

import java.util.\; public class Yuan \{ float r;//变量 float pai=(float) 3.14; vo

川长思鸟来/ 2022年05月15日 12:34/ 0 赞/ 211 阅读

相关 javascript 判断点在面内，点在圆内

点在多边形内常用的算法就是使用射线法，作为笔记直接上代码： / 判断一个点是否在多边形内部 @param points

傷城~/ 2022年01月30日 05:55/ 0 赞/ 342 阅读