blocks|key|1121270|text|如果你不知道坐标是不可能的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1121271|对于第一个三角形，拾取任意三个点。不管是哪一个，你都会得到一个可行的三角形。|1121272|对于第二个三角形，找到“远”点并将其移除，代之以剩余的点。|1121273|诀窍是找到远端的点。由于您只有三个选项，因此只需执行两次检查即可确定是哪一个(如果不是前两个，就是第三个)。这差不多是你能得到的最高效率了。|1121274|给定第一个三角形(A,+B,+C)和第四个点D，远点是三角形中线段(A,+D)和(B,+C)相交的点(假设它是A)。就这么简单。|offset|length|style|CODE|1121275|请注意，这将适用于退化的四边形三角形，但不适用于直线段。也许它会，取决于你是如何定义工作的。|1121276|entityMap^0|0|0|0|0|8|9|M|1|X|6|14|6|1J|1|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|V|8|@$J|W|K|X|L|M]|$J|Y|K|Z|L|M]|$J|10|K|11|L|M]|$J|12|K|13|L|M]|$J|14|K|15|L|M]]|9|@]|A|$]]|$1|N|3|O|5|6|7|16|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|17|8|@]|9|@]|A|$]]]|Q|$]]

It's not possible if you don't know the coordinates.

For the first triangle, pick any three points. It doesn't matter which; you will get a workable triangle.

For the second triangle, find the "far" point and remove it, substituting the remaining point.

The trick is finding the far point. Since you only have three options, you only need to perform two checks to figure out which it is (if it's not the first two, it's the third). That's about as efficient as you're gonna get. 

Given the first triangle <code>(A, B, C)</code> and the fourth point <code>D</code>, the far point is the point in the triangle (pretend it's <code>A</code>) where the line segments <code>(A, D)</code> and <code>(B, C)</code> intersect. Simple as that.

Note that this will work with a degenerate quadrilateral triangle, but not with a line segment. Or maybe it will, depending on how you define working...

blocks|key|1121300|text|哦，好了，又来了一个作业...|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1121301|如果你对坐标一无所知，你可能就完蛋了。像v1，v2，v3和v2，v3，v4一样拆分它。你不能做比这更糟的了。如果您知道面积或以某种方式计算它们，请继续阅读。|1121302|4个点是4个三角形，构成一个四面体。你有它在平面上的投影。您需要拆分每个子集总面积相等的三角形集。您可能正在使用浮点数，因此让我们放宽拆分条件。你在寻找最小的绝对差。|1121303|让我们称三角形的面积为A，B，C，D：|1121304|总共有2%5E4/2种方法可以拆分三角形集。|1121305|如果A%2BB%2BC%2BD为最小值，则说明面积计算中存在错误，或者存在直线段。|1121306|如果像A-(B%2BC%2BD)这样的情况是最小的，那么您的多边形实际上是带有额外顶点的A。或者，如果你喜欢，你可以用B，C，D做3个四边形。|1121307|如果像(A%2BB)-(C%2BD)这样的情况是最小的，您可以选择A，B或C，D|1121308|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|V|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|W|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|X|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|Y|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|Q|$]]

Oh well, here goes another homework...

If you have no idea about the coordinates, you might be screwed. Split it like v1,v2,v3 and v2,v3,v4. You can't do worse than this. If you know the areas or calculate them somehow, read on.

4 points are 4 triangles which makes a tetrahedron. You have a projection of it on a plane. You need to split the triangle set where the total area of each subset is equal. Probably you are using floating points so let's relax the split condition. You are looking for the minimum absolute difference.

Let's call the areas of the triangles A, B, C, D:

There are total of 2^4/2 ways you can split the triangle set.

If A+B+C+D is minimum, you either have a bug in your area calculation or you have a line segment.

If a case like A-(B+C+D) is minimum, your polygon is actually A with an extra vertex. Alternatively, you can make 3 quadrilaterals out of B,C,D if you like.

If a case like (A+B)-(C+D) is minimum, you can pick A,B or C,D

blocks|key|3202896|text|如果你真的在尝试渲染这些，你应该在中间创建一个顶点，并制作4个三角形，其中一个顶点是中间点。否则我看不出(v1，v2，v3)，(v2，v3，v4)有什么问题|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3202897|编辑：|3202898|抱歉，我在想3D模式。这不适用。|3202899|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

If you are actually trying to render these, you should create a vertex in the middle and make 4 triangles with the middle point as one of the verts.
Otherwise I don't see whats wrong with going (v1, v2, v3), (v2, v3, v4)

[EDIT:]

Sorry, I'm thinking in 3D. This doesn't apply.

blocks|key|1121350|text|您需要将其分解为两个步骤：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1121351|1)按顺时针顺序对顶点进行排序。参见this+question+and+its+answers。|offset|length|1121352|2)找出四边形内的一条对角线(如果四边形是凹的，则只有一条在里面。如果是凸的，则两者都是)。参见this+question+and+its+answers。|1121353|一旦你得到了它，它应该是显而易见的如何找到这两个三角形。|1121354|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order|1|https://stackoverflow.com/questions/2816572/diagonal-of-polygon-is-inside-or-outside^0|0|I|T|0|0|1C|T|1|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@]|9|@$D|V|E|W|1|X]]|A|$]]|$1|F|3|G|5|6|7|Y|8|@]|9|@$D|Z|E|10|1|11]]|A|$]]|$1|H|3|I|5|6|7|12|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|13|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|Q]]|R|$5|M|N|O|A|$P|S]]]]

You need to break this down into two steps:

1) Sort the vertices into clockwise order. See <a href="https://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order">this question and its answers</a>.

2) Find a diagonal which is inside the quadrilateral (if the quadrilateral is concave, only one of these will be inside. If convex, both are). See <a href="https://stackoverflow.com/questions/2816572/diagonal-of-polygon-is-inside-or-outside">this question and its answers</a>.

Once you've got that, it should be obvious how to find the two triangles.

Here's a riddle for you. You have a polygon composed of exactly 4 vertices, call them v1, v2, v3, v4. They are given in any random order. How would you split these vertices into two sets, each defining a triangle, such that both triangles make up the polygon without overlap.

The result should look like this: 

Triangle 1: v1, v2, v3
Triangle 2: v2, v3, v4

... the trick is, the triangles can't overlap, and those points are given in any order, without any indication of their x,y coordinates. Is this even possible? If not, please suggest the best way to triangularize a 4-point polygon whose coordinates ARE known. I'm looking for an efficient loop.

Triangularizing an arbitrary 4-Vertex Polygon

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

这是给你的谜语。你有一个正好由4个顶点组成的多边形，称它们为v1，v2，v3，v4。它们以任意的随机顺序给出。如何将这些顶点拆分为两个集合，每个集合定义一个三角形，以便这两个三角形组成没有重叠的多边形。结果应该如下所示：三角形1: v1，v2，v3三角形2: v2，v3，v4..。诀窍是，三角形不能重叠，这些点以任何顺...

问对任意四顶点多边形进行三角化
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问对任意四顶点多边形进行三角化EN