检查四个线段是否形成一个矩形

2022-09-20  乐帮网

数学

我们得到四个段作为它们端点的一对坐标。 我们需要判断这四个线段是否构成一个矩形。
例子:


Input : segments[] =  [(4, 2), (7, 5),
                       (2, 4), (4, 2),
                       (2, 4), (5, 7),
                       (5, 7), (7, 5)]
Output : Yes
Given these segment make a rectangle of length 3X2.

Input : segment[] = [(7, 0), (10, 0),
                     (7, 0), (7, 3),
                     (7, 3), (10, 2),
                     (10, 2), (10, 0)]
Output : Not
These segments do not make a rectangle.
Above examples are shown in below diagram.

这个问题主要是如何检查给定的四个点是否形成正方形的扩展。
我们可以通过使用矩形的属性来解决这个问题。 首先,我们检查线段的唯一端点总数,如果这些点的数量不等于 4,则线段不能构成矩形。 然后我们检查所有点对之间的距离,最多应该有 3 个不同的距离,一个是对角线,两个是边,最后我们将检查这三个距离之间的关系,对于制作矩形的线段,这些距离应该 满足毕达哥拉斯关系,因为矩形的边和对角线构成直角三角形。 如果它们满足上述条件,那么我们会将由线段制成的多边形标记为矩形,否则不会。

C++

// C++ program to check whether it is possible
// to make a rectangle from 4 segments
#include <bits/stdc++.h>
using namespace std;
#define N 4

// structure to represent a segment
struct Segment
{
	int ax, ay;
	int bx, by;
};

// Utility method to return square of distance
// between two points
int getDis(pair<int, int> a, pair<int, int> b)
{
	return (a.first - b.first)*(a.first - b.first) +
		(a.second - b.second)*(a.second - b.second);
}

// method returns true if line Segments make
// a rectangle
bool isPossibleRectangle(Segment segments[])
{
	set< pair<int, int> > st;

	// putting all end points in a set to
	// count total unique points
	for (int i = 0; i < N; i++)
	{
		st.insert(make_pair(segments[i].ax, segments[i].ay));
		st.insert(make_pair(segments[i].bx, segments[i].by));
	}

	// If total unique points are not 4, then
	// they can't make a rectangle
	if (st.size() != 4)
		return false;

	// dist will store unique 'square of distances'
	set<int> dist;

	// calculating distance between all pair of
	// end points of line segments
	for (auto it1=st.begin(); it1!=st.end(); it1++)
		for (auto it2=st.begin(); it2!=st.end(); it2++)
			if (*it1 != *it2)
				dist.insert(getDis(*it1, *it2));

	// if total unique distance are more than 3,
	// then line segment can't make a rectangle
	if (dist.size() > 3)
		return false;

	// copying distance into array. Note that set maintains
	// sorted order.
	int distance[3];
	int i = 0;
	for (auto it = dist.begin(); it != dist.end(); it++)
		distance[i++] = *it;

	// If line seqments form a square
	if (dist.size() == 2)
	return (2*distance[0] == distance[1]);

	// distance of sides should satisfy pythagorean
	// theorem
	return (distance[0] + distance[1] == distance[2]);
}

// Driver code to test above methods
int main()
{
	Segment segments[] =
	{
		{4, 2, 7, 5},
		{2, 4, 4, 2},
		{2, 4, 5, 7},
		{5, 7, 7, 5}
	};

	(isPossibleRectangle(segments))?cout << "Yes\n":cout << "No\n";
}

 

JavaScript:

// JavaScript program to check whether it is possible
// to make a rectangle from 4 segments

const N = 4;

// Utility method to return square of distance
// between two points
function getDis(a, b)
{
	return (parseInt(a[0]) - parseInt(b[0]))*(parseInt(a[0]) - parseInt(b[0])) + (parseInt(a[1]) - parseInt(b[1]))*(parseInt(a[1]) - parseInt(b[1]));
}

// method returns true if line Segments make
// a rectangle
function isPossibleRectangle(segments)
{
	let st = new Set();

	// putting all end points in a set to
	// count total unique points
	for (let i = 0; i < N; i++)
	{
		let tmp1 = [segments[i][0], segments[i][1]];
		let tmp2 = [segments[i][2], segments[i][3]];
		st.add(tmp1.join(''));
		st.add(tmp2.join(''));
	}

	// If total unique points are not 4, then
	// they can't make a rectangle
	if (st.size != 4)
	{
		return false;
	}
		
	// dist will store unique 'square of distances'
	let dist = new Set();

	// calculating distance between all pair of
	// end points of line segments
	for(let it1 of st)
	{
		for(let it2 of st)
		{
			if(it1 !== it2)
			{
				dist.add(getDis(it1.split(''), it2.split('')));
			}
		}
	}

	// if total unique distance are more than 3,
	// then line segment can't make a rectangle
	if (dist.size > 3)
	{
		return false;
	}
		
	// copying distance into array. Note that set maintains
	// sorted order.
	let distance = new Array();
	for (let x of dist)
	{
		distance.push(x);
	}
		
	// If line seqments form a square
	if (dist.size === 2)
	{
		return (2*distance[0] == distance[1]);
	}

	// distance of sides should satisfy pythagorean
	// theorem
	return (distance[0] + distance[1] == distance[2]);
}

// Driver code to test above methods
{
	let segments = [
		[4, 2, 7, 5],
		[2, 4, 4, 2],
		[2, 4, 5, 7],
		[5, 7, 7, 5] ]

	if(isPossibleRectangle(segments)){
		console.log("Yes");
	}
	else{
		console.log("No");
	}
}

// The code is contributed by Nidhi Goel

https://www.geeksforgeeks.org/check-four-segments-form-rectangle/?ref=lbp

公众号二维码

关注我的微信公众号
在公众号里留言交流
投稿邮箱:1052839972@qq.com

庭院深深深几许?杨柳堆烟,帘幕无重数。
玉勒雕鞍游冶处,楼高不见章台路。
雨横风狂三月暮。门掩黄昏,无计留春住。
泪眼问花花不语,乱红飞过秋千去。

欧阳修

付款二维码

如果感觉对您有帮助
欢迎向作者提供捐赠
这将是创作的最大动力