问题标签 [triangle-count]

我正在使用 Trinigy 3d 引擎，它报告模型在渲染期间的三角形数量是模型显示中的两倍（假设是 4000 而不是 2000）。如果我使用额外的轮廓着色器渲染模型，它会报告 6000 个三角形，所以这不是简单的复制。可能是什么问题呢？

我知道这个问题有很多答案。但是，我发现他们都没有真正做到这一点。
有人争辩说，循环（几乎）与强连接组件相同（s.在有向图中查找所有循环），因此可以使用为该目标设计的算法。
一些人认为，可以通过 DFS 并检查后边来找到循环（s. boost graph documentation on file dependencies）。

我现在想对是否可以通过 DFS 检测到图中的所有循环并检查后边提出一些建议？
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf（在 SO 上找到）说明了一种基于循环基础的方法。就我个人而言，我觉得它不是很直观，所以我正在寻找不同的解决方案。

编辑：我最初的看法显然是错误的。S.下一个答案是“白痴”。
初步意见：我的意见是，当 DFS-VISIT（S. DFS 的伪代码）新进入每个尚未访问的节点时，它确实可以这样工作。从这个意义上说，每个顶点都展示了一个循环的潜在开始。此外，由于 DFS 访问每条边一次，因此也覆盖了通向循环起点的每条边。因此，通过使用 DFS 和后端检查，确实应该可以检测到所有图中的循环。请注意，如果存在具有不同数量的参与者节点的循环（例如三角形、矩形等），则必须进行额外的工作来区分每个循环的实际“形状”。

gl_PrimitiveID似乎计算了渲染的基元数量。这似乎可以通过片段和几何着色器获得。

这是否是视锥体中渲染三角形的准确计数（假设只有 tris，因为图元 ID 也适用于线和点）而不是整个场景？

修订版 1
我看过这个线程：所有可能的毕达哥拉斯三元组
看起来与我的相似，但由于某种原因我无法让我的工作......这是我的代码：

输出：

DEBUG_01：a = 95，b = 228，c = 247

DEBUG_01：a = 96，b = 110，c = 146
DEBUG_01：a = 96，b = 128，c = 160
DEBUG_01：a = 96，b = 180 , c = 204
DEBUG_01: a = 96, b = 247, c = 265
DEBUG_01: a = 96, b = 280, c = 296
DEBUG_01: a = 96, b = 378, c = 390
DEBUG_01: a = 98, b = 336, c = 350
DEBUG_01: a = 99, b = 132, c = 165
DEBUG_01: a = 99, b = 168, c = 195
DEBUG_01: a = 99, b = 440, c = 451
DEBUG_01: a = 100 , b = 105, c = 145
DEBUG_01: a = 100, b = 240, c = 260
DEBUG_01: a = 100, b = 495, c = 505
DEBUG_01: a = 102, b = 136, c = 170
DEBUG_01: a = 102，b = 280，c = 298
DEBUG_01：a = 104，b = 153，c = 185
DEBUG_01：a = 104，b = 195，c = 221
DEBUG_01：a = 104，b = 330，c = 346
DEBUG_01：a = 105，b = 140，c = 175
DEBUG_01：a = 105，b = 208，c = 233
DEBUG_01：a = 105，b = 252，c = 273
DEBUG_01：a = 105，b = 360，c = 375
DEBUG_01：a = 108，b = 144，c = 180
DEBUG_01：a = 108，b = 231 , c = 255
DEBUG_01: a = 108, b = 315, c = 333
DEBUG_01: a = 108, b = 480, c = 492
DEBUG_01: a = 110, b = 264, c = 286
DEBUG_01: a = 111, b = 148, c = 185
DEBUG_01: a = 112, b = 180, c = 212
DEBUG_01: a = 112, b = 210, c = 238
Triangel med hypotenusan 400: a = 112, b = 384
DEBUG_01: a = 112, b = 384，c = 400
DEBUG_01：a = 112，b = 441，c = 455
DEBUG_01：a = 114，b = 152，c = 190
DEBUG_01：a = 114，b = 352，c = 370
DEBUG_01：a = 115，b = 252，c = 277
DEBUG_01：a = 115，b = 276，c = 299
DEBUG_01：a = 117，b = 156，c = 195
DEBUG_01：a = 117，b = 240，c = 267
DEBUG_01：a = 119，b = 120，c = 169
DEBUG_01：a = 119，b = 408 , c = 425
DEBUG_01: a = 120, b = 126, c = 174
Triangel med hypotenusan 200: a = 120, b = 160
DEBUG_01: a = 120, b = 160, c = 200
DEBUG_01: a = 120, b = 182, c = 218
DEBUG_01: a = 120, b = 209, c = 241
DEBUG_01: a = 120, b = 225, c = 255
DEBUG_01: a = 120, b = 288, c = 312
DEBUG_01: a = 120, b = 350，c = 370
DEBUG_01：a = 120，b = 391，c = 409
DEBUG_01：a = 120，b = 442，c = 458
DEBUG_01：a = 123，b = 164，c = 205
DEBUG_01：a = 125，b = 300，c = 325
DEBUG_01：a = 126，b = 168，c = 210
DEBUG_01：a = 126，b = 432，c = 450
DEBUG_01：a = 128，b = 240，c = 272
DEBUG_01：a = 129，b = 172，c = 215
DEBUG_01：a = 130，b = 144 , c = 194
DEBUG_01: a = 130, b = 312, c = 338
DEBUG_01: a = 132, b = 176, c = 220
DEBUG_01: a = 132, b = 224, c = 260
DEBUG_01: a = 132, b = 351，c = 375
DEBUG_01：a = 132，b = 385，c = 407
DEBUG_01：a = 132，b = 475，c = 493
DEBUG_01：a = 133，b = 156，c = 205
DEBUG_01：a = 133 , b = 456, c = 475
DEBUG_01: a = 135, b = 180, c = 225
DEBUG_01：a = 135，b = 324，c = 351
DEBUG_01：a = 135，b = 352，c = 377
DEBUG_01：a = 136，b = 255，c = 289
DEBUG_01：a = 136，b = 273，c = 305
DEBUG_01：a = 138，b = 184，c = 230
DEBUG_01：a = 140，b = 147，c = 203
DEBUG_01：a = 140，b = 171，c = 221
DEBUG_01：a = 140，b = 225 , c = 265
DEBUG_01: a = 140, b = 336, c = 364
Triangel med hypotenusan 500: a = 140, b = 480
DEBUG_01: a = 140, b = 480, c = 500
DEBUG_01: a = 141, b = 188，c = 235
DEBUG_01：a = 144，b = 165，c = 219
DEBUG_01：a = 144，b = 192，c = 240
DEBUG_01：a = 144，b = 270，c = 306
DEBUG_01：a = 144， b = 308，c = 340
DEBUG_01：a = 144，b = 420，c = 444
DEBUG_01：a = 145，b = 348，c = 377
DEBUG_01：a = 145，b = 408，c = 433
DEBUG_01：a = 147，b = 196，c = 245
DEBUG_01：a = 150，b = 200，c = 250
DEBUG_01：a = 150，b = 360，c = 390
DEBUG_01：a = 152，b = 285，c = 323
DEBUG_01：a = 152，b = 345，c = 377
DEBUG_01：a = 153，b = 204 , c = 255
DEBUG_01: a = 153, b = 420, c = 447
DEBUG_01: a = 155, b = 372, c = 403
DEBUG_01: a = 155, b = 468, c = 493
DEBUG_01: a = 156, b = 208, c = 260
DEBUG_01: a = 156, b = 320, c = 356
DEBUG_01: a = 156, b = 455, c = 481
DEBUG_01: a = 156, b = 495, c = 519
DEBUG_01: a = 159 , b = 212, c = 265
DEBUG_01: a = 160, b = 168, c = 232
DEBUG_01：a = 160，b = 231，c = 281
DEBUG_01：a = 160，b = 300，c = 340
DEBUG_01：a = 160，b = 384，c = 416
DEBUG_01：a = 161，b = 240，c = 289
DEBUG_01：a = 162，b = 216，c = 270
DEBUG_01：a = 165，b = 220，c = 275
DEBUG_01：a = 165，b = 280，c = 325
DEBUG_01：a = 165，b = 396 , c = 429
DEBUG_01: a = 168, b = 224, c = 280
DEBUG_01: a = 168, b = 270, c = 318
DEBUG_01: a = 168, b = 315, c = 357
DEBUG_01: a = 168, b = 374，c = 410
DEBUG_01：a = 168，b = 425，c = 457
DEBUG_01：a = 168，b = 490，c = 518
DEBUG_01：a = 170，b = 264，c = 314
DEBUG_01：a = 170 , b = 408, c = 442
DEBUG_01: a = 171, b = 228, c = 285
DEBUG_01：a = 174，b = 232，c = 290
DEBUG_01：a = 175，b = 288，c = 337
DEBUG_01：a = 175，b = 420，c = 455
DEBUG_01：a = 176，b = 210，c = 274
DEBUG_01：a = 176，b = 330，c = 374
Triangel med hypotenusan 500：a = 176，b = 468
DEBUG_01：a = 176，b = 468，c = 500
DEBUG_01：a = 177，b = 236， c = 295
DEBUG_01：a = 180，b = 189，c = 261
Triangel med hypotenusan 300：a = 180，b = 240
DEBUG_01：a = 180，b = 240，c = 300
DEBUG_01：a = 180，b = 273 , c = 327
DEBUG_01: a = 180, b = 299, c = 349
DEBUG_01: a = 180, b = 385, c = 425
DEBUG_01: a = 180, b = 432, c = 468
DEBUG_01: a = 183, b = 244，c = 305
DEBUG_01：a = 184，b = 345，c = 391
DEBUG_01：a = 185，b = 444，c = 481
DEBUG_01：a = 186，b = 248，c = 310
DEBUG_01：a = 189，b = 252，c = 315
DEBUG_01：a = 189，b = 340，c = 389
DEBUG_01：a = 190，b = 336，c = 386
DEBUG_01：a = 190，b = 456，c = 494
DEBUG_01：a = 192，b = 220，c = 292
DEBUG_01：a = 192，b = 256 , c = 320
DEBUG_01: a = 192, b = 360, c = 408
DEBUG_01: a = 192, b = 494, c = 530
DEBUG_01: a = 195, b = 216, c = 291
DEBUG_01: a = 195, b = 260, c = 325
DEBUG_01: a = 195, b = 400, c = 445
DEBUG_01: a = 195, b = 468, c = 507
DEBUG_01: a = 196, b = 315, c = 371
DEBUG_01: a = 198 , b = 264, c = 330
DEBUG_01: a = 198, b = 336, c = 390
DEBUG_01：a = 200，b = 210，c = 290
DEBUG_01：a = 200，b = 375，c = 425
DEBUG_01：a = 200，b = 480，c = 520
DEBUG_01：a = 201，b = 268，c = 335
DEBUG_01：a = 203，b = 396，c = 445
DEBUG_01：a = 204，b = 253，c = 325
DEBUG_01：a = 204，b = 272，c = 340
DEBUG_01：a = 205，b = 492 , c = 533
DEBUG_01: a = 207, b = 224, c = 305
DEBUG_01: a = 207, b = 276, c = 345
DEBUG_01: a = 208, b = 306, c = 370
DEBUG_01: a = 208, b = 390, c = 442
DEBUG_01: a = 210, b = 280, c = 350
DEBUG_01: a = 210, b = 416, c = 466
DEBUG_01: a = 213, b = 284, c = 355
DEBUG_01: a = 216 , b = 288, c = 360
DEBUG_01: a = 216, b = 405, c = 459
DEBUG_01：a = 216，b = 462，c = 510
DEBUG_01：a = 217，b = 456，c = 505
DEBUG_01：a = 219，b = 292，c = 365
DEBUG_01：a = 220，b = 231，c = 319
DEBUG_01：a = 220，b = 459，c = 509
DEBUG_01：a = 222，b = 296，c = 370
DEBUG_01：a = 224，b = 360，c = 424
DEBUG_01：a = 224，b = 420 , c = 476
DEBUG_01: a = 225, b = 272, c = 353
DEBUG_01: a = 225, b = 300, c = 375
DEBUG_01: a = 228, b = 304, c = 380
DEBUG_01: a = 228, b = 325, c = 397
DEBUG_01: a = 231, b = 308, c = 385
DEBUG_01: a = 231, b = 392, c = 455
DEBUG_01: a = 232, b = 435, c = 493
DEBUG_01: a = 234 , b = 312, c = 390
DEBUG_01: a = 234, b = 480, c = 534
DEBUG_01：a = 237，b = 316，c = 395
DEBUG_01：a = 238，b = 240，c = 338
DEBUG_01：a = 240，b = 252，c = 348
DEBUG_01：a = 240，b = 275，c = 365
Triangel med hypotenusan 400：a = 240，b = 320
DEBUG_01：a = 240，b = 320，c = 400
DEBUG_01：a = 240，b = 364，c = 436
DEBUG_01：a = 240，b = 418， c = 482
DEBUG_01：a = 240，b = 450，c = 510
DEBUG_01：a = 243，b = 324，c = 405
DEBUG_01：a = 246，b = 328，c = 410
DEBUG_01：a = 248，b = 465，c = 527
DEBUG_01：a = 249，b = 332，c = 415
DEBUG_01：a = 252，b = 275，c = 373
DEBUG_01：a = 252，b = 336，c = 420
DEBUG_01：a = 252， b = 405，c = 477
DEBUG_01：a = 255，b = 340，c = 425
DEBUG_01：a = 255，b = 396，c = 471
DEBUG_01：a = 256，b = 480，c = 544
DEBUG_01：a = 258，b = 344，c = 430
DEBUG_01：a = 260，b = 273，c = 377
DEBUG_01：a = 260，b = 288，c = 388
DEBUG_01：a = 261，b = 348，c = 435
DEBUG_01：a = 261，b = 380，c = 461
DEBUG_01：a = 264，b = 315 , c = 411
DEBUG_01: a = 264, b = 352, c = 440
DEBUG_01: a = 264, b = 448, c = 520
DEBUG_01: a = 264, b = 495, c = 561
DEBUG_01: a = 266, b = 312，c = 410
DEBUG_01：a = 267，b = 356，c = 445
DEBUG_01：a = 270，b = 360，c = 450
DEBUG_01：a = 273，b = 364，c = 455
DEBUG_01：a = 276 , b = 368, c = 460
DEBUG_01: a = 276, b = 493, c = 565
DEBUG_01：a = 279，b = 372，c = 465
DEBUG_01：a = 279，b = 440，c = 521
DEBUG_01：a = 280，b = 294，c = 406
DEBUG_01：a = 280，b = 342，c = 442
DEBUG_01：a = 280，b = 351，c = 449
DEBUG_01：a = 280，b = 450，c = 530
DEBUG_01：a = 282，b = 376，c = 470
DEBUG_01：a = 285，b = 380 , c = 475
DEBUG_01: a = 288, b = 330, c = 438
DEBUG_01: a = 288, b = 384, c = 480
DEBUG_01: a = 291, b = 388, c = 485
DEBUG_01: a = 294, b = 392，c = 490
DEBUG_01：a = 297，b = 304，c = 425
DEBUG_01：a = 297，b = 396，c = 495
DEBUG_01：a = 300，b = 315，c = 435
Triangel med hypotenusan 500： a = 300，b = 400
DEBUG_01：a = 300，b = 400，c = 500
DEBUG_01：a = 300，b = 455，c = 545
DEBUG_01：a = 303，b = 404，c = 505
DEBUG_01：a = 306，b = 408，c = 510
DEBUG_01：a = 308，b = 435，c = 533
DEBUG_01：a = 308，b = 495，c = 583
DEBUG_01：a = 309，b = 412，c = 515
DEBUG_01：a = 312，b = 416，c = 520
DEBUG_01：a = 312，b = 459 , c = 555
DEBUG_01: a = 315, b = 420, c = 525
DEBUG_01: a = 318, b = 424, c = 530
DEBUG_01: a = 319, b = 360, c = 481
DEBUG_01: a = 320, b = 336，c = 464
DEBUG_01：a = 320，b = 462，c = 562
DEBUG_01：a = 321，b = 428，c = 535
DEBUG_01：a = 322，b = 480，c = 578
DEBUG_01：a = 324 , b = 432, c = 540
DEBUG_01: a = 325, b = 360, c = 485
DEBUG_01：a = 327，b = 436，c = 545
DEBUG_01：a = 330，b = 440，c = 550
DEBUG_01：a = 333，b = 444，c = 555
DEBUG_01：a = 336，b = 377，c = 505
DEBUG_01：a = 336，b = 385，c = 511
DEBUG_01：a = 336，b = 448，c = 560
DEBUG_01：a = 339，b = 452，c = 565
DEBUG_01：a = 340，b = 357 , c = 493
DEBUG_01: a = 341, b = 420, c = 541
DEBUG_01: a = 342, b = 456, c = 570
DEBUG_01: a = 345, b = 460, c = 575
DEBUG_01: a = 348, b = 464，c = 580
DEBUG_01：a = 351，b = 468，c = 585
DEBUG_01：a = 352，b = 420，c = 548
DEBUG_01：a = 354，b = 472，c = 590
DEBUG_01：a = 357 , b = 360, c = 507
DEBUG_01: a = 357, b = 476, c = 595
DEBUG_01：a = 360，b = 378，c = 522
DEBUG_01：a = 360，b = 480，c = 600
DEBUG_01：a = 363，b = 484，c = 605
DEBUG_01：a = 366，b = 488，c = 610
DEBUG_01：a = 368，b = 465，c = 593
DEBUG_01：a = 369，b = 492，c = 615
DEBUG_01：a = 372，b = 496，c = 620
DEBUG_01：a = 375，b = 500 , c = 625
DEBUG_01: a = 380, b = 399, c = 551
DEBUG_01: a = 384, b = 440, c = 584
DEBUG_01: a = 390, b = 432, c = 582
DEBUG_01: a = 396, b = 403，c = 565
DEBUG_01：a = 399，b = 468，c = 615
DEBUG_01：a = 400，b = 420，c = 580
DEBUG_01：a = 414，b = 448，c = 610
DEBUG_01：a = 420 , b = 441, c = 609
DEBUG_01: a = 429, b = 460, c = 629
DEBUG_01：a = 432，b = 495，c = 657
DEBUG_01：a = 440，b = 462，c = 638
DEBUG_01：a = 460，b = 483，c = 667
DEBUG_01：a = 476，b = 480，c = 676

Antal itererade 三角：125250 Antal pytagoreiska 三角：456

如您所见，每当我运行此程序时，我都会从“counter_pyth”中得到答案“456”，根据我的老师的说法，正确答案是“386”，但我不知道我做错了什么..

修订版 2

代码：

我发现了几个与这个问题相关的主题，我只想知道为什么我的代码返回不正确的数据。所以我们必须找到第一个具有超过 500 个除数的三角形数。详细信息可以在这里找到：http ://projecteuler.net/problem=12 这是我的代码：

这给了我号码 842161320，这显然是不正确的。

我将每个元素作为“总和”、“第一”和“秒”。如果 (first + sec < sum) 我将创建这 3 个的 hashset(tmp) 并将这个 hashset 放入一个包含所有 tmp hashset 的更大的 hashset(triangle) 中。这将删除 3 个数字的重复组合。这是我的代码。它有效，但有没有更好的解决方案？

以下代码是确定整数三角形数量的算法，最大边小于或等于 MAX，具有整数中位数。Python 版本可以工作，但对于更大的 N 来说太慢了，而 C++ 版本要快得多，但没有给出正确的结果。

当 MAX 为 10 时，C++ 和 Python 都返回 3。

当 MAX 为 100 时，Python 返回 835，C++ 返回 836。

当 MAX 为 200 时，Python 返回 4088，C++ 返回 4102。

当 MAX 为 500 时，Python 返回 32251，C++ 返回 32296。

当 MAX 为 1000 时，Python 返回 149869，C++ 返回 150002。

这是 C++ 版本：

这是原始的 Python 版本：

我对 C++ 不太熟悉，所以我不知道会发生什么导致这种情况（可能是溢出错误？）。

当然，任何对算法的优化都非常受欢迎！

我在一次采访中被问到这个问题，并被告知 O(n^2) 是可能的。任何人都有一个简单的方法吗？

在这里找到一篇论文，告诉我它和矩阵乘法一样难：http: //kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

给定一个严格递增的n正整数序列A(1) < A(2) < ... < A(n)。我们需要找到边长作为3这个序列的不同元素的三角形的数量。

由于n <= 6000，检查每个可能的组合还不够快。有没有更好的算法？谢谢你的帮助。

我的伪代码：

我很难用 Java 做学校练习。我们被要求打印出这个模式：

我可以做一个三角形或沙漏形状，但我不能让它水平重复。

这是我到目前为止所拥有的：