다각형 점 목록이 시계 방향인지 확인하는 방법?
포인트 목록이 있는데 시계 방향인지 어떻게 알 수 있습니까?
예를 들면 다음과 같습니다.
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
시계 반대 방향 (또는 일부 사람들에게는 시계 반대 방향)이라고 말할 것입니다.
초승달 모양과 같은 볼록하지 않은 다각형의 경우 제안 된 방법 중 일부가 실패합니다. 다음은 볼록하지 않은 다각형에서 작동하는 간단한 것입니다 (그림 8과 같이 자체 교차 다각형에서도 작동하여 대부분 시계 방향 인지 여부를 알려줍니다 ).
모서리에 대한 합, (x 2 -x 1 ) (y 2 + y 1 ). 결과가 양수이면 곡선은 시계 방향이고, 음수이면 곡선은 시계 반대 방향입니다. (결과는 +/- 규칙으로 닫힌 영역의 두 배입니다.)
point[0] = (5,0) edge[0]: (6-5)(4+0) = 4
point[1] = (6,4) edge[1]: (4-6)(5+4) = -18
point[2] = (4,5) edge[2]: (1-4)(5+5) = -30
point[3] = (1,5) edge[3]: (1-1)(0+5) = 0
point[4] = (1,0) edge[4]: (5-1)(0+0) = 0
---
-44 counter-clockwise
외적은 두 벡터의 수직 다움의 정도를 측정한다. 다각형의 각 가장자리가 3 차원 xyz 공간의 xy 평면에있는 벡터라고 가정합니다. 그런 다음 두 개의 연속 모서리의 교차 곱은 z 방향의 벡터입니다 (두 번째 세그먼트가 시계 방향이면 양수 z 방향, 반 시계 방향이면 z 방향 빼기). 이 벡터의 크기는 두 개의 원래 가장자리 사이의 각도 사인에 비례하므로 가장자리가 직각 일 때 최대 값에 도달하고 가장자리가 동일 선상에있을 때 테이퍼링이 사라집니다 (병렬).
따라서 다각형의 각 정점 (점)에 대해 두 개의 인접한 모서리의 곱의 크기를 계산합니다.
Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)
그래서 연속 에지 라벨
edgeA의 세그먼트 point0로 point1및
edgeB사이 point1에이 point2
...
edgeE사이 point4와 point0.
그런 다음 정점 A ( point0)는
edgeE[From point4to point0]
edgeA[From point0to`point1 '사이에 있습니다.
이 두 가장자리는 그 자체로 벡터이며, 시작점과 끝점의 좌표를 빼서 x 및 y 좌표를 결정할 수 있습니다.
edgeE= point0- point4= (1, 0) - (5, 0)= (-4, 0)및
edgeA= point1- point0= (6, 4) - (1, 0)= (5, 4)및
이 두 인접한 모서리의 곱은 좌표축 세를 나타내는 기호 아래 두 벡터의 좌표를 넣어 구성되어 다음과 같은 행렬의 행렬식을 계산한다 ( i, j, k). 교차 곱 개념이 3 차원 구조이기 때문에 세 번째 값이 0 인 좌표가 있으므로 교차 곱을 적용하기 위해 이러한 2 차원 벡터를 3 차원으로 확장합니다.
i j k
-4 0 0
1 4 0
모든 교차 곱이 곱해지는 두 벡터의 평면에 수직 인 벡터를 생성한다고 가정하면, 위의 행렬 결정 k요소 에는 , 또는 z 축 성분 만 있습니다. z 축 구성 요소
의 크기를 계산하는 공식 k은
a1*b2 - a2*b1 = -4* 4 - 0* 1=-16
이 값의 크기 ( -16)는 2 개의 원래 벡터 사이의 각도의 사인 값에 2 개의 벡터 크기의 곱을 곱한 값입니다.
실제로 그 값에 대한 다른 공식은
A X B (Cross Product) = |A| * |B| * sin(AB)입니다.
따라서 각도 측정으로 돌아가려면이 값 ( -16)을 두 벡터 크기의 곱으로 나눠야합니다 .
|A| * |B|= 4 * Sqrt(17)=16.4924...
따라서 sin (AB) = -16 / 16.4924=-.97014...
이것은 정점 뒤의 다음 세그먼트가 왼쪽 또는 오른쪽으로 구부러 졌는지 여부와 그 정도를 측정 한 것입니다. 아크 사인을 취할 필요가 없습니다. 우리가 관심을 가질 것은 그 규모뿐 아니라 물론 그 징후 (긍정적이든 부정적이든)입니다!
닫힌 패스 주위의 다른 4 개의 점마다이 작업을 수행하고 각 정점에서이 계산의 값을 더합니다.
최종 합이 양수이면 시계 방향, 음수, 시계 반대 방향으로 이동합니다.
나는 이것이 꽤 오래된 질문이라고 생각하지만, 간단하고 수학적으로 집중적이지 않기 때문에 어쨌든 다른 솔루션을 버릴 것입니다. 기본 대수학 만 사용합니다. 다각형의 부호있는 영역을 계산하십시오. 음수이면 포인트가 시계 방향이며 양수이면 반 시계 방향입니다. (베타의 솔루션과 매우 유사합니다.)
부호있는 영역을 계산합니다. A = 1/2 * (x 1 * y 2 -x 2 * y 1 + x 2 * y 3 -x 3 * y 2 + ... + x n * y 1 -x 1 * y n )
또는 의사 코드에서 :
signedArea = 0
for each point in points:
x1 = point[0]
y1 = point[1]
if point is last point
x2 = firstPoint[0]
y2 = firstPoint[1]
else
x2 = nextPoint[0]
y2 = nextPoint[1]
end if
signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2
주문 만 확인하는 경우 2로 나눌 필요가 없습니다.
출처 : http://mathworld.wolfram.com/PolygonArea.html
y가 가장 작은 정점을 찾으십시오 (동점이있는 경우 가장 큰 x). 정점하자 A하고 목록에서 이전 정점 수 B와 목록의 다음 정점 수 C. 이제 계산 기호 의 십자가 제품을 AB하고 AC.
참고 문헌 :
간단한 다각형의 방향을 어떻게 찾습니까? 에서 자주 묻는 질문 : comp.graphics.algorithms를 .
Wikipedia의 커브 방향 .
이 답변을 기반으로 한 알고리즘의 간단한 C # 구현은 다음과 같습니다 .
Vector유형 X과 Y유형의 속성 이 있다고 가정 해 봅시다 double.
public bool IsClockwise(IList<Vector> vertices)
{
double sum = 0.0;
for (int i = 0; i < vertices.Count; i++) {
Vector v1 = vertices[i];
Vector v2 = vertices[(i + 1) % vertices.Count];
sum += (v2.X - v1.X) * (v2.Y + v1.Y);
}
return sum > 0.0;
}
%는 Wikipedia에 따르면 모듈 을 다른 숫자로 나눈 후 나머지를 찾는 모듈로 연산을 수행하는 모듈로 또는 나머지 연산자 입니다.
꼭짓점 중 하나에서 시작하여 각 변의 각도를 계산하십시오.
첫 번째와 마지막은 0입니다 (그래서 건너 뛰십시오). 나머지의 경우, 각도의 사인은 정규화의 교차 곱에 의해 (point [n] -point [0]) 및 (point [n-1] -point [0])의 단위 길이로 주어집니다.
값의 합이 양수이면 다각형이 시계 반대 방향으로 그려집니다.
가치있는 점을 위해이 믹스 인을 사용하여 Google Maps API v3 앱의 와인딩 순서를 계산했습니다.
이 코드는 다각형 영역의 부작용을 활용합니다. 꼭지점의 시계 방향 권선 순서는 양수 영역을 생성하는 반면 동일한 꼭지점의 시계 반대 방향 권선 순서는 음수 값과 동일한 영역을 생성합니다. 이 코드는 또한 Google Maps 지오메트리 라이브러리에서 일종의 개인 API를 사용합니다. 나는 그것을 사용하는 것이 편안하다고 생각했습니다.
샘플 사용법 :
var myPolygon = new google.maps.Polygon({/*options*/});
var isCW = myPolygon.isPathClockwise();
단위 테스트 @ http://jsfiddle.net/stevejansen/bq2ec/의 전체 예
/** Mixin to extend the behavior of the Google Maps JS API Polygon type
* to determine if a polygon path has clockwise of counter-clockwise winding order.
*
* Tested against v3.14 of the GMaps API.
*
* @author stevejansen_github@icloud.com
*
* @license http://opensource.org/licenses/MIT
*
* @version 1.0
*
* @mixin
*
* @param {(number|Array|google.maps.MVCArray)} [path] - an optional polygon path; defaults to the first path of the polygon
* @returns {boolean} true if the path is clockwise; false if the path is counter-clockwise
*/
(function() {
var category = 'google.maps.Polygon.isPathClockwise';
// check that the GMaps API was already loaded
if (null == google || null == google.maps || null == google.maps.Polygon) {
console.error(category, 'Google Maps API not found');
return;
}
if (typeof(google.maps.geometry.spherical.computeArea) !== 'function') {
console.error(category, 'Google Maps geometry library not found');
return;
}
if (typeof(google.maps.geometry.spherical.computeSignedArea) !== 'function') {
console.error(category, 'Google Maps geometry library private function computeSignedArea() is missing; this may break this mixin');
}
function isPathClockwise(path) {
var self = this,
isCounterClockwise;
if (null === path)
throw new Error('Path is optional, but cannot be null');
// default to the first path
if (arguments.length === 0)
path = self.getPath();
// support for passing an index number to a path
if (typeof(path) === 'number')
path = self.getPaths().getAt(path);
if (!path instanceof Array && !path instanceof google.maps.MVCArray)
throw new Error('Path must be an Array or MVCArray');
// negative polygon areas have counter-clockwise paths
isCounterClockwise = (google.maps.geometry.spherical.computeSignedArea(path) < 0);
return (!isCounterClockwise);
}
if (typeof(google.maps.Polygon.prototype.isPathClockwise) !== 'function') {
google.maps.Polygon.prototype.isPathClockwise = isPathClockwise;
}
})();
JavaScript에서 Sean의 답변 구현 :
function calcArea(poly) {
if(!poly || poly.length < 3) return null;
let end = poly.length - 1;
let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
for(let i=0; i<end; ++i) {
const n=i+1;
sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
}
return sum;
}
function isClockwise(poly) {
return calcArea(poly) > 0;
}
let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];
console.log(isClockwise(poly));
let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];
console.log(isClockwise(poly2));이것이 옳다는 것을 확신하십시오. 작동하는 것 같습니다 :-)
궁금한 점이 있다면 해당 다각형은 다음과 같습니다.
Matlab을 사용하는 ispolycw경우이 함수 는 다각형 정점이 시계 방향으로되어 있으면 true를 반환합니다.
이것은 OpenLayers 2에 대해 구현 된 기능입니다 . 시계 방향 다각형을 갖는 조건은 이 참조에area < 0 의해 확인됩니다 .
function IsClockwise(feature)
{
if(feature.geometry == null)
return -1;
var vertices = feature.geometry.getVertices();
var area = 0;
for (var i = 0; i < (vertices.length); i++) {
j = (i + 1) % vertices.length;
area += vertices[i].x * vertices[j].y;
area -= vertices[j].x * vertices[i].y;
// console.log(area);
}
return (area < 0);
}
바와 같이이 위키 백과 문서에 설명 된 곡선 방향 3 점을 감안 p, q그리고 r비행기 (즉, x와 y 좌표)에 다음과 같은 결정의 부호를 계산할 수 있습니다
행렬식이 음수이면 (즉 Orient(p, q, r) < 0) 다각형이 시계 방향 (CW)을 향합니다. 결정자가 양수 (즉 Orient(p, q, r) > 0)이면 다각형은 시계 반대 방향 (CCW)을 향합니다. 행렬식이 제로 (예입니다 Orient(p, q, r) == 0) 점의 경우 p, q및 r있습니다 선상 .
상기 화학식에서는 좌표 앞에 덧붙이 것들 p, q및 r우리가 사용하기 때문에 균일 한 좌표 .
일부 포인트를 시계 방향으로 제공하려면 모든 에지가 에지의 합뿐만 아니라 양수이어야한다고 생각합니다. 하나의 모서리가 음수 인 경우 시계 반대 방향으로 3 점 이상이 지정됩니다.
내 C # / LINQ 솔루션은 @charlesbretana의 교차 제품 조언을 기반으로합니다. 권선에 대한 기준 법선을 지정할 수 있습니다. 커브가 대부분 위쪽 벡터에 의해 정의 된 평면에있는 한 작동합니다.
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace SolidworksAddinFramework.Geometry
{
public static class PlanePolygon
{
/// <summary>
/// Assumes that polygon is closed, ie first and last points are the same
/// </summary>
public static bool Orientation
(this IEnumerable<Vector3> polygon, Vector3 up)
{
var sum = polygon
.Buffer(2, 1) // from Interactive Extensions Nuget Pkg
.Where(b => b.Count == 2)
.Aggregate
( Vector3.Zero
, (p, b) => p + Vector3.Cross(b[0], b[1])
/b[0].Length()/b[1].Length());
return Vector3.Dot(up, sum) > 0;
}
}
}
단위 테스트
namespace SolidworksAddinFramework.Spec.Geometry
{
public class PlanePolygonSpec
{
[Fact]
public void OrientationShouldWork()
{
var points = Sequences.LinSpace(0, Math.PI*2, 100)
.Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0))
.ToList();
points.Orientation(Vector3.UnitZ).Should().BeTrue();
points.Reverse();
points.Orientation(Vector3.UnitZ).Should().BeFalse();
}
}
}
이것은 다른 답변의 설명을 사용하는 솔루션입니다.
def segments(poly):
"""A sequence of (x,y) numeric coordinates pairs """
return zip(poly, poly[1:] + [poly[0]])
def check_clockwise(poly):
clockwise = False
if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
clockwise = not clockwise
return clockwise
poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False
poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True
다각형 내부의 점을 이미 알고 있다면 훨씬 계산적으로 간단한 방법입니다 .
원래 다각형, 점 및 좌표에서 순서대로 선분을 선택하십시오.
알려진 "내부"점을 추가하고 삼각형을 형성하십시오.
신뢰할 수없는 몇 가지 구현을 테스트 한 후 CW / CCW 방향과 관련하여 만족스러운 결과를 제공 한 알고리즘 이이 스레드 에 OP로 게시되었습니다 ( shoelace_formula_3).
항상 그렇듯이 양수는 CW 방향을 나타내는 반면 음수는 CCW를 나타냅니다.
위의 답변을 기반으로 한 신속한 3.0 솔루션은 다음과 같습니다.
for (i, point) in allPoints.enumerated() {
let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
}
let clockwise = signedArea < 0
이것에 대한 또 다른 해결책;
const isClockwise = (vertices=[]) => {
const len = vertices.length;
const sum = vertices.map(({x, y}, index) => {
let nextIndex = index + 1;
if (nextIndex === len) nextIndex = 0;
return {
x1: x,
x2: vertices[nextIndex].x,
y1: x,
y2: vertices[nextIndex].x
}
}).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);
if (sum > -1) return true;
if (sum < 0) return false;
}
모든 정점을 이와 같은 배열로 가져옵니다.
const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);
R이 방향을 결정하고 시계 방향으로 방향을 바꾸는 해결책 (Owin 객체에 필요함) :
coords <- cbind(x = c(5,6,4,1,1),y = c(0,4,5,5,0))
a <- numeric()
for (i in 1:dim(coords)[1]){
#print(i)
q <- i + 1
if (i == (dim(coords)[1])) q <- 1
out <- ((coords[q,1]) - (coords[i,1])) * ((coords[q,2]) + (coords[i,2]))
a[q] <- out
rm(q,out)
} #end i loop
rm(i)
a <- sum(a) #-ve is anti-clockwise
b <- cbind(x = rev(coords[,1]), y = rev(coords[,2]))
if (a>0) coords <- b #reverses coords if polygon not traced in anti-clockwise direction
이 답변은 정확하지만 필요한 것보다 수학적으로 더 강렬합니다. 지도에서 가장 북쪽이 가장 높은 지점 인지도 좌표를 가정합니다. 가장 북쪽을 찾은 다음 2 점이 동점 인 경우 가장 북쪽이 가장 동쪽입니다 (이것은 lhf가 그의 대답에 사용하는 지점입니다). 당신의 요점에서
점 [0] = (5,0)
점 [1] = (6,4)
점 [2] = (4,5)
점 [3] = (1,5)
점 [4] = (1,0)
P2가 가장 북쪽에 있고 동쪽에 있다고 가정하면 이전 또는 다음 점이 시계 방향, CW 또는 CCW를 결정합니다. 가장 북쪽이 북쪽에 있으므로 P1 (이전)에서 P2까지 동쪽으로 이동하면 방향은 CW입니다. 이 경우 서쪽으로 이동하므로 허용되는 대답에 따라 방향은 CCW입니다. 이전 점에 수평 이동이 없으면 같은 시스템이 다음 점 P3에 적용됩니다. P3이 P2의 서쪽이면, 그 움직임은 CCW입니다. P2에서 P3 로의 움직임이 동쪽이면이 경우 서쪽입니다. 움직임은 CW입니다. 데이터에서 nte, P2가 가장 북쪽 다음 동쪽 포인트이고 prv가 이전 점, 데이터에서 P1이고 nxt가 다음 포인트, P3이고 데이터 [0]이 가로 또는 동쪽 /이라고 가정합니다. 서쪽은 동쪽보다 작고 [1]은 수직입니다.
if (nte[0] >= prv[0] && nxt[0] >= nte[0]) return(CW);
if (nte[0] <= prv[0] && nxt[0] <= nte[0]) return(CCW);
// Okay, it's not easy-peasy, so now, do the math
if (nte[0] * nxt[1] - nte[1] * nxt[0] - prv[0] * (nxt[1] - crt[1]) + prv[1] * (nxt[0] - nte[0]) >= 0) return(CCW); // For quadrant 3 return(CW)
return(CW) // For quadrant 3 return (CCW)
lhf의 답변 을 구현하는 C # 코드 :
// https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
int nVerts = vertices.Count;
// If vertices duplicates first as last to represent closed polygon,
// skip last.
Vector2 lastV = vertices[nVerts - 1];
if (lastV.Equals(vertices[0]))
nVerts -= 1;
int iMinVertex = FindCornerVertex(vertices);
// Orientation matrix:
// [ 1 xa ya ]
// O = | 1 xb yb |
// [ 1 xc yc ]
Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
Vector2 b = vertices[iMinVertex];
Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
// determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);
// TBD: check for "==0", in which case is not defined?
// Can that happen? Do we need to check other vertices / eliminate duplicate vertices?
WindingOrder result = detOrient > 0
? WindingOrder.Clockwise
: WindingOrder.CounterClockwise;
return result;
}
public enum WindingOrder
{
Clockwise,
CounterClockwise
}
// Find vertex along one edge of bounding box.
// In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
int iMinVertex = -1;
float minY = float.MaxValue;
float minXAtMinY = float.MaxValue;
for (int i = 0; i < vertices.Count; i++)
{
Vector2 vert = vertices[i];
float y = vert.Y;
if (y > minY)
continue;
if (y == minY)
if (vert.X >= minXAtMinY)
continue;
// Minimum so far.
iMinVertex = i;
minY = y;
minXAtMinY = vert.X;
}
return iMinVertex;
}
// Return value in (0..n-1).
// Works for i in (-n..+infinity).
// If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
// "+n": Moves (-n..) up to (0..).
return (i + n) % n;
}
이 점들의 질량 중심을 찾으십시오.
이 시점에서 현재 시점까지 선이 있다고 가정하십시오.
line0에 대한 두 줄 사이의 각도를 찾으십시오.
line1과 line2보다
...
...
이 각도가 시계 반대 방향보다 단조 증가하는 경우
그렇지 않으면 단조로 감소하면 시계 방향입니다
그렇지 않은 경우 (단조가 아님)
당신은 결정할 수 없으므로 현명하지 않습니다
'IT story' 카테고리의 다른 글
| Android에서 TextView에 줄 바꿈을 어떻게 추가합니까? (0) | 2020.04.10 |
|---|---|
| Maven의 pom.xml에서 pluginManagement는 무엇입니까? (0) | 2020.04.10 |
| 디렉토리에서 필터링 된 파일 목록 가져 오기 (0) | 2020.04.10 |
| Visual Studio 코드의 메서드 목록 (0) | 2020.04.10 |
| Git에서 로컬 커밋을 버리는 방법? (0) | 2020.04.10 |